Euclid環上の因数分解およびGCDについて : 格子算法の応用
スポンサーリンク
概要
- 論文の詳細を見る
A. K. Lenstra, H. W. LenstraとL. Lovaszが格子算法を整数環上の1変数多項式の因数分解アルゴリズムに応用し,計算時間がその多項式の次数に対してその次数の多項式オーダーになることを可能にして以来,格子算法が種々の因数分解アルゴリズムに応用されている.本論文では,A. K. Lenstraによる格子算法の基本的性質を抽出し,Euclid付値環上の因数分解およびGCD計算に格子算法が適用できることを示す.また,ある種の条件の下ではEuclid環上の因数分解へも応用が可能であることを示す.
- 日本ソフトウェア科学会の論文
- 1988-01-14
著者
-
竹島 卓
富士通研究所
-
横山 和弘
富士通研究所
-
横山 和弘
立教大学理学部数学科
-
竹島 卓
富士通(株)
-
横山 和弘
富士通(株)
-
竹島 卓
富士通(株)国際情報社会科学研究所
-
横山 和弘
富士通研究所国際情報社会科学研究所
関連論文
- Algebraic approach to discrete-time polynomial spectral factorization
- 計算実代数幾何入門(第5回)CADによるQE
- 計算実代数幾何入門(第4回)CADアルゴリズム(後半)
- 計算実代数幾何入門(第3回)CADアルゴリズム(前半)
- 最適化問題を効率的に解くための special CAD
- 計算実代数幾何入門(第2回)QEによる最適化とその応用
- 計算実代数幾何入門(第1回)CADとQEの概要
- Numerical Cylindrical Algebraic Decomposition with Certification via Symbolic Reconstruction (Computer Algebra : Design of Algorithms, Implementations and Applications)
- On Computing Sum of Roots with Positive Real Parts of Polynomials (Computer Algebra : Design of Algorithms, Implementations and Applications)
- Radical Representation of Polynomial Roots
- 有限体上の多変数多項式の因数分解について (Computer Algebra : Algorithms, Implementations and Applications)
- 標数2有限体上楕円曲線の位数計算 (代数曲線とその応用論文小特集)
- Atkin,Elkies らによる Schoof のアルゴリズム改良の実装について(数式処理における理論と応用の研究)
- 連立代数方程式の種々の解法 (特集 数式処理とその周辺--最新事情からソフトの評価・応用まで)
- Atkin, ElkiesらによるSchoofアルゴリズム改良の実装について
- Prime Decomposition of Radical Ideals and Algebraic Factorization of Polynomials
- 行列の有理標準形の一計算法(数式処理と数学研究への応用)
- modular 算法による多項式GCD計算について(数式処理と数学研究への応用)
- 共通鍵ブロック暗号SC2000
- 楕円曲線暗号 (特集 21世紀に向けた研究開発)
- 多項式環上の素イデアル分解について(数式処理における理論とその応用の研究)
- 零因子をもつ環上の逆行列計算について(数式処理における理論と応用の研究)
- 代数制約の処理 (制約論理プログラミング)
- Euclid環上の因数分解およびGCDについて : 格子算法の応用
- 楕円曲線暗号
- 計算機代数入門
- 固有分解と特異値分解用ライブラリの性能評価のためのテスト行列に関する考察(数値計算1)
- 宮城清行「明元算法」に現れる連立代数方程式の解について
- 和算における「冪乗演段」で扱われた連立代数方程式の解について
- real root countingに関する話題 (Computer Algebra : Design of Algorithms, Implementations and Applications)
- 関孝和の問題を解く
- パラメーターが指数部に現れる連立代数方程式について (Computer Algebra : Design of Algorithms, Implementations and Applications)
- On the Abhyankar's question for affine plane curves with one place at infinity (Feasibility of Theoretical Arguments of Mathematical Analysis on Computer)
- 今を生きる
- Risa/Asir上の複数多項式2次ふるい(MPQS)の実装について
- On a polynomial parametrization problem of plane curves with one place at infinity
- 日本数式処理学会第12回大会報告
- 頂点作用素代数研究の計算機による証明支援 (Computer Algebra : Algorithms, Implementations and Applications)
- 大会報告 日本数式処理学会第12回大会報告
- 有限体上の多項式イデアルの素イデアル分解について (数学解析の計算機上での理論的展開とその遂行可能性)
- Mandelbrot 集合の泡について
- Mandelbrot集合の泡について (大会報告 第15回日本数式処理学会大会報告)
- Risa/Asirの開発
- 整数行列の固有値,固有ベクトルの計算法について
- 線形分離写像による判定を用いた代数方程式の実解の定位 (数式処理における理論と応用の研究)
- Cplotの3次元描画への拡張について
- 線形写像による判定を用いた代数方程式の実解の代数的解法について
- 2変数代数曲線の忠実な描画
- 線形写像による判定を用いた代数方程式の実解の代数的解法について (数式処理における理論と応用の研究)
- 任意精度によるゼロ次元代数方程式の解の位置判定
- Displaying Real Solution of Mathematical Equations
- 数式処理と画像描画II
- 三斜内容三圓術(Malfattiの問題)の数式処理 : 有理関数体上のタワーの構成(数式処理における理論とその応用の研究)
- 数式処理と画像描画
- グレブナー基底の並列計算と連立代数方程式
- ブール方程式による併存到達可能性解析 (情報の記憶と利用に関する理論的研究)
- 同値律をみたす述語による関係データモデル従属性の一般化について (情報の記憶と利用に関する理論的研究)
- PSI上の数式処理システムSAM
- ISSAC 参加記
- RISC-Linz 滞在報告(数式処理と数学研究への応用)
- Grobner Basis の基礎(数式処理と数学研究への応用)
- 電子相関理論のための数式処理システムに向けて (数式処理研究の新たな発展)
- 「検証」は「信頼」の原点
- 有限体上の多項式イデアルのベキ零次数別分解(DND)について (第20回日本数式処理学会大会報告)
- QC2ASの設計について
- $\mathbf{QC^2AS}$ : 電子相関理論のための数式処理システムの設計とその利用 (Computer Algebra : Design of Algorithms, Implementations and Applications)
- 有限体上の多項式イデアルのベキ零次数別分解(DND)について
- 第二量子化演算子の代数的扱いとその実装
- グレブナー基底候補の正当性検証について (数式処理 : その研究と目指すもの)
- RL-003 準同型暗号を用いた複数企業間の顧客情報分析(L分野:ネットワーク・セキュリティ,査読付き論文)