講演抄録/キーワード |
講演名 |
2007-07-20 13:00
平方数を探索する素因数分解アルゴリズム ○小林邦勝(山形大) ISEC2007-55 |
抄録 |
(和) |
合成数nに関する平方数を探索する素因数分解アルゴリズムを提案する。nの10進桁数を底が10の対数lognで表し、メモリー量(計算機の台数)をlognのs乗、計算機1台当たりの計算量をlognのt乗とすると、素因数分解に要する関係式として、s+t=1/2が得られる。例えば、s=1/6のときt=1/3となり、数体ふるい法とほぼ同じ計算量になる。また、s=1/4のときt=1/4となり、並列計算を行うことにより高速化をはかることができる。 |
(英) |
We propose a factoring algorithm searching squares. By using parallel computing with this factoring algorithm, we can make a speeding up of factoring. |
キーワード |
(和) |
素因数分解アルゴリズム / 平方数 / 並列計算 / 拡張Fermat法 / 相加平均 / 相乗平均 / / |
(英) |
factoring algorithm / square / parallel computing / extended Fermat method / arithmetic mean / harmonic mean / / |
文献情報 |
信学技報, vol. 107, no. 141, ISEC2007-55, pp. 71-73, 2007年7月. |
資料番号 |
ISEC2007-55 |
発行日 |
2007-07-13 (ISEC) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
ISEC2007-55 |