2015/04/06 by Semaev, Igor
#Commutative Algebra (math.AC) #Computational Complexity (cs.CC) #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT)
paper · doi:10.48550/arxiv.1504.01175
A new algorithms for computing discrete logarithms on elliptic curves defined over finite fields is suggested. It is based on a new method to find zeroes of summation polynomials. In binary elliptic curves one is to solve a cubic system of Boolean equations. Under a first fall degree assumption the regularity degree of the system is at most 4. Extensive experimental data which supports the assumption is provided. An heuristic analysis suggests a new asymptotical complexity bound 2c√(nln n), c≈ 1.69 for computing discrete logarithms on an elliptic curve over a field of size 2n. For several binary elliptic curves recommended by FIPS the new method performs better than Pollard's.