Note
Soit \(b\) un entier supérieur ou égal à deux, pour tout entier \(n\geq0\) il existe une unique suite d’entiers \(a_k,\dots a_0\) tels que \(0\leq a_i<b\), \(a_k\neq 0\) et
De plus, on a \(k = \floor{ \log_b n }\).
Ecrire une fonction evalue_base(a,b) qui renvoie l’entier \(n\) dont
a est la suite de chiffres en base b.
Par exemple, evalue_base([1,1,0,1],2) retourne 13.
evalue_base(a,b) := {
local(j);
sum(v[j]*b^(j),j,0,length(v)-1);
}
Ecrire une fonction ecriture(n,b) qui renvoie la liste \([a_k,\dots a_0 ]\).
\(a_0\) est le reste de la division euclidienne de \(n\) par \(b\), et les chiffres \(a_k,\dots a_1\) forment l’écriture en base \(b\) du quotient.
On a donc sous forme récursive
ecriture(n,b) := {
local q,r;
if(n=0) return [];
q := iquo(n,b);
r := irem(n,b);
return concat(ecriture(q,b),[r]);
}
ou sous forme itérative, dans laquelle on initialise dès le début une lsite de la bonne taille
1 2 3 4 5 6 7 8 9 10 | ecriture(n,b) := {
local a,k,j;
k := floor(log(n)/log(b));
a := newList(k+1);
for(j:=0;j<=k;j++) {
a[k-j] := irem(n,b);
n := iquo(n,b);
}
return a;
}
|
Note
Soit \(P(x)\in\K[x]\) un polynôme de degré \(r\). Le schéma d’évaluation de Hörner consiste à écrire
Ecrire une fonction evalue_horner(a,b) qui calcule \(n\) en utilisant
le schéma de Hörner.
evalue_horner(a,b) := {
local(j);local(s);
s := 0;
for(j:=0;j<length(a);j++) {
s := b*s + a[j];
}
return s;
}
Déterminer la plus petite base \(b\) telle que le nombre dont l’écriture en
base \(b\) est formée de \(157\) chiffres 1 soit un nombre premier (utiliser
la fonction is_pseudoprime).
v := seq(1, k, 1, 157);
for(b:=2;b<100;b++) { if(is_pseudoprime(evalue_horner(v,b))) break; }
b;
On peut aller plus vite : pour toute base \(b\) ce nombre vaut \(\sum_{j=0}^{156}b^j=\frac{b^{157}-1}{b-1}\).
b:=2; while(is_pseudoprime((b^157-1)/(b-1))=0) {b++}; b;
Au passage, il y a une réponse pour \(l=157\) qui est un nombre premier, si \(l\) n’est pas premier ce n’est jamais le cas à cause de la factorisation cyclotomique suivante
Ecrire une fonction puissance_naive(a,n) qui effectue le calcul via la
formule élémentaire
Quel est le nombre de multiplications effectuées ?
puissance_naive(a,n) := {
if (n==0) return 1;
return a*puissance_naive(a,n-1);
}
Cette fonction effectue \(n-1\) multiplications (en négligeant la dernière multiplication par 1).
On peut faire beaucoup mieux.
Note
Pour obtenir ce résultat, on écrit \(n\) en base \(2\)
\[n=e_0+2e_1+4e_2+\dots 2^re_r\]
on peut alors écrire \(a^n\) sous deux formes
\[a^n = a^{e_0} \times (a^2)^{e_1} \times \dots (a^{2^r})^{e_r}\]
ou bien
\[a^n = a^{e_0} \times \bigl( a^{e_1} \times \bigl(\dots a^{e_r}\bigr)^2\dots\bigr)^2\bigr)^2.\]
On a écrit la fonction récursive suivante
puissance_rec(a,n):= {
if(n==0) return 1;
if(irem(n,2)) {
return a*puissance_rec(a^2,iquo(n,2));
}
else {
return puissance_rec(a^2,n/2);
}
}
À quelle écriture correspond-elle ?
Cette fonction effectue le calcul selon la première écriture.
Modifier la fonction puissance_rec pour qu’elle corresponde à l’autre écriture.
Dans l’autre sens on «met le carré en dehors»
puissance_rec2(a,n):= {
if(n==0) return 1;
if(irem(n,2)) {
return a*puissance_rec(a,iquo(n,2))^2;
}
else {
return puissance_rec(a^2,n/2)^2;
}
}
Ecrire une fonction puissance_iter(a,n) qui calcule \(a^n\) de manière
itérative. On essaiera de ne pas calculer d’abord la décomposition de \(n\) en
base \(2\), mais de le faire au cours du calcul (comme dans les fonctions
récursives).
Si l’on ne veut pas calculer a priori la décomposition binaire de \(n\), la solution la plus simple correspond au premier algorithme récursif.
puissance_iter(a,n):= { local(r:=1); while(n>0) { if (n%2==1) {r := r*a}; a := a^2; n := iquo(n,2); }; return(r); }
Modifier la fonction puissance_iter(a,n) pour qu’elle accepte un
paramètre b et fasse le calcul en décomposant selon une base \(b\)
(on pourra cette fois commencer par calculer la décomposition).
Tester votre fonction sur le calcul de Mod(3, 2^1024+1)^(2^(2^15)-1).
Pour quelles bases obtient-on les meilleurs résultats ?
Cette fois on utilise le schéma de Hörner en précalculant l’écriture de \(n\) en base \(b\), ainsi que les quelques puissances de \(a^j\) pour \(j<b\).
On obtient de meilleurs résultats sur les puissances de 2, pour ce calcul 256 est une bonne base.
Ecrire une fonction fib_rapide(n) qui calcule le \(n\)-ième terme de la
suite de Fibonacci par puissance rapide de la matrice A:=[[0,1],[1,1]].
Quel est l’avantage par rapport aux méthodes employées précédemment ?
fib_mat(n):={ local(A); A := matrix(2,2,[1,1,1,0]); return( (A^n)[0,0] ); };
La complexité est à présent de \(O(\log(n))\) multiplications matricielles \(2\times 2\), d’entiers dont la taille croît en \(O(n)\), d’où une complexité dominée par les derniers produits en \(O(n\log(n)\log\log n)\)
Quel est le nombre de chiffres de \(F_{F_{F_{F_{F_4}}}}\) ? (utiliser l’expression algébrique exacte de \(F_n\)).
Ce nombre est trop gros pour être calculé par xcas. En revanche on peut calculer le terme d’avant, \(n=F_{F_{F_{F_{4}}}}\).
n := (fib_mat@@4)(4)
Il reste à trouver le nombre de chiffres de \(F_n\), soit la valeur de \(\log_{10}F_n\).
Soient \(\phi=\frac{1+\sqrt5}2\) et \(1-\phi\) les deux racines de \(x^2=x+1\), on a l’expression
En passant au logarithme, on a \(\log F_n\sim n\log\phi\), et plus précisément
avec \(0<\epsilon=\log_{10}(1+(1-\phi)^n)<(1-\phi)^n\).
phi := (1+sqrt(5))/2;
r := n * logb(phi,10) - logb(5,10)/2;
ceil(r);
Exemple à retenir : calculer les trois derniers chiffres de \(3^{123456789}\).
Pour obtenir les trois derniers chiffres, il faut prendre le reste modulo 1000. Et puisque la projection \(\Z\to \Z/1000\Z\) est un morphisme d’anneaux, il faut surtout effectuer tout le calcul modulo 1000 en écrivant:
pow_rec(3%1000,123456789)
et non pas prendre le reste à la fin, ce qui demande de calculer un nombre gigantesque (ce que Xcas ne peut pas faire):
pow_rec(3,123456789) % 1000
Déterminer les fonctions xcas qui effectuent les exponentiations modulaires \(a^k\bmod n\), ou \(P^n\bmod Q\) pour des polynômes \(P\) et \(Q\).
Soit \(n=pq\) où \(p\) et \(q\) sont des nombres premiers distincts. A quelle condition sur \(e\) la fonction \(f_e:a\to a^e\) est-elle une bijection de \(\Z/n\Z\) ?
Il faut et il suffit que \(e\) soit premier à \(\phi(n)=(p-1)(q-1)\). Dans ce cas, l’inverse est \(f_d\) où \(d\) est l’inverse de \(e\) modulo \(\phi(n)\).
remarque: on vérifie que \(f_d\) et \(f_e\) sont inverses l’une de l’autre, cela découle du théorème de Lagrange, de sorte que la condition sur \(e\) est suffisante. Elle est aussi nécessaire si l’on considère un élément d’ordre un éventuel diviseur premier commun à \(e\) et \(\phi(n)\), lequel élément existe d’après le lemme de Cauchy (ou les théorèmes de Sylow): cet élément serait dans le noyau de \(f_e\).
On pose \(e=65537\). Programmer efficacement l’application \(f_e\). Programmer également l’application inverse de manière efficace.
\(e\) vaut \(2^{16}+1\), si bien que son écriture binaire est très simple. Il suffit d’élever 16 fois au carré, puis de multiplier par \(x\).
fe(x,n) := {
local j, r;
r := x;
for(j:=0;j<16;j++) r := irem(r^2,n);
r := irem(r*x,n);
}
Pour \(f_d\), on se contente de la puissance rapide générique (voir question suivante).
On pose p:=nextprime(2^255) et q:=nextprime(2^256).
En utilisant les fonctions asc et char, ainsi que les fonctions de
représentation des nombres en base \(b=256\), codez un message sous forme d’un
entier inférieur à \(n=pq\), puis envoyez le chiffré par RSA à votre voisin
et déchiffrez le sien
On met en place le système RSA
p := nextprime(2^255); q := nextprime(2^256); n := p*q; phin := (p-1)*(q-1); e := 2^16+1; d := ( (e mod phi)^-1 ) % 0 fe(m) := powermod(m, e, n); fd(m) := powermod(m, d, n);
Cornélius peut chiffrer le message suivant
M := asc("Zephir va trahir Babar");
m := evalue_base(M,256);
c := fe(m)
et Céleste le déchiffrer
m := fd(c);
M := ecriture(m, 256)
char(M);
Pour quelles raisons est-il d’usage de prendre cette valeur de \(e\) ?
\(e\) est un nombre de Fermat (d’où une exponentiation rapide très simple) et le plus grand (connu) qui soit premier (ce qui diminue les chances qu’il soit non premier à \(\varphi(n)\)).
A l’aide de la commande factor, déterminer un polynôme \(P\in\F_{101}[X]\) irréductible de degré 4.
On cherche un polynôme au hasard, et on essaie de le factoriser.
p := 101;
P := ( x^4+rand(p)*x+rand(p) ) % p;
factor(P);
On note \(K\) le corps fini \(\F_{101}[X]/(P)\). Quel est le cardinal de \(K^\ast\) ? Quel est le cardinal de \(\{u^2, u\in K^\ast\}\) ?
On pose \(p=101\) : le cardinal de \(K\) vaut \(p^4\), donc \(\card{ K^\ast}=p^4-1\). Les carrés sont l’image de l’application carré, qui a pour noyau \(\pm1\), on en a donc \(\frac{p^4-1}2\).
En déduire un test, à l’aide d’un calcul de puissance rapide, déterminant si la classe de \(x\) est un carré dans \(K\).
Les carrés forment un sous-groupe, donc d’après le théorème de Lagrange tout carré \(c\) vérifie \(c^{\frac{p^4-1}2}=1\). Réciproquement, cette équation est polynomiale et n’admet pas plus de solutions que son degré, donc elle caractérise exactement les carrés. Pour les \(x\) non-carrés, on a \(r=x^{\frac{p^4-1}2}=-1\) (car \(r^2=1\) et \(r\neq 1\)).
carremodP(x) := {
return powermod(x,(p^4-1)/2,P)==1;
}
Note
Complexité des opérations élémentaires