ωビット消去による拡張GCD問題の解法 : 逆元計算の一高速化手法(<特集>数論アルゴリズムとその応用,その1)
スポンサーリンク
概要
- 論文の詳細を見る
This paper presents a new algorithm for the extended integer GCD problem, which is often refered to for computing modular reciprocals, and has been being investigated rigorously. We apply the multi-bit elimination algorithm, recently developed for the integer GCD problem, to the extended problem. We show that the application cannot be straightforward, and there arise two problems related with exact division. To resolve these problems, we also apply the bit elimination algorithm. A brief discussion about implementation will be also given.
- 日本応用数理学会の論文
- 2002-12-15
著者
関連論文
- 陰関数描画と区間数演算の効率化について (Computer Algebra : Design of Algorithms, Implementations and Applications)
- 数式処理(システム)におけるマルチスレッド化の試み (Computer Algebra : Design of Algorithms, Implementations and Applications)
- 行列積アルゴリズムに強く依存した行列のデータ構造の実装
- Risa/Asirの行列演算の実装(II) (Computer Algebra : Design of Algorithms, Implementations and Applications)
- Risa/Asir の Matrix 演算の実装について
- 行列計算と基本線形演算の実装法について (Computer Algebra : Design of Algorithms, Implementations and Applications)
- 数式処理のための行列演算の効率的な実装法について
- 多項式表現と行列演算の改良 (Computer Algebra : Algorithms, Implementations and Applications)
- Risa/AsirのMatrix演算の検討
- Risa/AsirのMatrix演算の新しい実装について (Computer Algebra : Algorithms, Implementations and Applications)
- Web上におけるプレゼンテーション法(セッション2:Webと社会のつながり、応用技術)
- 数式の零点描画の高速化
- Risa/Asir のifplot の改良と並列化の試み (Computer Algebra : Design of Algorithms, Implementations and Applications)
- GPUを用いた多倍長整数演算法の設計
- GPUを使用した陰関数グラフ描画の高速処理法
- Web上におけるプレゼンテーション法(セッション2:Webと社会のつながり、応用技術)
- A Relation between a Group and a Ring (Computer Algebra : Algorithms, Implementations and Applications)
- A Machine Proof of the Proposition : "Ideal $\subseteq \cup_i$ PrimeIdeal$_i$ $\Rightarrow$ Ideal $\subseteq$ PrimeIdeal$_i$" (Computer Algebra : Algorithms, Implementations and Applications)
- "Ring Story"再考 : トレンド,エヴォリューション,そして計画
- 記号行列式の一階微分の評価法
- Wikiやblogでも数式を : BrEdiMaを使って (数式処理と教育 : 数学教育における数式処理システムの効果的利用に関する研究)
- Web上におけるプレゼンテーション法 (情報学基礎・デジタルドキュメント)
- Noda2005論文 Matrix Multiplication Made Fast--Practical View of Fast Matrix Operation for Computer Algebra System
- 自動証明を効果的に行うための手法 (Computer Algebra : Design of Algorithms, Implementations and Applications)
- 有理区間数とGPU並列処理について (第19回日本数式処理学会大会報告)
- 統合並列処理向けの多項式計算ソフトウェアの試作 (数式処理における理論と応用の研究)
- 一変数多項式因数分解のための並列計算系について(数式処理における理論と応用の研究)
- 5.数式処理と並列処理 (数式処理の最近の研究動向)
- 並列処理の多項式計算への応用
- 並列DDFアルゴリズム(数式処理における理論とその応用の研究)
- U-終結式の計算について(数式処理と数学研究への応用)
- 有理区間数とGPU並列処理について
- ωビット消去による拡張GCD問題の解法 : 逆元計算の一高速化手法(数論アルゴリズムとその応用,その1)
- 拡張された2W-ary GCDアルゴリズム
- 国際会議報告 : PASCO'97
- 高速多項式乗算アルゴリズムの実現
- 数式処理の教科書と関連書籍
- 多項式の高速多点評価法とその並列処理について : 高速プログラムの開発へ向けて(数式処理における理論と応用の研究)
- Speeded Chinese Remaindering
- 疎な多項式の補間のためのモジュラー算法(数式処理と数学研究への応用)
- 数式を省略して表示する方法の提案と検討 (数学ソフトウェアと教育 : 数学ソフトウェアの効果的利用に関する研究)
- Risa / Asir の行列演算と改良について (数式処理 : その研究と目指すもの)
- GPU並列処理による陰関数描画について
- 3変数の陰関数描画について (第20回日本数式処理学会大会報告)
- 有理区間数とGPU並列処理による陰関数描画について (Computer Algebra : Design of Algorithms, Implementations and Applications)
- 3変数の陰関数描画について
- 数式処理システム概説
- Asirでの3変数陰関数描画 (数式処理 : その研究と目指すもの)