Factorisation par courbes elliptiques
guillitte
1,791 views
Bonjour!
Ce programme présente la factorisation par la méthode de Lenstra qui utilise des courbes elliptiques sur les entiers modulaires.
Cette version travaille en coordonnées projectives afin d'éviter le recours aux inverses modulaires, lourds à calculer.
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
from time import time
from random import randint
from math import gcd
# test de Miller pour un témoin a
# Retourne faux si n est composé et vrai si n est probablement premier
# d et r doivent vérifier n = 2^r * d + 1 avec d impair
def millerTest(a,d,n,r):
x = pow(a, d, n) # Calcule a^d % n
if (x == 1 or x == n-1):
return True
for _ in range(r):
x = (x * x) % n
if (x == 1):
return False
if (x == n-1):
return True
return False
# Test de primalité de Miller Rabin
# Si faux alors n est composé et si vrai alors n est probablement premier
# k determine le niveau de certitude : P(erreur) < 1/4**k
def isPrime(n, k=25):
if (n <= 1 or n == 4):
return False
if (n <= 5):
return True
# Trouver d et r tels que n = 2^r * d + 1 avec d impair
d = n - 1
r = 0
while (d&1 == 0):
d >>= 1
r += 1
# Effectuer k tests de Miller
for i in range(k):
a = randint(2,n-2)
if (not millerTest(a, d, n, r)):
return False
return True
# Premier suivant n
Create your playground on Tech.io
This playground was created on Tech.io, our hands-on, knowledge-sharing platform for developers.