User

[Actualité] Algorithmes probabilistes et nombres premiers : le test de primalité de Fermat

Noter ce billet

par

User

, 06/05/2024 à 13h58 (4940 Affichages)

I. Introduction

On s'intéresse maintenant aux algorithmes probabilistes et plus précisément au test de primalité de Fermat :

On va d'abord définir ce qu'est un test de primalité probabiliste en donnant comme exemple le test de primalité de Fermat. Ensuite, on va décrire cet algorithme et montrer comment le rendre plus fiable.

Enfin, on va implémenter ce test en Python afin de le comparer au test de primalité classique en termes de rapidité d'exécution.

II. Algorithme probabiliste

D'après Wikipedia, un algorithme probabiliste, ou algorithme randomisé, est un algorithme qui utilise une source de hasard. Plus précisément le déroulement de l’algorithme fait appel à des données tirées au hasard. Par exemple à un certain point de l’exécution, on tire un bit 0 ou 1, selon la loi uniforme et si le résultat est 0, on fait une certaine action A et si c'est 1, on fait une autre action.

III. Test de primalité

Un test de primalité est un algorithme permettant de savoir si un nombre entier est premier.

III-A. Méthode naïve

Le test le plus simple est celui des divisions successives : pour tester N, on vérifie s’il est divisible par l’un des entiers compris au sens large entre 2 et N-1. Si la réponse est négative, alors N est premier, sinon il est composé.

On peut améliorer les performances de cet algorithme en testant tous les entiers entre 2 et √𝑁, puisque si N = pq, alors soit p≤√𝑁, soit q≤√𝑁.

III-B. Tests probabilistes

Toujours d'après Wikipedia, les tests probabilistes ne sont pas des tests de primalité au sens strict (ils font partie des méthodes de Monte-Carlo) : ils ne permettent pas de garantir de façon certaine qu’un nombre est premier, mais leur faible coût en temps de calcul en font d’excellents candidats pour les applications en cryptologie qui souvent dépend de façon critique de grands nombres premiers et accepte un taux d’erreur pourvu qu’il soit très faible : on les appelle des nombres premiers industriels. L’idée de base du test de la primalité d’un nombre N est la suivante :

Tirer aléatoirement un nombre a.
Vérifier une certaine identité qui fait intervenir a ainsi que le nombre donné N et qui est vraie si le nombre N est premier. Si l’identité n’est pas satisfaite, alors N est nécessairement composé et le test s’arrête ; dans ce cas, a est appelé un témoin du test.
Répéter l’étape 1 jusqu’à ce que la marge d’incertitude souhaitée soit atteinte.

Après plusieurs itérations, si N n’est pas reconnu comme un nombre composé, il est déclaré probablement premier.

Étant donné un test, il peut exister certains nombres composés qui sont déclarés « probablement premier » quel que soit le témoin. De tels nombres résistant au test sont appelés nombres pseudopremiers pour ce test.

III-B-1. Test de primalité de Fermat

En algorithmique, le test de primalité de Fermat est un test de primalité probabiliste basé sur le petit théorème de Fermat. Il est de type Monte-Carlo : s'il détecte qu'un nombre est composé alors il a raison ; en revanche, il peut se tromper s'il prétend que le nombre est premier.

Nom : test_fermat.png
Affichages : 2188
Taille : 9,2 Ko

Petit théorème de Fermat :

Si p est un nombre premier alors pour tout 1 ≤ a < p, alors a^p-1 ≡ 1 (mod p) ou encore a^p-1 mod p = 1.

L'opération a^p-1 mod p représente une exponentiation modulaire. Son calcul est considéré comme facile, même lorsque les nombres en jeu sont énormes.

Si maintenant on fixe a, il se peut en fait que a^p-1 ≡ 1 (mod p) sans que p ne soit premier ; un tel nombre a est nécessairement premier avec p. Le nombre p est dit alors pseudo-premier de Fermat de base a.

Le test de primalité de Fermat repose sur l'idée suivante : si p est composé, alors il est peu probable que a^p–1 soit congru à 1 modulo p pour une valeur arbitraire de a, autrement dit il est peu probable qu'on ait a^p-1 mod p = 1.

