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]$.

In [1]:
# On reprend les fonctions du TD 6
def xgcd(a, b):
    if a == 0 and b == 0: return (0, 0, 1)
    if a == 0: return (abs(b), 0, b/abs(b))
    if b == 0: return (abs(a), a/abs(a), 0)
    x_sign = 1; y_sign = 1
    if a < 0: a = -a; x_sign = -1
    if b < 0: b = -b; y_sign = -1
    x = 1; y = 0; r = 0; s = 1
    while b != 0:
        (c, q) = (a%b, a/b)
        (a, b, r, s, x, y) = (b, c, x-q*r, y-q*s, r, s)
    return (a, x*x_sign, y*y_sign)

def inversemod(a, n):
    g, x, y = xgcd(a, n)
    if g != 1:
        raise ZeroDivisionError, (a,n)
    assert g == 1, "a doir etre premier avec n."
    return x%n
def solve_chinese(yy,mm):
    assert len(yy) == len(mm), "Arguments must have same length."
    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])
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 powermod(a,m,n):
    res = 1; x = a
    while m:
        if m%2:  res = (res * x) % n
        m /= 2
        x = (x*x) % n
    return res   
In [3]:
powermod(2,65536,65537)
Out[3]:
1
In [4]:
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 [5]:
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 [6]:
from random import randrange

def test_base(a,n):
    m = n-1; k = 0
    while not m%2:
        k+=1; m/=2
    b = powermod(a,m,n)
    if b==1: return True
    for i in range(k):
        x = b
        b = pow(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
In [7]:
miller_rabin(F(8))
Out[7]:
False
In [8]:
miller_rabin(2**127-1,tests=20)
Out[8]:
True
In [8]: