Paper Abstract and Keywords |
Presentation |
2010-03-04 17:00
An Experiment of Number Field Sieve over GF(p) of Low Hamming Weight Characteristic Kenichiro Hayasaka, Tsuyoshi Takagi (Future Univ. Hakodate) IT2009-79 ISEC2009-87 WBS2009-58 |
Abstract |
(in Japanese) |
(See Japanese page) |
(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 100bits or 110 bits. |
Keyword |
(in Japanese) |
(See Japanese page) |
(in English) |
discrete logarithm / number field sieve / low hamming weight / polynomial selection / / / / |
Reference Info. |
IEICE Tech. Rep., vol. 109, no. 445, ISEC2009-87, pp. 53-60, March 2010. |
Paper # |
ISEC2009-87 |
Date of Issue |
2010-02-25 (IT, ISEC, WBS) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
Download PDF |
IT2009-79 ISEC2009-87 WBS2009-58 |
Conference Information |
Committee |
IT ISEC WBS |
Conference Date |
2010-03-04 - 2010-03-05 |
Place (in Japanese) |
(See Japanese page) |
Place (in English) |
Nagano-Engineering Campus, Shinshu University |
Topics (in Japanese) |
(See Japanese page) |
Topics (in English) |
|
Paper Information |
Registration To |
ISEC |
Conference Code |
2010-03-IT-ISEC-WBS |
Language |
Japanese |
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 |
Keyword(5) |
|
Keyword(6) |
|
Keyword(7) |
|
Keyword(8) |
|
1st Author's Name |
Kenichiro Hayasaka |
1st Author's Affiliation |
Future University-Hakodate (Future Univ. Hakodate) |
2nd Author's Name |
Tsuyoshi Takagi |
2nd Author's Affiliation |
Future University-Hakodate (Future Univ. Hakodate) |
3rd Author's Name |
|
3rd Author's Affiliation |
() |
4th Author's Name |
|
4th Author's Affiliation |
() |
5th Author's Name |
|
5th Author's Affiliation |
() |
6th Author's Name |
|
6th Author's Affiliation |
() |
7th Author's Name |
|
7th Author's Affiliation |
() |
8th Author's Name |
|
8th Author's Affiliation |
() |
9th Author's Name |
|
9th Author's Affiliation |
() |
10th Author's Name |
|
10th Author's Affiliation |
() |
11th Author's Name |
|
11th Author's Affiliation |
() |
12th Author's Name |
|
12th Author's Affiliation |
() |
13th Author's Name |
|
13th Author's Affiliation |
() |
14th Author's Name |
|
14th Author's Affiliation |
() |
15th Author's Name |
|
15th Author's Affiliation |
() |
16th Author's Name |
|
16th Author's Affiliation |
() |
17th Author's Name |
|
17th Author's Affiliation |
() |
18th Author's Name |
|
18th Author's Affiliation |
() |
19th Author's Name |
|
19th Author's Affiliation |
() |
20th Author's Name |
|
20th Author's Affiliation |
() |
Speaker |
Author-1 |
Date Time |
2010-03-04 17:00:00 |
Presentation Time |
25 minutes |
Registration for |
ISEC |
Paper # |
IT2009-79, ISEC2009-87, WBS2009-58 |
Volume (vol) |
vol.109 |
Number (no) |
no.444(IT), no.445(ISEC), no.446(WBS) |
Page |
pp.53-60 |
#Pages |
8 |
Date of Issue |
2010-02-25 (IT, ISEC, WBS) |
|