Voici un pseudo-code pour le test de Fermat :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
Fonction testPrimaliteFermat(N)
    choisir un entier positif a < N au hasard   

    Si a^N-1 ≡ 1 mod N alors
        renvoyer oui (N est probablement premier)
    Sinon
        renvoyer non (N est composé)
    Fin Si 

Fin Fonction

On peut maintenant imaginer que si le test est positif pour plusieurs entiers positifs a₁, ..., a_k < N choisis au hasard, on augmente les chances qu'il soit juste.

On sait en fait que si N n'est pas un nombre de Carmichael, alors on peut choisir k entiers positifs a₁, ..., a_k < N au hasard, et la probabilité que le test de Fermat soit positif pour les k entiers si N est composé est inférieure à 1/2^k.

On obtient ainsi le pseudo-code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Fonction testPrimaliteFermatItere(N)
     
    pour i de 1 jusqu'à k

	choisir un entier positif a_i < N au hasard

        Si a_i^N-1 ≢ 1 mod N alors
            renvoyer non (N est composé : sortie de la fonction)
        Fin Si 

    Fin Pour

    renvoyer oui (N est probablement premier : sortie de la fonction)

Fin fonction

Le test de primalité de Fermat est le test probabiliste le plus simple. Le test de primalité de Miller-Rabin et le test de primalité de Solovay-Strassen sont des variantes plus sophistiquées qui détectent tous les composés.

IV. Implémentation en Python

IV-A. Test de primalité : méthode naïve

La fonction naïve vérifie si N est divisible par l’un des entiers compris entre 2 et √𝑁. Si la réponse est négative, alors N est premier, sinon il est composé :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def test_primalite(N):
    # fonction permettant de tester si N est premier en utilisant la méthode naïve
    # N : nombre entier à tester
 
    # détermination du dernier entier m à tester comme diviseur de N : m est égal à la partie entière de √𝑁
    m = int(math.sqrt(N))
 
    # parcours des entiers : 2 -> m
    for i in range(2, m+1):
        # Si i divise N
        if N % i == 0:
            # N possède un diviseur donc n'est pas premier
            # renvoie le tuple : (False, i-1) => (est_premier, nbre_iterations)
            return (False, i-1)
 
    # N n'a pas de diviseur autre que 1 et lui-même, il est donc premier.
    # renvoie le tuple : (True, m-1) => (est_premier, nbre_iterations)
    return (True, m-1)

Elle renvoie donc un tuple contenant le résultat du test (True/False) et le nombre de divisions nécessaires pour aboutir.

Testons maintenant notre fonction pour un grand nombre entier N :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
print("Test de primalité classique :\n")
 
# valeur de N
N = 99999980021
 
print("N = " + str(N))
 
print()
 
# Teste si le nombre entier N est premier par la méthode naïve.
est_premier, nbre_iterations = test_primalite(N)
 
# Affiche le résultat
if est_premier:
    print("Résultat du test : {0} est premier.".format(N))
else:
    print("Résultat du test : {0} est composé.".format(N))
 
print("------------------------------------------")
print("Nombre de division(s) : " + str(nbre_iterations))

Résultat du test :

Test de primalité classique :

N = 99999980021

Résultat du test : 99999980021 est premier.
----------------------------------------------------
Nombre de division(s) : 316226

On constate dans ce cas que le test de primalité classique utilise beaucoup de divisions successives avant d'aboutir à un résultat (de l'ordre de √𝑁 dans le pire des cas).

IV-B. Test de primalité de Fermat : test probabiliste

On sait que si N est premier, alors il est très probable que pour 1 ≤ a < N on ait a^N-1 mod N = 1.

On peut alors écrire la fonction en Python qui permet d'effectuer ce test :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def test_primalite_fermat(N):
    # fonction permettant de tester si N est premier avec un entier positif a < N choisi au hasard
    # N : nombre entier à tester
 
    # séquence de nombres entiers compris entre 2 et N-1 : 2 -> N-1
    nombres_entiers = range(2, N)
 
    # choix au hasard de l'entier positif a < N
    a = random.choice(nombres_entiers)
 
    # Si a^(N-1) mod N = 1 : a^(N-1) est congru à 1 modulo N
    if pow(a, N-1, N) == 1:
        # N est probablement premier
        return True
 
    else: # sinon : N est composé
        return False

En Python, l'opération pow(a, N-1, N) permet donc de réaliser l'exponentiation modulaire a^N-1 mod N.

