L3 Mathématiques pour l'informatique 4 - TD 7

Restes chinois.

É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.

In [1]:
from TD7 import *
solve_chinese([1,2,3,4], [11,13,17,19])
Out[1]:
41823

Exponentiation modulaire.

É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). 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 ?

In [2]:
def F(n):
    return 2**(2**n)+1

for n in range(9): print F(n)
3
5
17
257
65537
4294967297
18446744073709551617
340282366920938463463374607431768211457
115792089237316195423570985008687907853269984665640564039457584007913129639937

In [3]:
m = F(8)
for a in [2,3,5,7]: print powermod(a,m-1,m)
1
113080593127052224644745291961064595403241347689552251078258028018246279223993
63917531333650471651353505715673973878358329190708031798737007023636906166728
42292655872463866595282799088611729949438617670861386191995035462150949680389

Test de Miller-Rabin.

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.

In [4]:
miller_rabin(F(8))
Out[4]:
False
In [5]:
miller_rabin(2**117-1)
Out[5]:
False
In [5]: