pyspeedup/algorithms/_indexCalculus.py
def discreteLog(n,a,p,primes):
    '''Uses index calculus to find n=a^m mod p using the list of primes provided.'''
    #break up n using primes provided.
    nList=[]
    temp=n
    for prime in primes:
        while temp%prime==0:
            temp//=prime
            nList.append(prime)
    if temp!=1:
        nList.append(temp)
        #We don't know that the value left is prime,
        #but we can't break it up anymore with the values given.
        primes.append(temp)
    primeEquations=[]
    aPowM,m=1,0
    #While we can't solve for one of the primes.
    while not (len(primeEquations)==len(primes) and sum([sum(x[0:-1]) for x in primeEquations])==len(primes)) and m<p-1:
        curList=[]
        temp=0
        while temp!=1 or m>p:
            aPowM,m=(aPowM*a)%p,m+1
            if m>=p-1:
                return None
            curList=[]
            temp=aPowM
            for prime in primes:
                while temp%prime==0:
                    temp//=prime
                    curList.append(prime)
        primeEquations.append([curList.count(x) for x in primes])
        primeEquations[-1].append(m)
        rowReduce(primeEquations,p-1)
    out=0
    for i in nList:
        out+=primeEquations[primes.index(i)][-1]
        out%=p-1
    return out
Uses index calculus to find n=a^m mod p using the list of primes provided.
Uses index calculus to find n=a^m mod p using the list of primes provided.
Uses index calculus to find n = a^m mod p using the list of primes provided .
def discreteLog(n,a,p,primes):
    nList=[]
    temp=n
    for prime in primes:
        while temp%prime==0:
            temp//=prime
            nList.append(prime)
    if temp!=1:
        nList.append(temp)
        primes.append(temp)
    primeEquations=[]
    aPowM,m=1,0
    while not (len(primeEquations)==len(primes) and sum([sum(x[0:-1]) for x in primeEquations])==len(primes)) and m<p-1:
        curList=[]
        temp=0
        while temp!=1 or m>p:
            aPowM,m=(aPowM*a)%p,m+1
            if m>=p-1:
                return None
            curList=[]
            temp=aPowM
            for prime in primes:
                while temp%prime==0:
                    temp//=prime
                    curList.append(prime)
        primeEquations.append([curList.count(x) for x in primes])
        primeEquations[-1].append(m)
        rowReduce(primeEquations,p-1)
    out=0
    for i in nList:
        out+=primeEquations[primes.index(i)][-1]
        out%=p-1
    return out
def discreteLog ( n , a , p , primes ) : nList = [ ] temp = n for prime in primes : while temp % prime == 0 : temp //= prime nList . append ( prime ) if temp != 1 : nList . append ( temp ) primes . append ( temp ) primeEquations = [ ] aPowM , m = 1 , 0 while not ( len ( primeEquations ) == len ( primes ) and sum ( [ sum ( x [ 0 : - 1 ] ) for x in primeEquations ] ) == len ( primes ) ) and m < p - 1 : curList = [ ] temp = 0 while temp != 1 or m > p : aPowM , m = ( aPowM * a ) % p , m + 1 if m >= p - 1 : return None curList = [ ] temp = aPowM for prime in primes : while temp % prime == 0 : temp //= prime curList . append ( prime ) primeEquations . append ( [ curList . count ( x ) for x in primes ] ) primeEquations [ - 1 ] . append ( m ) rowReduce ( primeEquations , p - 1 ) out = 0 for i in nList : out += primeEquations [ primes . index ( i ) ] [ - 1 ] out %= p - 1 return out
Uses index calculus to find n=a^m mod p using the list of primes provided.
Uses index calculus to find n = a^m mod p using the list of primes provided .
'''Uses index calculus to find n=a^m mod p using the list of primes provided.''' #break up n using primes provided. #We don't know that the value left is prime, #but we can't break it up anymore with the values given. #While we can't solve for one of the primes.
n
a
p
primes