PRIME FACTOR EXTRACTION METHOD, METHOD FOR DETERMINING PRIME NUMBER AND POWER, PRIME FACTOR EXTRACTION DEVICE, AND PRIME FACTOR EXTRACTION PROGRAM

摘要

PROBLEM TO BE SOLVED: To provide a prime factor extraction method and a device which have excellent computation efficiency. SOLUTION: The method is characterized in that: small prime numbers Liand natural numbers eiare prepared so that the product of the prime numbers raisde to (Liei)th power exceeds 2u; Liis selected by further making (r) and Lirelatively prime on condition that r and Li-1 are mutually prime and ei≥2 and outputting Liwhen one Liis exactly divisible; such a minimum natural number kithat s×kiis exactly divisible byλ(Liei) when N is not exactly divisible by all Li's is found when N is not exactly divisible by all the Li's; kiroots Ai,jof kidifferent Nkimodulo Lieiare all regarded as candidates for Pr(mod Liei); one (j) is selected for all the (i)'s; candidates for Prmodule the product M of Li's are found among (m) Ai,j(mod Liei) given by those (i)'s and (j) by using Chinese residue theorem; and r-1modϕ(M) is found. COPYRIGHT: (C)2003,JPO