高木 剛 (九州大学)
  

  

    
題名: 低Hamming 重み標数の素体上における数体篩法の計算機実験 
  

  

    
アブストラクト: DSA やDiffie-Hellman 鍵共有は，素体GF(p) 上の離散対数問題
の困難性を安全性の根拠としているため，GF(p) 上の離散対数
問題の困難性を評価することは，DSA やDiffie-Hellman 鍵共有
などの安全性を考察する上で重要である．GF(p) 上の離散対数
問題に対する漸近的に最速な解読アルゴリズムとして，数体篩
法が知られている．離散対数問題に対する数体篩法はGordon
によって初めて提案され，その後，Schirokauer やJoux-Lercier
が改良した．一方，一般的な素数pではなく，low weight なp
(pの符号付き2進表現のHamming重みが低い場合)に対して，
Schirokauer は従来の数体篩法よりも計算量が小さくなるような
多項式の選択方法を提案した．本稿では，100bits 及び110bits
のlow weight なp に対してJoux-Lercier とSchirokauerの多項式
選択法を実装し，実行時間の比較を行った．



  
  

    

  


     
Tsuyoshi Takagi (Kyusyu University)
  

  

    
Title: An Experiment of Number Field Sieve over GF(p) of Low Hamming
Weight Characteristic

  

  

    
Abstract: The security of the digital signature algorithm (DSA) and
Diffie-Hellman 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 the DLP over GF(p) for discussing the security of these protocols. The number field sieve (NFS) is asymptotically the fastest algorithm to solve the 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.

  
    

[Back ]