On souhaite maintenant itérer le test plusieurs fois pour avoir un résultat plus fiable dans le cas où il est toujours positif.

On peut alors écrire notre fonction permettant de tester si un nombre entier est premier avec un paramètre de fiabilité k passé en argument :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def test_primalite_fermat_iter(N, k, n=None):
    # fonction permettant de tester si N est premier en itérant au plus k fois le test de Fermat
    # N : nombre entier à tester
    # k : nombre maxi. d'itérations ou d'entiers positifs a1, ... ak < N choisis au hasard
    # n : valeur maxi de la séquence de nombre entiers inférieurs à N : 2 -> n, si n est omis ou si n ≥ N, alors n = N-1
 
    # si l'argument n est omis ou si n ≥ N
    if (not n) or (n >= N) : n = N-1
 
    # séquence de nombres entiers compris entre 2 et n : 2 -> n, avec n < N
    nombres_entiers = range(2, n+1)
 
    # on itère k fois le test de Fermat : 0 -> k-1
    for i in range(k):
 
        # choix de l'entier positif ai < N au hasard
        ai = random.choice(nombres_entiers)
 
        # Si ai^(N-1) mod N ≠ 1 : ai^(N-1) n'est pas congru à 1 modulo N
        #if not test_primalite_fermat(N):
        if pow(ai, N-1, N) != 1:
            # N n'est pas premier :
            # renvoie le tuple : (False, i+1) => (est_premier, nbre_iterations)
            return (False, i+1)
 
    # N est probablement premier
    # renvoie le tuple : (True, k) => (est_premier, nbre_iterations)
    return (True, k)

Elle renvoie donc un tuple contenant le résultat du test (True/False) et le nombre d'itérations nécessaires pour aboutir.

L'argument n permet de borner la séquence de nombre entiers sur lesquels on effectue le tirage : 2, 3, ..., n < N. On peut ainsi économiser de la mémoire et augmenter la rapidité d'exécution de la fonction en diminuant le nombre de choix possibles lors de chaque tirage.

Testons la maintenant avec notre grand nombre entier :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
print("Test de primalité de Fermat :\n")
 
# valeur de N
N = 99999980021
 
print("N = " + str(N))
 
# paramètre de fiabilité k : nombres d'entiers positifs a1, ..., ak < N choisis au hasard 
k = 20
 
print("N = " + str(N)) 
print("k = " + str(k))
 
print()
 
# test de primalité de Fermat pour un nombre entier N et au plus k itérations
est_premier, nbre_iterations = test_primalite_fermat_iter(N, k, n=1000)
 
# Affiche le résultat
if est_premier: # si N est premier
    print("Résultat du test : {0} est probablement premier.".format(N))
else: # sinon
    print("Résultat du test : {0} est composé.".format(N))
 
print("------------------------------------------------------------------------------------------")
print("Nombre de tirage(s) : " + str(nbre_iterations))
print("Nombre d'exponentiation(s) modulaire(s) : " + str(nbre_iterations))
if est_premier:
    # risque d'erreur maxi si ce n'est pas un nombre de Carmichael : t = 1/(2^k)
    t = pow(2,-k)
    print("Risque d'erreur si N n'est pas un nombre de Carmichael inférieur à : " + str(t))

Résultat du test :

Test de primalité de Fermat :

N = 99999980021
k = 20

Résultat du test : 99999980021 est probablement premier.
---------------------------------------------------------------------------------------------------------
Nombre de tirage(s) : 20
Nombre d'exponentiation(s) modulaire(s) : 20
Risque d'erreur si N n'est pas un nombre de Carmichael inférieur à : 9.5367431640625e-07

On constate que le test de Fermat nécessite beaucoup moins d'opérations que le test classique pour ce grand nombre premier (k tirages et k exponentiations modulaires dans le pire des cas, c'est à dire si N est premier, contre environ √𝑁 divisions successives pour la version naïve). Comme mentionné précédemment, il devrait donc être en moyenne plus rapide à l'exécution pour de grands nombres entiers.

IV-C. Comparaison des temps d'exécution des deux fonctions

Pour vérifier notre hypothèse, on souhaite maintenant mesurer le temps mis par chacune des fonctions pour effectuer une série de tests de primalité sur de grands nombres entiers :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
print("Mesure du temps d'exécution des deux fonctions de test sur une série de 20 000 nombres entiers ..\n")
 
