Écrivez une fonction solve_chinese(xx, mm) qui résout le système de congruences $$ \left\{ \begin{matrix} x &\equiv& x_1& [m_1] \\ x &\equiv& x_2& [m_2]\\ \vdots & \cdots &\vdots \\ x&\equiv &x_n&[m_n]\end{matrix}\right.$$
xx est la liste des seconds membres $x_i$ et mm celle des modules $m_i$. La fonction renverra l'unique solution $x$ dans l'intervalle $[0,m-1]$. On suppose que les $m_i$ sont deux à deux premiers entre eux.
# On reprend les fonctions du TD 6
def xgcd(a,b):
if b==0:
return (a,1,0)
else:
d,u,v = xgcd(b,a % b)
return (d,v,u-(a//b)*v)
def inversemod(a, n):
d, x, y = xgcd(a, n)
assert d == 1, "a doit etre premier avec n."
return x%n
# Algorithme vu en cours
from functools import reduce
def solve_chinese(yy,mm):
assert len(yy) == len(mm), "Les arguments doivent etre de meme longueur"
k = len(yy); m = reduce(lambda x,y:x*y, mm); x=0
for i in range(k):
u = reduce(lambda x,y:x*y, [mm[j] for j in range(k) if j!=i])
v = inversemod(u,mm[i])
x = (x + yy[i]*v*u) % m
return x
solve_chinese([1,2,3,4], [11,13,17,19])
solve_chinese([3,4,5],[17,11,6])
Écrivez une fonction powermod(a,m,n) qui calcule $a^m\mod n$ (la fonction pow de Python le fait aussi, mais on aura besoin de ce code pour la suite), et programmez le test de Fermat :
un entier $n$ est dit pseudo-premier de Fermat pour la base $a$ si $a^{n-1}\equiv 1\,[n]$.
Écrivez une fonction test_fermat(n, tests=5) qui va essayer tests bases $a$ au hasard et renvoie True
si on obtient 1 pour chacune (et False sinon).
Voir aussi ici.
Les nombres de Fermat sont les $F_n = 2^{(2^n)}+1$. Ainsi, $F_0=3, F_1= 5, F_2= 17, F_3= 257, F_4= 65537, F_5= 4294967297\ldots$. Ils sont premiers pour $n\le 4$. Fermat pensait qu'il étaient premiers en général, mais Euler a prouvé que $F_5$ était divisible par 641.
Vérifiez par quelques tests de Fermat pour de petites bases $a=2,3,5,7 ...$ que $F_5,F_6,F_7, F_8$ ne sont pas premiers. Pouvez vous en tester de plus grands ?
def powermod(a,m,n):
res = 1;
while m:
if m&1: res = (res * a) % n
m >>= 1
a = (a *a ) % n
return res
powermod(2,666,2**101-1)
pow(2,666,2**101-1) # la fonction de Python
# Les nombres de Fermat
def F(n):
return 2**(2**n)+1
for n in range(9): print (F(n))
# On vérifie que F(8) n'est pas premier
m = F(8)
for a in [2,3,5,7]: print (powermod(a,m-1,m))
En modifiant le test de Fermat, programmer le test de Miller-Rabin.
Pour cela, on écrit $n-1=2^km$ avec $m$ impair, et on commence par calculer
$b=a^m \mod n$. Si $b=1$, on renvoie True (probablement premier).
Sinon, on calcule les $b^{(2^i)}\mod n$ et la première fois que le résultat vaut 1,
on teste si la valeur précédente était $\equiv -1\mod n$.
Si ce n'est pas le cas, on renvoie False (composé). Si on arrive à $b^{(2^k)}$
sans avoir rencontré de racine carrée non triviale de 1, on renvoie True.
from random import randrange
def test_base(a,n):
m = n-1; k = 0
while not m&1:
k+=1; m >>=1
b = powermod(a,m,n)
if b==1: return True
for i in range(k):
x = b
b = powermod(b,2,n)
if b==1:
if x != n-1: return False
else: return True
return False
def miller_rabin(n, tests=4):
if n in [2,3]: return True
if not n%2: return False
for i in range(tests):
a = randrange(2,n-1)
if not test_base(a,n): return False
return True
miller_rabin(F(8))
miller_rabin(2**117-1)
# Test des nombres de Fermat
for n in range(1,10): print(n,miller_rabin(F(n)))
Les nombres de Mersenne sont les $M_n=2^n-1$. Ils ne peuvent être premiers que si $n$ est lui-même premier, car $$2^{ab}-1=(2^a)^b-1=(2^a-1)(2^{a(b-1)}+2^{a(b-2)}+\cdots +1)$$ mais lorsque $p$ est premier, $M_p$ est souvent premier. Le plus grand nombre premier connu (qui change de temps en temps) est généralement un nombre de Mersenne.
# Une petite liste de nombres (probablement) premiers
pp = [p for p in range(2,500) if miller_rabin(p)]
print(pp)
# Quelques nombres de Mersenne (probablement) premiers
def M(p): return 2**p-1
MM = [p for p in pp if miller_rabin(M(p))]
print(MM)
On voit qu'il n'y en a plus entre $p=127$ et $500$. Est-ce que c'est fini ? Notre résultat est correct, voir la page Wikipedia. On y apprend que le suivant est $M_{521}$. Et ça continue...
M(521)
miller_rabin(M(521))
Pour le moment, ces nombres de Mersenne sont seulement probablement premiers. Leur forme très particulière permet, grace au test de Lucas-Lehmer, de prouver qu'ils sont premiers lorsqu'ils le sont effectivement.