A-037 格子縮約を用いた素因数分解アルゴリズムについて(A.モデル・アルゴリズム・プログラミング)
スポンサーリンク
概要
- 論文の詳細を見る
N=p^rqという形の合成数に対し,1999年にBoneh等は格子縮約(LLL)アルゴリズムを用いた素因数分解法を提案した.その時間計算量はLLLアルゴリズムの呼び出し回数によって評価され,最悪の場合2(1+c)/(r+c)loggp回の呼び出しが必要であった(cはある定数).2001年に内山,金山はアルゴリズムを改良し,(2^k-p)/|p-N<r+1>|倍の高速化を達成した(k,N_<r+1>はある定数).さらに伊豆は2003年に約2倍の高速化法を提案した.本稿ではこれらの改良法の効果を実証する.
- FIT(電子情報通信学会・情報処理学会)推進委員会の論文
- 2004-08-20
著者
関連論文
- 素因数分解とRSA暗号の安全性(インダストリアルマテリアル)
- 4. ハードウェアによる素因数分解(素数)
- 標数2有限体上楕円曲線の位数計算 (代数曲線とその応用論文小特集)
- Atkin,Elkies らによる Schoof のアルゴリズム改良の実装について(数式処理における理論と応用の研究)
- Atkin, ElkiesらによるSchoofアルゴリズム改良の実装について
- 暗号理論と楕円曲線-数学的土壌の上に花開く暗号技術-, 辻井重男,笠原正雄(編著), 有田正剛,境隆一,只木孝太郎,趙晋輝,松尾和人(共著), 森北出版, 2008-09, 菊判, 定価(本体3,800円+税)
- 千葉大学サマースクール 楕円曲線暗号入門 (特集 数学ライブ2007)
- 素因数分解と楕円曲線 (フォーラム:現代数学のひろがり 楕円曲線:その魅惑の世界)
- XTRに対するサイドチャネル攻撃と効率的な対策方式
- XTRに対するサイドチャネル攻撃と致率的な対策方式
- ランダム化初期点を用いた電力解析対策法について(その2)
- テイト・ペアリングの高速計算法(MOV次数が大きい場合)(モバイル環境におけるPerson to person高信頼性情報流通技術)(情報通信サブソサイエティ合同研究会)
- テイト・ペアリングの高速計算法(MOV次数が大きい場合)(モバイル環境におけるPerson to person高信頼性情報流通技術 : 情報通信サブソサイエティ合同研究会)
- SIMDを用いた楕円曲線の高速演算法について
- Address-bit DPAによるOK-ECDHとOK-ECDSAの解析報告
- サイドチャネル攻撃への耐性を持つ高速楕円曲線スカラー倍算について
- Brier-Joyeの加法公式について
- 素因数分解に適した楕円曲線の生成法について
- 楕円曲線法の高速化について
- 次世代電子パスポートへの署名偽造攻撃の適用評価
- 暗号解読 : 受賞業績 素因数分解専用ハードウェアの開発とRSA暗号の安全性評価(平成19年度喜安記念業績賞紹介)
- 素因数分解ハードウェアTWIRLの実現可能性に関する検討報告(II)
- 素因数分解ハードウェアTWIRLの実現可能性に関する検討報告(I)
- 素因数分解ハードウェアTWIRLの実現可能性に関する検討報告(II)
- 素因数分解ハードウェアTWIRLの実現可能性に関する検討報告(I)
- 素体上の超特異楕円曲線におけるペアリング暗号の効率的な計算手法
- 有限体での剰余演算のソフトウェア実装に適したGF(3)上の既約4項式の探索について
- 有限体での剰余演算のソフトウェア実装に適したGF(3)上の既約4項式の探索について
- テイト・ペアリングの高速計算法(MOV次数が大きい場合)(モバイル環境におけるPerson to person高信頼性情報流通技術)(情報通信サブソサイエティ合同研究会)
- テイト・ペアリングの高速計算法(MOV次数が大きい場合)(モバイル環境におけるPerson to person高信頼性情報流通技術)(情報通信サブソサイエティ合同研究会)
- サイドチャネル攻撃に対する情報理論的安全性に向けて
- サイドチャネル攻撃に対する情報理論的安全性に向けて
- サイドチャネル攻撃への耐性を持つ高速楕円曲線スカラー倍算について
- A Parallelized Elliptic Curve Multiplication and its Resistance against Side-Channel Attacks (Algorithms in Algebraic Systems and Computation Theory)
- Brier-Joyeの加法公式について
- Brier-Joyeの加法公式について
- Brier-Joyeの加法公式について
- 墨塗り署名方式PIATの安全性について(セッション4-B:署名)
- 墨塗り署名方式PIATの安全性について(セッション4-B:署名)
- EMV署名に対するCNTW攻撃の計算量評価(セキュリティ関係,一般)
- EMV署名に対するCNTW攻撃の計算量評価(セキュリティ関係,一般)
- EMV署名に対するCNTW攻撃の計算量評価(セキュリティ関係,一般)
- Cheonアルゴリズムの高速化検討(セキュリティ関係,一般)
- Cheonアルゴリズムの高速化検討(セキュリティ関係,一般)
- Cheonアルゴリズムの高速化検討(セキュリティ関係,一般)
- 補助入力つき離散対数問題と暗号プロトコルの安全性について(セキュリティ関係,一般)
- 補助入力つき離散対数問題と暗号プロトコルの安全性について(セキュリティ関係,一般)
- 国際会議SAC 2001報告
- 補助入力つき離散対数問題と暗号プロトコルの安全性について(セキュリティ関係,一般)
- 1G-1 楕円曲線暗号の攻撃評価(セキュリティ基盤,一般セッション, セキュリティ,情報処理学会創立50周年記念)
- 墨塗り・削除署名の拡張
- 墨塗り・削除署名の拡張
- y座標を用いない楕円曲線演算について
- y座標を用いない楕円曲線演算について
- A-037 格子縮約を用いた素因数分解アルゴリズムについて(A.モデル・アルゴリズム・プログラミング)
- 素因数分解の現状について
- 素因数分解に適した楕円曲線の生成法について
- ルーティングを用いた素因数分解回路について
- ルーティングを用いた素因数分解回路について
- A-7-4 モンゴメリ型楕円曲線について(A-7.情報セキュリティ,一般セッション)
- TinyTateライブラリが使用する楕円曲線における補助入力付き離散対数問題の解読報告(その2)(セキュリティ関係,一般)
- TinyTateライブラリが使用する楕円曲線における補助入力付き離散対数問題の解読報告(その2)(セキュリティ関係,一般)
- TinyTateライブラリが使用する楕円曲線における補助入力付き離散対数問題の解読報告(その2)(セキュリティ関係,一般)
- TinyTateライブラリが使用する楕円曲線における補助入力付き離散対数問題の解読報告(その2)(セキュリティ関係,一般)
- 国際会議SHARCS 2012報告 (情報セキュリティ)
- 点のスカラ倍算に対するメッセージ選択型電力解析(サイドチャネル攻撃,暗号と情報セキュリティ実装技術論文)
- 国際会議CHES 2011報告
- "I"見聞録(第37回)NIAT2011 FDTC2011 CHES2011
- 国際会議SHARCS 2012報告