# initialisation des compteurs de tests positifs
cpt1 = 0; cpt2 = 0
 
print("Version n°1 - Test de primalité classique :\n")
 
# heure Unix de début (exprimée en secondes)
start = time.time()
 
# parcours des 20 0000 nombres entiers : 99999980000 -> 99999999999
for N in range(99999980000, 100000000000):
 
    # test classique pour N
    est_premier, nbre_iterations = test_primalite(N)
 
    if est_premier: # si le test est positif
        cpt1+=1 # incrémentation du compteur
 
# heure Unix de fin (exprimée en secondes)
end = time.time()
 
# Affiche la durée d'exécution.
print(f"Durée d'exécution : {end - start} sec.\n")
 
 
print("Version n°2 - Test de primalité de Fermat\n")
 
# heure Unix de début (exprimée en secondes)
start = time.time()
 
# parcours des 20 0000 nombres entiers : 99999980000 -> 99999999999
for N in range(99999980000, 100000000000):
 
    # test de primalité de Fermat pour N et k
    est_premier, nbre_iterations = test_primalite_fermat_iter(N, k=10, n=1000)
 
    if est_premier: # si le test est positif
        cpt2+=1 # incrémentation du compteur
 
# heure Unix de fin (exprimée en secondes)
end = time.time()
 
# Affiche la durée d'exécution.
print(f"Durée d'exécution : {end - start} sec.")
print("Taux d'erreur : " + str((cpt2-cpt1)/20000))

Résultat :

Mesure du temps d'exécution des deux fonctions de test sur une série de 20 000 nombres entiers ..

Version n°1 - Test de primalité classique :

Durée d'exécution : 88.61510872840881 sec.

Version n°2 - Test de primalité de Fermat :

Durée d'exécution : 0.6873371601104736 sec.
Taux d'erreur : 0.0

On constate que le test de Fermat est environ 130 fois plus rapide que le test classique sur cette série de grands nombres.

Ce type d'algorithme est d'ailleurs très utilisé en cryptologie, domaine dans lequel on a souvent besoin de générer rapidement un grand nombre premier en acceptant un taux d'erreur infime.

IV-D. Module complet

On donne pour finir le code complet du module contenant les fonctions de test de primalité :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
import math
import random
import time
 
def test_primalite(N):
    # fonction permettant de tester si N est premier en utilisant la méthode naïve
    # N : nombre entier à tester
 
    # détermination du dernier entier m à tester comme diviseur de N : m est égal à la partie entière de √𝑁
    m = int(math.sqrt(N))
 
    # parcours des entiers : 2 -> m
    for i in range(2, m+1):
        # Si i divise N
        if N % i == 0:
            # N possède un diviseur donc n'est pas premier
            # renvoie le tuple : (False, i-1) => (est_premier, nbre_iterations)
            return (False, i-1)
 
    # N n'a pas de diviseur autre que 1 et lui-même, il est donc premier.
    # renvoie le tuple : (True, m-1) => (est_premier, nbre_iterations)
    return (True, m-1)
 
 
def test_primalite_fermat(N):
    # fonction permettant de tester si N est premier avec un entier positif a < N choisi au hasard
    # N : nombre entier à tester
 
    # séquence de nombres entiers compris entre 2 et N-1 : 2 -> N-1
    nombres_entiers = range(2, N)
 
    # choix de l'entier positif a < N au hasard
    a = random.choice(nombres_entiers)
 
    # Si a^(N-1) mod N = 1 : a^(N-1) est congru à 1 modulo N
    if pow(a, N-1, N) == 1:
        # N est probablement premier
        return True
 
    else: # sinon : N est composé
        return False
 
 
