Seminar
Number Field Sieve over GF(p) of Low Hamming Weight Characteristic

Hold Date 
20110511 09:00～20110511 10:00 


Place 
Seminar Room 6, Faculty of Mathematics building, Ito Campus 


Object person 



Speaker 
Tsuyoshi Takagi, Kyushu University 

Abstract: The security of the digital signature algorithm (DSA) and DiffieHellman key exchange is based on the difficulty of the discrete logarithm problems (DLP) over prime field GF(p), and thus it is important to evaluate the difficulty of DLP over GF(p) for discussing the security of these protocols. The number field sieve (NFS) is asymptotically the fastest algorithm to solve DLP over GF(p). NFS was first proposed by Gordon and then it was improved by Schirokauer and JouxLercier. On the other hand, Schirokauer presented a new variant of NFS, which is particularly efficient for the characteristic p with low weight (p has a signed binary representation of low Hamming weight). In this talk, we compare the running time of the NFS using the polynomials by JouxLercier (JL03) and Schirokauer (Sch06) with respect to low weight primes of 194bit, and up to 259bit. Sch06 is about 4, 8, or 18 times faster than JL03 for 146bit, 192bit, or 259bit, respectively. Our experiment was carried out on two Xeon E5440 CPU using gcc, pthread and GMP.