An Implementation Of GNFS Algorithms For Discrete Logarithms In GF(p)

The public key cryptosystem are based on the difficulty of computing some mathematical problems.As the first practical public key cryptosystem to be published, the Diffie-Hellman key exchange algorithm,is based on the assumption that discrete logarithms are hard to compute.Discrete logarithms have a long history in number theory.Initially they were used primarily computing in finite fields.The main impetus for the intensive current interest in discrete log came from the invention of the Diffie-Hellman algorithm The discrete logarithms have been achieved substantial advances in the last three decades from the appearance of the Diffie-Hellman algorithm.There are different algorithms for computing discrete logarithms in different cyclic groups.By the time complexity,Algorithms can be classified to general algorithms and subexponential algorithms.The Shanks"baby-steps,gaint-steps", Pollard rho and Pollard lambda belong to general methods.The basic processing for these algorithm requires total about o(n_g^1/2) steps.The subexponential algorithms come from COS in 1986 by Coppersmith.GNFS is most efficent Algorithms in subexponential algorithms.The algorithm to compute discrete logarithms include 3 steps:1 Contructure the linear system of the factor base by sieving;2 Getting the log value of the factor base by solving these equations;3 Computing the individual logarithm.The best algorithm to compute discrete logarithms in GNFS is "Jour's and Lericer's GNFS" at present.Its main advantage is,for a fixed modulus p,to compute individual logarithms only need to solvie a very large linear system for each logarithm once.GNFS Algorithms to compute discrete logarithms involve deeply profound mathematical theory,Such as abstract algebra,algebraic number theory,and computational algebra etc.The implementation of the GNFS of Joux and Lercier is also a very complex project,it includes many works,such as factoring,sieving, solving linear system etc.In this paper,it first introduces the principle and the steps of the implemention of the GNFS of Joux and Lercier in details.Then,It discusses this mainly by computing the discrete log of a 70 decimal digits modulus p=[10⁷⁰π]+25507 =31415926535897932384626433832795028 84197169399375105820974944592333323The implementation is compiled with C language and assemble language on Dual Core AMD Opteron(tm) Processor 875,.and run out the resulat of the example in 813 minutes.