def test_primalite_fermat_iter(N, k, n=None):
    # fonction permettant de tester si N est premier en itérant au plus k fois le test de Fermat
    # N : nombre entier à tester
    # k : nombre maxi. d'itérations ou d'entiers positifs a1, ... ak < N choisis au hasard
    # n : valeur maxi de la séquence de nombre entiers inférieurs à N : 2 -> n, si n est omis ou si n ≥ N, alors n = N-1
 
    # si l'argument n est omis ou si n ≥ N
    if (not n) or (n >= N) : n = N-1
 
    # séquence de nombres entiers compris entre 2 et n : 2 -> n, avec n < N
    nombres_entiers = range(2, n+1)
 
    # on itère k fois le test de Fermat : 0 -> k-1
    for i in range(k):
 
        # choix de l'entier positif ai < N au hasard
        ai = random.choice(nombres_entiers)
 
        # Si ai^(N-1) mod N ≠ 1 : ai^(N-1) n'est pas congru à 1 modulo N
        #if not test_primalite_fermat(N):
        if pow(ai, N-1, N) != 1:
            # N n'est pas premier :
            # renvoie le tuple : (False, i+1) => (est_premier, nbre_iterations)
            return (False, i+1)
 
    # N est probablement premier
    # renvoie le tuple : (True, k) => (est_premier, nbre_iterations)
    return (True, k) 
 
 
print("I. Test de primalité..\n")
 
print("I-A. Version n°1 - Méthode naïve :\n")
 
# valeur de N
N = 99999980021 # 99999980051, 99999980053, 99999980057, 99999980089, 99999980099, 99999980123, 99999980147, 99999980159, 99999980167
 
print("N = " + str(N))
 
print()
 
# Teste si le nombre entier N est premier par la méthode naïve.
est_premier, nbre_iterations = test_primalite(N)
 
# Affiche le résultat
if est_premier:
    print("Résultat du test : {0} est premier.".format(N))
else:
    print("Résultat du test : {0} est composé.".format(N))
 
print("--------------------------------------------")
print("Nombre de division(s) : " + str(nbre_iterations))
 
print();print()
 
print("I-B. Version n°2 - Test probabiliste de Fermat :\n")
 
# paramètre de fiabilité k : nombres d'entiers positifs a1, ..., ak < N choisis au hasard
k = 20
 
print("N = " + str(N)) 
print("k = " + str(k))
 
print()
 
# test de primalité de Fermat pour un nombre entier N et au plus k itérations
est_premier, nbre_iterations = test_primalite_fermat_iter(N, k, n=1000)
 
# Affiche le résultat
if est_premier: # si N est premier
    print("Résultat du test : {0} est probablement premier.".format(N))
else: # sinon
    print("Résultat du test : {0} est composé.".format(N))
 
print("------------------------------------------------------------------------------------------")
print("Nombre de tirage(s) : " + str(nbre_iterations))
print("Nombre d'exponentiation(s) modulaire(s) : " + str(nbre_iterations))
if est_premier:
    # risque d'erreur maxi si ce n'est pas un nombre de Carmichael : t = 1/(2^k)
    t = pow(2,-k)
    print("Risque d'erreur si N n'est pas un nombre de Carmichael inférieur à : " + str(t))
 
print(); print()
 
print("II. Mesure du temps d'exécution des deux fonctions de test sur une série de 20 000 nombres entiers ..\n")
 
# initialisation des compteurs de tests positifs
cpt1 = 0; cpt2 = 0
 
print("Version n°1 - Test de primalité classique :\n")
 
# heure Unix de début (exprimée en secondes)
start = time.time()
 
# parcours des 20 0000 nombres entiers : 99999980000 -> 99999999999
for N in range(99999980000, 100000000000):
 
    # test classique pour N
    est_premier, nbre_iterations = test_primalite(N)
 
    if est_premier: # si le test est positif
        cpt1+=1 # incrémentation du compteur
 
# heure Unix de fin (exprimée en secondes)
end = time.time()
 
# Affiche la durée d'exécution.
print(f"Durée d'exécution : {end - start} sec.\n")
 
 
print("Version n°2 - Test de primalité de Fermat :\n")
 
# heure Unix de début (exprimée en secondes)
start = time.time()
 
# parcours des 20 0000 nombres entiers : 99999980000 -> 99999999999
for N in range(99999980000, 100000000000):
 
    # test de primalité de Fermat pour N et k
    est_premier, nbre_iterations = test_primalite_fermat_iter(N, k=10, n=1000)
 
    if est_premier: # si le test est positif
        cpt2+=1 # incrémentation du compteur
 
# heure Unix de fin (exprimée en secondes)
end = time.time()
 
# Affiche la durée d'exécution.
print(f"Durée d'exécution : {end - start} sec.")
 
print("Taux d'erreur : " + str((cpt2-cpt1)/20000))