Algorithmes usuels¶
Exponentiation binaire¶
Algorithme¶
Théorème
Soit \(a\in (G,\times)\) et \(n\in\N\). On peut calculer \(a^n\) avec moins de \(2\log_2(n)\) multiplications de \(G\)
Pour développer cette idée, décomposons \(n\) en base deux
on peut écrire
Dans les deux dernières lignes, l’expression ne fait plus intervenir que \(k\) carrés et au plus \(k+1\) multiplications, avec \(k=\floor{\log_2(n)}\) (plus précisément, \(k\) carrés et un nombre de multiplications égal au nombre de \(1\) dans l’écriture binaire de \(n\)).
Sans cette technique, la cryptographie à clef publique (RSA et ElGamal) n’existeraient pas, en effet on a besoin de prendre des puissances gigantesques.
application : suites récurrentes¶
Même sans prendre de puissances gigantesques, il peut être utile de penser à l’exponentiation rapide. Prenons une suite récurrente linéaire, par exemple la suite de Fibonacci \(f_0=0\), \(f_1=1\), \(f_{n+1}=f_n+f_{n-1}\).
Trois idées de calcul :
programmer directement la récurrence. C’est effroyable, on calcule \(f_n\) avec \(f_n\) additions
fibo1(n) = if(n<=1,n,fibo1(n-1)+fibo1(n-2)); default(timer, 1) fibo1(20)
utiliser une fenêtre glissante pour ne pas recalculer les termes deux fois
fibo2(n) = { ff = [0,1]; for(k=2,n,ff=[ff[2],vecsum(ff)]); ff[2]; } fibo2(20)écrire l’itération sous forme matricielle \(F_n = A F_{n-1}\), où \(A = \left(\begin{array}{cc}1 & 1 \\ 1 & 0\end{array}\right)\) et \(F_n = \left(\begin{array}{c}f_{n+1}\\f_{n}\end{array}\right)\) de sorte que \(F_n=A^{n-1}F_0\), et comme \(F_0=(1,0)\)
fibo3(n) = ([1,1;1,0]^(n-1))[1,1] fibo3(20)
Calculs modulaires¶
Si l’on cherche un résultat dans une structure quotient, il est souvent essentiel d’effectuer les calculs dans le quotient.
exemple¶
Quels sont les 3 derniers chiffres de \(3^{12345678}\) ?
On veut \(3^{12345678}\bmod 1000\), et même si l’on calcule la puissance avec une puissance rapide il y a deux solutions
calculer \(3^{12345678}\in\Z\) puis réduire modulo 1000
3^12345678 % 1000
calculer \((3 \bmod 1000)^{12345678}\)
Mod(3,1000)^12345678
De même, les calculs modulaires fournissent une manière alternative (et plus efficace) de calculer les termes de suites récurrentes. Pour la suite de Fibonacci, d’annulateur \(x^2-x-1\), on a \(x^n \equiv f_nx+f_{n-1} \bmod x^2-x-1\).
D’où un algorithme encore meilleur
fibo4(n)=polcoeff(lift(Mod(x,x^2-x-1)^n),1) fibo4(20)
Ordre d’un élément¶
Dans le cas où l’on connaît l’ordre \(n\) du groupe, on sait que l’ordre est un diviseur de \(n\).
Proposition
\(x\in G\) est d’ordre \(n\) si et seulement si \(x^n=1\) et pour tout premier \(p\mid n\), \(x^{n/p}\neq 1\).
générateurs de \(\F_p^\ast\)¶
Ce groupe est cyclique, mais il n’existe pas de formule pour en donner un générateur. On sait simplement qu’ils sont au nombre de \(\phi(p-1)\), ce qui fait une bonne proportion.
On en trouve donc en essayant les éléments un par un
generateur(p) = {
q = factor(p-1)[,1];
a = Mod(1,p);
while(1,
a += 1;
for(i=1,#q,
if(a^((p-1)/q[i])==1, next(2));
);
break();
);
a;
}
preuve de primalité¶
Proposition
\(n\in\N\) est premier si et seulement si il existe \(a<n\) tel que pour tout premier \(p\mid n-1\), \(a^{\frac{n-1}p}\not\equiv1\bmod n\).
De plus, si \(n\) est effectivement premier, il existe \(\phi(n-1)\) tels entiers \(a<n\).
Exemple : on démontre que \(n=\frac{3^{103}-1}2\) est premier.
generateur((3^103-1)/2)
generateur(2^127-1)
critère d’irréductibilité¶
Proposition
Sur \(\F_p[x]\), \(x^{p^n}-x\) est produit de tous les irréductibles de degré \(d\mid n\).
Corollaire
Soit \(P(x)\in\F_p[x]\) de degré \(n\), alors \(P\) est irréductible ssi \(P(x)\mid x^{p^n}-x\) et pour tout premier \(q\mid n\), \(\pgcd(x^{p^{n/q}}-x,P(x))=1\).
isirred(P,p) = {
n = poldegree(P);
q = factor(n)[,1];
xP = Mod(x,P);
for(i=1,#q,
if(gcd(lift(xP^p^(n/q[i])-x),P)!=1,return(0));
);
return(1);
}
findirred(n,p) = {
until(isirred(P,p),
P = x^n+random(Mod(1,p)*x^(n-1));
);P;
}
findirred(3,3)
findirred(50, 101)
Carrés¶
Proposition
Les carrés de \(\F_p^\ast\) sont l’image du morphisme \(x\mapsto x^2\), il y en a \(\frac{p-1}2\).
Proposition
\(x^p-x\) est scindé sur \(\F_p\)
les racines de \(x^{\frac{p-1}2}-1\) sont les carrés de \(\F_p^\ast\)
symbole de Legendre¶
symbole de Legendre
Soit \(p\) un nombre premier impair. On définit un caractère (un morphisme de groupes)
en posant \(\kronecker ap=1\) si \(a\) est résidu quadratique modulo \(p\), et \(\kronecker ap=-1\) sinon. On étend ce symbole en une fonction \(\Z\to\set{-1,0,1}\) en posant \(\kronecker ap = \kronecker{a\bmod p}p\) et \(\kronecker 0p=0\).
symbole de Jacobi
On étend le symbole de Legendre à tout couple d’entiers \(a,n\), avec \(n\) impair, de la manière suivante : si \(n=\prod p_i^{e_i}\), on pose
Ce symbole est multiplicatif en \(a,n\), c’est-à-dire que pour tous \(a,b,m,n\) on a
réciprocité quadratique¶
réciprocité quadratique
Soient \(m,n\in\Z\) impairs avec \(\pgcd(m,n)=1\). Alors on a les formules
\(\kronecker{-1}m=(-1)^{\frac{m-1}2}\) ;
\(\kronecker2m=(-1)^{\frac{m^2-1}8}\) ;
\(\kronecker mn\kronecker nm = (-1)^{\frac{(m-1)(n-1)}4}\).
Racines carrées¶
Un cas simple : si \(p=3\bmod 4\). En effet, puisque \(x^p=x\), \(x^{p+1}=x^2\) avec \(p+1\) qui est divisible par 4.
Théorème
Soit \(p\equiv 3\bmod 4\). Alors pour tout \(a\in\Z/p\Z\),
En fait, la racine est ici facile à calculer parce que \(2\) est premier à l’ordre du sous-groupe des carrés.
Quand \(p=1\bmod 2^e\), on peut s’en sortir en séparant ce qui se passe sur le 2 Sylow et sur le complémentaire. On va présenter une autre méthode, pas plus efficace, mais plus élégante !
Algorithme de Cipolla¶
Cet algorithme consiste à passer par l’extension \(\F_{p^2}\), dans laquelle tout élément de \(\F_p\) possède une racine carrée. Pour tout \(a\in\F_p\), en notant \(x\in\F_{p^2}\) une racine de \(x^2-a\), on a la disjonction
de sorte que pour tout \(u\) dans \(\F_p\) et \(v\in\F_{p^2}\) une racine d’un non résidu quadratique, on a
L’astuce de Cipolla consiste à choisir \(u\) tel que \(u^2-a\) n’est pas un carré modulo \(p\), et définir \(v\) comme une racine carrée de \(u^2-a\). Alors le calcul ci-dessus montre que l’élément
est une racine carrée de \(a\), dans \(\F_{p^2}\). Il appartient en particulier à \(\F_p\) si et seulement si \(a\) est un carré dans \(\F_p\).
Le calcul de \(x\) se fait alors de la manière suivante :
déterminer \(u\) tel que \(u^2-a\) n’est pas un carré modulo \(p\)
construire \(\F_{p^2}\) comme \(\F_p[v]/(v^2-(u^2-a))\)
calculer \(x=(u+v)^{\frac{p+1}2}\) par exponentiation rapide
le résultat \(x\) est dans \(\F_p\) et est une racine carrée de \(a\).
racine(a,p) = {
u=1;while(Mod(u^2-a,p)^((p-1)/2)==1,u++);
lift(Mod(u+v,v^2-u^2+a)^((p+1)/2));
}
p = (11^73-1)/10 racine(6,p)
Racines de polynômes¶
Soit \(P(x)\in\F_p[x]\) un polynôme sans facteur carré, et notons \(A=\set{a\in\F_p, P(a)=0}\) l’ensemble de ses racines dans \(\F_p\).
Puisque
on a
Le degré de ce pgcd donne donc \(\#A\), le nombre de racines de \(P\) dans \(\F_p\).
Par ailleurs, on peut affiner légèrement :
factorisation qui traduit la partition
Ainsi, on trouve facilement le facteur de \(P(x)\) dont les racines sont des carrés en calculant
Mais par translation,
renvoie le facteur de \(P\) dont les racines \(a\) sont telles que \(a+b\) est un carré.
Pour \(b\) aléatoire, la probabilité que tous les \(a+b\) soient simultanément des carrés est de \(2^{-\deg P}\)…
Algorithme d’Euclide étendu¶
Proposition
Soient \(a,b\in\Z\), on définit \(r_0,r_1=a,b\) et pour \(k\geq 1\) tel que \(r_k>0\) \(r_{k+1}\) par la division euclidienne
Alors il existe \(k\) tel que \(r_{k+1}=0\), auquel cas \(r_k=\pgcd(a,b)\).
Démonstration
D’une part \(\pgcd(r_{k-1},r_k) = \pgcd(r_k, r_{k+1})\), d’autre part \(r_k\) est strictement décroissant dans \(\N\), d’où la terminaison.
Si l’on veut obtenir une relation de Bézout
il est commode d’introduire la famille de relations
où par linéarité \(u_k\) et \(v_k\) obéissent à la récurrence donnée par \(r_k\)
euclide(a,b) = {
u=[1,0,a;0,1,b];
while(u[2,3],
q = u[1,3] \ u[2,3];
u = [0,1;1,-q]*u;
);
u[1,];
}
Applications¶
inversion modulaire¶
lemme chinois¶
Théorème
Soient \(m_1,\dots m_k\) premiers entre eux deux à deux. Alors en posant \(M=\prod m_i\) on a un isomorphisme d’anneaux
d’inverse \((x_i)\mapsto \sum u_iM_i x_i\) où \(M=M_im_i\) et \(u_iM_i=1\bmod m_i\)
Exemple
v = vector(6, k, k^5+k-1 )
w = vector(6, k, Mod(v[k], x - k) ) chinese(w)
approximations rationnelles¶
On peut utiliser l’algorithme d’Euclide pour représenter un élément \(a\bmod n\) sous forme de quotient.
En effet, en écrivant l’algorithme d’Euclide entre \(n\) et \(a\), chaque étape
se traduit par une congruence
soit
De plus, on sait que l’on a toujours \(v_k < n\).
une application
Soit \(p\equiv1\bmod 4\) un nombre premier, il existe \(0<a<b\) uniques tels que \(p=a^2+b^2\).
Soit \(p\equiv 1\bmod 4\). Alors \(-1\) est un carré modulo \(p\), donc il existe un unique \(0<x<\frac p2\) tel que \(x^2+1\equiv 0[p]\).
On applique l’algorithme d’Euclide étendu à \(p\) et \(x\) jusqu’à obtenir une écriture
avec \(r_k<\sqrt p\). Alors a priori on a seulement \(p\mid r_k^2+v_k^2\), mais une analyse plus détaillée de l’algorithme montre qu’on a l’égalité.
sumsquares(p) = {
if(p%4==3,0,
x = sqrt(Mod(-1,p));
U=[1,0,p;0,1,lift(x)];
while(U[2,3]^2>p,
q = U[1,3] \ U[2,3];
U = [0,1;1,-q]*U;
);
abs(U[2,2..3]);
);
}
[ sumsquares(p) | p <- primes(100), p%4==1 ]
Cette technique permet de résoudre plus généralement les équations
mais dans le cas général on n’est pas sûr que le couple \(a,b\) soit fourni par une approximation de l’algorithme d’Euclide, en revanche au moins l’un des deux termes le sera, et il est trivial de retrouver l’autre en calculant une racine dans \(\Z\). Cette technique est due à Cornacchia.