| Presentation | 2010-03-04 An Experiment of Number Field Sieve over GF(p) of Low Hamming Weight Characteristic Kenichiro HAYASAKA, Tsuyoshi TAKAGI, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The security of DSA and Diffie-Hellman key exchange is based on the difficulty of the discrete logarithm problems (DLP) over 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 Joux-Lercier. 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 paper, we implement the NFS proposed by Joux-Lercier and Schirokauer, and then we compare the running time of the NFS using the polynomials by Joux-Lercier and Schirokauer with respect to low weight primes of 100 bits or 110 bits. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | discrete logarithm / number field sieve / low hamming weight / polynomial selection |
| Paper # | IT2009-79,ISEC2009-87,WBS2009-58 |
| Date of Issue |
| Conference Information | |
| Committee | ISEC |
|---|---|
| Conference Date | 2010/2/25(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Information Security (ISEC) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | An Experiment of Number Field Sieve over GF(p) of Low Hamming Weight Characteristic |
| Sub Title (in English) | |
| Keyword(1) | discrete logarithm |
| Keyword(2) | number field sieve |
| Keyword(3) | low hamming weight |
| Keyword(4) | polynomial selection |
| 1st Author's Name | Kenichiro HAYASAKA |
| 1st Author's Affiliation | Future University-Hakodate() |
| 2nd Author's Name | Tsuyoshi TAKAGI |
| 2nd Author's Affiliation | Future University-Hakodate |
| Date | 2010-03-04 |
| Paper # | IT2009-79,ISEC2009-87,WBS2009-58 |
| Volume (vol) | vol.109 |
| Number (no) | 445 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |