Factorisation ECM version Montgomery

538 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.

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.

Go to tech.io

Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!

JOIN US ON DISCORD

Online Participants

Bonjour!

Factorisation par courbes elliptiques

Descente de gradient (fonction de deux variables)

Apprendre Python dans le secondaire

Contest tools and workflow

Keyboard Shortcuts: