Fast Remainder Calculation in Polynomial Multiplication
スポンサーリンク
概要
- 論文の詳細を見る
多項式f(x), g(x)の積f(x)g(x)に関する余剰f(x)g(x)mod x^mの計算法において, 三角積という手法を用いた高速な計算アルゴリズムあるを提案する.本アルゴリズムは部分的に従来の高速積計算法が適用できる点と, 並列計算が可能である点が特徴的である.計算量的には従来の高速計算法の域を越えられていないが, 現実的な大きさの多項式に対しては一定の効果を持つことがわかった.三角積の応用例として, (1)モジュラー多項式の計算, (2)一般的な余剰f(x)g(x)mod n(x)の計算, (3)有限体GF(q)における演算の計算への適用について述べる.
- 一般社団法人情報処理学会の論文
- 1998-09-16
著者
-
野呂 正行
富士通研究所
-
伊豆 哲也
富士通研究所セキュアコンピューティング研究部
-
伊豆 哲也
(株)富士通研究所hpc研究センター
-
野呂 正行
神戸大学理学研究科
-
野呂 正行
株式会社富士通研究所hpc研究センター
-
野呂 正行
富士通国際研究所
-
野呂 正行
(株)富士通研究所セキュアコンピューティング研究部
-
野呂 正行
株式会社富士通研究所情報社会科学研究所
関連論文
- 有限体上の多変数多項式の因数分解について (Computer Algebra : Algorithms, Implementations and Applications)
- 標数2有限体上楕円曲線の位数計算 (代数曲線とその応用論文小特集)
- 連立代数方程式の種々の解法 (特集 数式処理とその周辺--最新事情からソフトの評価・応用まで)
- Prime Decomposition of Radical Ideals and Algebraic Factorization of Polynomials
- 行列の有理標準形の一計算法(数式処理と数学研究への応用)
- modular 算法による多項式GCD計算について(数式処理と数学研究への応用)
- 多項式環上の素イデアル分解について(数式処理における理論とその応用の研究)
- XTRに対するサイドチャネル攻撃と効率的な対策方式
- XTRに対するサイドチャネル攻撃と致率的な対策方式
- 楕円曲線法の高速化について
- y座標を用いない楕円曲線演算について
- 一般数体篩法実装実験(2) : ミニ素因数分解・ミニ素数判定(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 一般数体篩法実装実験(2) : ミニ素因数分解・ミニ素数判定(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 一般数体篩法実装実験(2) : ミニ素因数分解・ミニ素数判定(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- A Parallelized Elliptic Curve Multiplication and its Resistance against Side-Channel Attacks (Algorithms in Algebraic Systems and Computation Theory)
- EMV署名に対するCNTW攻撃の計算量評価(セキュリティ関係,一般)
- EMV署名に対するCNTW攻撃の計算量評価(セキュリティ関係,一般)
- EMV署名に対するCNTW攻撃の計算量評価(セキュリティ関係,一般)
- 国際会議SAC 2001報告
- 固有分解と特異値分解用ライブラリの性能評価のためのテスト行列に関する考察(数値計算1)
- IMACS-ACA'96
- 多項式乗算の様々なアルゴリズムの比較 (数式処理における理論と応用の研究)
- Fast Remainder Calculation in Polynomial Multiplication
- 2.方程式を解く (数式処理の最近の研究動向)
- Replicable function の Risa/Asir による計算(数式処理における理論と応用の研究)
- Risa/Asir と数式処理(2)
- 数式処理システム risa / asir の内部構造(数式処理と数学研究への応用)
- PSI上の数式処理システムSAM
- 並行処理による数式処理の試み(数式処理と数学研究への応用)
- 局所$b$関数に付随するstratificationアルゴリズムの実装および応用 (Computer Algebra : Design of Algorithms, Implementations and Applications)
- グレブナーwalkアルゴリズムの実装と効率化について (Computer Algebra : Design of Algorithms, Implementations and Applications)
- Dynamic Evaluation を用いたDiscrete Comprehensive Grobner Bases の計算 (Computer Algebra : Design of Algorithms, Implementations and Applications)
- 斉次化とinter-reduction によるグレブナー基底計算の効率化について (Computer Algebra : Design of Algorithms, Implementations and Applications)
- Risa / Asir における新しい形式の数式の取り扱いについて (Computer Algebra : Design of Algorithms, Implementations and Applications)
- 代数体上のイデアルのグレブナー基底計算について (Computer Algebra : Design of Algorithms, Implementations and Applications)
- 離散戸田方程式を用いた大規模疎行列の連立一次方程式, 行列式, 固有多項式の計算法(応用可積分系, 平成17年研究部会連合発表会)
- 連立代数方程式の消去の理論と実際 (数学史の研究)
- Dynamic Evaluation の実装について
- 整数を要素とする大規模疎行列の固有方程式を高速に求める方法
- スピンの交換だけを用いた量子コンピュータにおける厳密なCNOTの存在
- KNOPPIX/Math を使ってみる
- はじめに
- Risa/Asirの新グレブナー基底計算パッケージについて (Computer Algebra : Design of Algorithms, Implementations and Applications)
- OpenXMの新サーバ, 新プロトコル (Computer Algebra : Design of Algorithms, Implementations and Applications)
- グレブナー基底計算のためのweight生成アルゴリズム (Computer Algebra : Design of Algorithms, Implementations and Applications)
- プログラマー=体力+腕力?
- Painleve-VI方程式の有理解と代数函数解について
- 有限体上の多変数多項式の因数分解について(その2) (Computer Algebra : Algorithms, Implementations and Applications)
- 並列計算機AP1000への数式処理システム Risa/Asir の実装とグレブナ基底の並列計算
- y座標を用いない楕円曲線演算について
- y座標を用いない楕円曲線演算について
- Risa / Asir による modular polynomial の計算(数式処理における理論と応用の研究)
- 数学ソフトの開発
- 代数幾何,代数解析に使えるソフトウェア (特集 数学を発展させるコンピュータソフト)
- OpenXM 1.1.3の概要 (数式処理における理論と応用の研究)
- OpenXMプロジェクトの現状について (数式処理における理論と応用の研究)
- Open asir入門
- Risa/Asir (特集 いろいろな数式処理システム)
- Risa/AsirにおけるWeyl Algebra上のグレブナ基底計算およびその応用 (数式処理における理論と応用の研究)
- フリ-の数学ソフトあれこれ (特集/計算の現在)
- Implementation of the $F_4$ algorithm in Asir (Algorithms for D-modules)
- グレブナ基底 : 理論,計算の効率化,応用 (数式処理における理論と応用の研究)
- Macintosh 版 Risa/Asir(数式処理における理論と応用の研究)
- Generalized Shape LemmaのHensel構成による計算(数式処理における理論とその応用の研究)
- 逐次代数拡大体上での1変数多項式のGCDについて(数式処理における理論とその応用の研究)
- 第二超局所理論におけるRadon変換の方法について(代数解析学の現況)
- 2-超函数のRadon変換とその応用について(偏微分方程式系の局所非局所変換理論)
- 国際会議CHES 2011報告
- グレブナー基底計算ソフトの開発秘話 (特集 グレブナー基底の新天地)
- 大会特別講演 数式処理の理論概説 (第20回日本数式処理学会大会報告)
- 数式処理の理論概説
- 国際会議CHES 2011報告
- グレブナー基底候補の正当性検証について (数式処理 : その研究と目指すもの)