3732.sagews

Durant ce TP, nous allons implanter différents tests de primalité et tenter de les comparer. Pour comparer deux tests, le temps utilisé est important, mais aussi la mémoire (est-ce que j'utilise des tableaux immenses, des entiers trop grands ?). En général, les meilleurs algorithmes sont des compromis entre mémoire et temps. Pour chaque question, vous pouvez faire quelques tests rapides à chaque fois : jusqu'à quelle taille d'entiers est-ce qu'on gère en moins d'une minute et sans avoir des bugs de dépassement de mémoire ? (Faites-le sur plus d'un exemple : en général, si on essaie sur un entier pair ou multiple de 3, ça va très vite, mais on explose sur un nombre premier)

Exercice 1 : Échauffement.

Parce qu'il faut bien commencer par le début : Écrivez une fonction ForceBrute(n) qui teste si n est divisible par au moins un entier k<n (quand peut-on s'arrêter ?).

def ForceBrute(n):
    for k in range(sqrt(n)):
        if n%k==0: return False
    return True

False

Exercice 2 : Théorème de Wilson.

On a vu en cours que n est premier si et seulement si (n-1)! = 1 [n]. Construisez un test Wilson(n) qui utilise ce résultat pour tester si n est premier.

def Wilson(n) :
    fact = 1
    for k in range(2,n):
        fact = (fact*k)%n
    return (fact == n-1)

Exercice 3 : Petit théorème de Fermat.

On sait que si p est premier, alors pour tout a, a^p-1=1 [p]. L'inverse n'est pas toujours vrai, mais on peut espérer repérer des nombres non premiers comme ça. Écrivez une fonction Fermat(n) qui :

- prend un entier a au hasard entre 2 et n-1 ;

- teste si a^n-1=1 [n] ;

- renvoie True si n est potentiellement premier, False sinon.

Pour la première partie, on pourra utiliser randint(a,b) qui renvoie un entier entre a et b. 

def Fermat(n):
    a = randint(2,n-1)
    res = 1
    for k in range(n-1):
        res = res*a%n
    return (res == 1)

Exercice 4 : Exponentiation rapide.

On veut accélérer l'algorithme précédent (j'espère que vous n'avez pas fait a**(n-1) ?) en étant plus efficace sur le calcul de la puissance. Écrire une fonction ExpoRapide(a,k,n) qui calcule a^k [n] en distinguant les cas :

- Si k est pair, on fait a^k = a^k/2  * a^k/2;

- Si k est impair, on fait a^k = a * a^(k-1)/2 * a^(k-1)/2

On peut par exemple utiliser la récursion en appelant la fonction qu'on est en train d'écrire (sans oublier de faire attention à ce qui se passe pour k=1).

def ExpoRapide(a,k,n):
    if k==1: return a%n
    if k%2==0:
        b = ExpoRapide(a,k/2,n)
        return (b*b)%n
    b = ExpoRapide(a,(k-1)/2,n)
    return a*(b*b)%n

Exercice 5 : Démarche scientifique.

On aimerait avoir une idée du taux d'erreur de l'algorithme précédent (nombres non premiers pour lesquels la réponse est True), par exemple pour les entiers à 5 chiffres. On peut tester sur tous les nombres de 1000 à 9999...(non conseillé), ou bien en prendre quelques centaines au hasard. Écrivez une fonction TestFermat() qui itère cette opération jusqu'à ce qu'on ait atteint 10 erreurs (environ 2 minutes). Quel est la probabilité de réussite du test ?

def TestFermat():
    compteur, erreurs = 0,0
    while erreurs<10:
        compteur +=1
        n = randint(1000,9999)
        if Fermat(n) != Wilson(n):
            erreurs +=1
    return (erreurs/compteur)

10/2851

Exercice 6 :

Plutôt que de prendre la valeur de a au hasard, on peut prendre a=2. Quel serait l'interêt en termes de vitesse ? Écrivez le programme Fermat2(n), puis testez sa probabilité d'erreur sur toutes les valeurs de 1 à 10000.

def Fermat2(n):
    res = 1
    for k in range(n-1):
        res = 2*res%n
    return (res == 1)

def TestFermat2():
    compteur, erreurs = 0,0
    while erreurs<10:
        compteur +=1
        n = randint(1000,9999)
        if Fermat2(n) != Wilson(n):
            erreurs +=1
    return (erreurs/compteur)

Exercice 7 : Notez que sur une entrée donnée, la réponse du programme précédent n'est pas aléatoire. Comment faire pour en tirer un programme qui ne commette aucune erreur sur les entrées <10000 ?

l = []
for k in range(10000):
    if Fermat2(k) != Wilson(k):
        l.append(k)
l

[0, 1, 2, 341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911]

def FermatExact(n):
    if n in l: return False
    else : return Fermat2(n)

Exercice 8 : factorisation de Pollard p-1

On suppose n=pq, avec p,q premiers. On se donne B une borne assez grande et 1<g<n un nombre quelconque 'testeur'. On suppose que tous les facteurs de p-1 sont plus petits que B, de telle sorte que (p-1) divise B!. On  considère alors a=g^(B!) mod n, qui doit être congru à 1 modulo p, par le petit théorème de Fermat. Ainsi p divise (a-1) et n, donc le pgcd(a-1,n), s'il est différent de 1 et n, est un diviseur non trivial de n. On a factorisé n.  

Écrire une procedure PollardTest(n,B,g) qui effectue l'algorithme (p-1) de Pollard pour le nombre testeur g.  Puis écrire une procedure Pollard(n,B) qui  effectue les tests de Pollard avec tous les testeurs g tels que 1<g<n et s'arrête si elle trouve un facteur de n ou si tous les g possibles ont été testés.  Appliquer cette procédure sur n = 139*197 et retrouver p,q.

Exercice 9 (*) : "Un groupe est un ensemble muni d'une loi"

Si vous êtes arrivés là, vous avez davantage besoin de faire des maths que de l'info. On veut compter le nombre de groupes finis non isomporhes de taille n. Autrement dit, il s'agit du nombre de choix de lois de groupe différentes sur [a1,...,an] telles que les groupes obtenus ne sont pas isomorphes. Regarder à la main les cas 3 et 4. Puis, faites la version facile en testant toutes les opérations possibles puis en vérifiant que c'est une loi, et ensuite en testant tous les isomorphismes possibles. Enfin, tentez d'améliorer l'algorithme en évitant les opérations inutiles.