Como calcular “inverso multiplicativo modular”, quando o denominador não é co-prime com m?

Question

Eu preciso calcular (a/b) mod m que a e b são números muito grandes.

O que estou tentando fazer é calcular (a mod m) * (x mod m) , onde x é o modular inversa de b .

Eu tentei usar Extensão euclidiana algoritmo , mas o que fazer quando b e m não são co -prime? É especificamente mencionado que b e m necessidade de ser co-prime.

Eu tentei usar o código aqui , e percebeu que, por exemplo: 3 * x mod 12 não é de todo possível para qualquer valor de x , ele não existe!

O que devo fazer? Pode o algoritmo ser modificado de alguma forma?

Answer 1

Sim, você está em apuros. x tem nenhuma solução em b*x = 1 mod m se b e m têm um divisor comum. Da mesma forma, em sua a/b = y mod m problema original, que você está procurando y tal que a=by mod m. Se um é divisível por gcd(b,m), então você pode dividir por esse fator e resolver para y. Se não, então não há nenhuma y que podem resolver a equação (ou seja a/b mod m não está definido).

Answer 2

A razão que b e m têm de ser coprime é por causa do chinês do resto Teorema. Basicamente, o problema:

3 * x mod 12

Pode ser pensado como um problema composto envolvendo

3*x mod 3 e 3*x mod 4 = 2^2

Agora, se b não é coprime a 12, isso é como tentar dividir por zero. Assim, a resposta não existe!

Isto é devido à teoria de campo em álgebra abstrata. Um campo é basicamente um conjunto que tem adição, subtracção, multiplicação, divisão e bem definida. Um campo finito é sempre da forma GF (p ^ n), em que p é primo e n é um número inteiro positivo, e as operações de adição e multiplicação são módulo p ^ n. Agora, 12 não é uma potência primária, para que o seu anel não é um campo. Assim, este problema não pode ser resolvido por qualquer b, que não é coprime a m.

Answer 3

Verifique o seguinte: http://www.math.harvard.edu / ~ sarah / magic / temas / divisão Pode ajudar. Ele explica métodos de divisão modular.