É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 doit obtenir
solve_chinese([1,2,3,4], [11,13,17,19])
É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$. 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 F(n):
return 2**(2**n)+1
for n in range(9): print F(n)
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.
miller_rabin(F(8))
miller_rabin(2**117-1)