Trouver l'inverse d'un nombre modulo un premier

Question

Je pensais à un algorithme pour résoudre la congruence ax = 1 mod p avec p premier. Je pensais utiliser le théorème de Fermat. Depuis que je sais que

a^(p-1) = 1 mod p

et que

a^(p-1) = a * (a^(p-2))

Cela signifie que a^(p-2) mod p est la solution. Malheureusement cette solution, bien que mathématiquement correcte, n'est pas bonne pour l'ordinateur puisque pour les grands nombres premiers je dois faire a^(p-2) qui n'est habituellement pas calculable.

Quel algorithme est bon pour l'informatique?

Answer 1

depuis pour les grands nombres premiers que je dois faire a^(p-2) qui est généralement pas calculable.

Vous avez besoin exponentiation modulaire, avec le exponentiation by squaringmentioned by IVlad vous avez seulement besoin Θ(log p) multiplications modulaires de nombres de taille au plus p-1. Les résultats intermédiaires sont délimités par p^2, donc en dépit de a^(p-2) n'étant pas calculable pour les grands nombres premiers, (a^(p-2)) % p est habituellement. Cette méthode est simple à mettre en oeuvre:

unsigned long long invert_mod(unsigned long long a, unsigned long long p) { 
    unsigned long long ex = p-2, result = 1; 
    while (ex > 0) { 
     if (ex % 2 == 1) { 
      result = (result*a) % p; 
     } 
     a = (a*a) % p; 
     ex /= 2; 
    } 
    return result; 
} 

mais présente quelques inconvénients. (p-1)^2 doit être représentable dans le type utilisé (pas de problème [sauf énormep] si des entiers de précision arbitraires sont utilisés), ou vous obtenez des résultats invalides en raison d'un débordement, et il utilise toujours au moins log (p-2)/log 2 multiplications modulaires.

L'algorithme d'Euclide étendu, as suggested by user448810, ou la méthode de manière équivalente fraction continue, ne produit des valeurs intermédiaires plus grandes que p, évitant ainsi tous les problèmes de débordement si p est représentable, et doit généralement moins divisions. De plus, il calcule l'inverse modulaire non seulement pour les nombres premiers, mais pour deux nombres quelconques.

unsigned long long invert_mod(unsigned long long a, unsigned long long p) { 
    unsigned long long new = 1, old = 0, q = p, r, h; 
    int pos = 0; 
    while (a > 0) { 
     r = q%a; 
     q = q/a; 
     h = q*new + old; 
     old = new; 
     new = h; 
     q = a; 
     a = r; 
     pos = !pos; 
    } 
    return pos ? old : (p - old); 
} 

Le code est un peu plus long, mais un compilateur optimisant doit compiler à une courte boucle en utilisant une seule division par itération.

Answer 2

Il n'y a aucune raison que ce n'est pas un bon algorithme pour les ordinateurs, il faut juste faire attention à la mise en œuvre, ce qui n'est pas très trivial je suppose, mais ce n'est pas difficile non plus.

Il suffit d'utiliser exponentiation by squaring, alors il n'aura probablement pas d'importance p.

a^n = a^(n/2) * a^(n/2) for n even 
    = a*a^(n - 1) for n odd 

Answer 3

La façon normale de calculer l'inverse modulaire est par l'algorithme d'Euclide étendu:

function inverse(x, m) 
    a, b, u := 0, m, 1 
    while x > 0 
     q, r := divide(b, x) 
     x, a, b, u := b % x, u, x, a - q * u 
    if b == 1 return a % m 
    error "must be coprime"