Factorisation ECM version Montgomery
guillitte
1,681 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 utilise des courbes de Montgomery, pour lesquelles les opérations arithmétiques peuvent être optimisées plus efficacement. Les calculs n'utilisent que les coordonées x et z du point projectif.
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
def millerTest(a,d,n,r):
# 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
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
def isPrime(n, k=25):
# 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
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
def nextPrime(n):
# premier suivant n
while not isPrime(n):
n += 1
Create your playground on Tech.io
This playground was created on Tech.io, our hands-on, knowledge-sharing platform for developers.