Si l’on scinde un numéro de sécurité sociale au niveau des deux derniers chiffres, il est formé de deux entiers \(m\) et \(n\) de respectivement 13 et 2 décimales.
Vérifiez la validité de votre numéro personnel en calculant \(m+n\bmod 97\).
Déterminer la première puissance de \(13\) qui se termine par \(01012013\).
Programmer le calcul du pgcd de deux entiers \(a\) et \(b\) à l’aide d’une fonction récursive.
Justifier la terminaison de l’algorithme.
pgcd(a,b):= {
if(b==0) return a;
q := idiv(a,b);
r := irem(a,b);
return pgcd(b,r);
}
Écrire une fonction bezout(a,b) qui renvoie la liste [u,v,d] telle
que \(au+bv=d\), où \(d\) est le pgcd de \(a\) et \(b\).
On définit la suite (Q_k) des égalités de divisions successives comme dans la question 3, et on introduit la suite d’égalités
\[(E_k) a*u_k + b*v_k = r_k.\]En considérant le système formé par \(E_{k-1}\), \(E_k\) et \(Q_k\), on déduit \(E_{k+1}\) et le fait que les coefficients satisfont la récurrence
\[ \begin{align}\begin{aligned}u_{k+1} &= u_{k-1} -q_k u_k\\v_{k+1} &= v_{k-1} -q_k v_k\end{aligned}\end{align} \]avec l’initialisation (formée d’égalités triviales \(a=a\) et \(b=b\))
\[u_0 = 1, v_0 = 0, u_1 = 0, v_1 = 1.\]
bezout(a,b):={
local (uk1:=1),(vk1:=0), (rk1:=a);
local (uk:=0), (vk:=1), (rk:=b);
local qk, r;
r:=irem(rk1,rk);
while(r>0) {
qk := iquo(rk1,rk);
uk1, uk := uk, uk1 - qk * uk;
vk1, vk := vk, vk1 - qk * vk;
rk1, rk := rk, r;
r:=irem(rk1,rk);
};
return([uk,vk,rk]);
}:;
Écrire une fonction chinois(x,a,y,b) qui code l’isomorphisme chinois
chinois(x,p,y,q):={
local (b:= bezout(p,q));
return(x*b[1]*q+y*b[0]*p);
}
Déterminer un entier \(x\) tel que
x:=chinois(17,65537,63,3511);
x%65537;
x%3511;
Soit la matrice
En réduisant \(A\) modulo \(2,3,5\) et \(7\), calculer son déterminant.
Le petit théorème de Fermat énonce que si \(p\) est premier, tout entier \(a\) vérifie
On appelle nombres de Carmichael les exceptions à la réciproque de l’énoncé de Fermat, c’est-à-dire les entiers \(n\) non premiers vérifiant
Déterminer le plus petit nombre de Carmichael.
iscarmichael(n):={
local k;
if(isprime(n)) return(0);
for(k:=2;k<n;k++) {
if( powermod(k,n,n) != k ) return(0);
}
return(1);
}:;
iscarmichael(91);
iscarmichael(1729);
premiercarmichael():={
local (n:=3);
while(!iscarmichael(n)) n++;
return(n);
}:;
n:=premiercarmichael();
On donne le critère suivant (Korselt, 1899) : \(n\) est un nombre de Carmichael si et seulement si
Donner la liste des nombres de Carmichael inférieurs à \(10^4\).
korselt(n):={
local k,F;
if(isprime(n)) return(0);
F:=ifactors(n);
for(k:=0;k<length(F);k+=2) {
if(F[k+1]>1) return(0);
if(irem(n-1,F[k]-1)>0) return(0);
}
return(1);
}:;
korselt(561);
korselt(1891);
L:=[]:;
for(n:=3;n<=10000;n++) {
if(korselt(n)) L:=append(L,n);
}:;
L;
Plus généralement (théorème d’Euler), on a \(a^{\phi(n)}\equiv 1\bmod n\) pour tout \(a\in(\Z/n\Z)^\ast\).
Résoudre l’équation \(x^2=1\) dans \(\Z/19\Z\).
Déterminer les racines carrées de \(1\) modulo 2325781.
Sachant que \(75569613259^2=1 \mod 98765432111\), comment peut-on en déduire une factorisation de l’entier 98765432111 ?
Connaître des racines carrées (non triviales) modulo \(n\) est équivalent à connaître une factorisation (non-triviale) de \(n\).
Soit \(p\) un nombre premier congru à 3 modulo 4. Montrer que pour tout entier \(y\), en posant \(x=y^{\frac{p+1}4}\) :
Programmer une fonction squareroots(y,p) qui calcule les racines
de \(y\) modulo \(p\), si elles existent.
Déterminer toutes les racines carrées de 1522756 modulo 2325781.
Soit \(n\) un entier impair, on pose \(n-1=2^km\) avec \(m\) impair. Si \(n\) est premier, alors pour tout entier \(a<n\) on a
Écrire une fonction miller(n,a) qui vérifie que \(n\) passe le test
de Miller pour l’entier \(a\). On ne factorisera pas \(n-1\).
miller(n,a):={
local m,k,b,j;
m:= n-1; k:= 0;
while(irem(m,2)==0) {
m/=2; k+=1;
};
b := powmod(a,m,n);
if(b==1) return(1);
for(j:=0;j<k;j++) {
if(b==n-1) return(1);
b := irem(b^2,n);
};
return(0);
}:;
Combien y a-t-il d’entiers \(a\) permettant de prouver la non primalité de \(n=1729\) ?
nb_faux(n):={
local (k:=0),a;
for(a:=0;a<1729;a++){
if(miller(n,a)) k++;
};
return(k);
}:;
nb_faux(1729);
nb_faux(1891);
On appelle faux témoin de primalité pour l’entier \(n\) non premier tout entier \(a\) qui passe le test de Miller.
Le théorème de Rabin énonce que si \(n\) n’est pas premier, le nombre de faux-témoins est inférieur à \(\frac{\phi(n)}4\).
Au bout de combien d’essais d’entiers \(a\) qui passent le test de Miller peut-on affirmer que \(n\) est premier avec \(99,99\%\) de certitude ?
ntests:=ceil(log(1-99.99/100)/log(1/4));
Écrire un test rabin(n) qui effectue ce test.
rabin(n):={
local k,a;
for(k:=0;k<ntests;k++) {
a := rand(n);
if(miller(n,a)==0) return(0);
}
return(1);
}:;
rabin(1729);
rabin(1891);
rabin(nextprime(1234567890));