Arithmetic of Elliptic Curve over GF (m) Using Parallel Montgomery Multiplication

IPSJ Web Site 10 References

Bibliographic Information

Other Title
  • GF（2m）上の並列モンゴメリ乗算を用いた楕円曲線演算法
  • GF 2m ジョウ ノ ヘイレツ モンゴメリ ジョウザン オ モチイタ ダエン キョクセン エンザンホウ
  • 公開鍵暗号・デジタル署名

Search this article

Description

本論文では，多項式剰余演算系（PRNS）表現を利用した GF(2^m) 上の並列モンゴメリ乗算アルゴリズムを提案する．PRNS表現は特にハードウェアでの並列処理による高速演算に適した多項式の表現方法であるが，効率的な除算のアルゴリズムが知られていないため，剰余乗算に適用した例はほとんどなかった．本論文では剰余演算系（RNS）表現でのモンゴメリ乗算アルゴリズムを応用して，GF(2^m) 上のPRNSモンゴメリ乗算アルゴリズムを構成した．モンゴメリ乗算は実効的な除算を含まないため，PRNS表現での剰余乗算の高速並列処理が可能となる．さらに提案アルゴリズムを GF(2^m) 上の楕円曲線演算に適用した場合の点のスカラー倍算アルゴリズムの検討を行い，処理性能の評価を行った．

This paper presents a new method of parallel modular multiplication in GF(2^m) using polynomial residue number systems (PRNS).Though PRNS is suitable for a fast and parallel computation, there arefew algorithms to compute modular multiplication in PRNS representationsince division is not efficiently implemented. We derive the proposed algorithm by analogy with Montgomery multiplicationbased on residue number systems. We apply this method to arithmetic ofelliptic curve over GF(2^m) and provide point scalar multiplication method in PRNS representation.

Journal

References(10)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top