平方数を探索する素因数分解アルゴリズム（その2）

摘要

合成数n＝pqに関する平方数を探索する確率的な素因数分解アルゴリズムを提案する。奇素数からなる集合Fの要素を任意に2分割し、その部分集合のすべての要素を掛け合わせた値を各々i，jとするとき、p-j/2・q-i/2＞「（(pq)~(1/2)-(ij+4)~(1/2)/2）~2」の関係が成り立つ場合には、x＝p-j/2・q-i/2において、関数f(x)＝（1＋「(nx)~(1/2)」）~2-nxは平方数となり、素因数pとqが得られる。すなわち、本方法は集合Fの2つの部分集合の比i/j（≈q/p）に依存する確率的な素因数分解アルゴリズムである。%We propose a probabilistic factoring algorithm searching squares using a factor base consisting of odd primes.