首页>
外国专利>
PRIME FACTOR EXTRACTION METHOD, METHOD FOR DETERMINING PRIME NUMBER AND POWER, PRIME FACTOR EXTRACTION DEVICE, AND PRIME FACTOR EXTRACTION PROGRAM
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 Li and natural numbers ei are prepared so that the product of the prime numbers raisde to (Liei)th power exceeds 2u; Li is selected by further making (r) and Li relatively prime on condition that r and Li-1 are mutually prime and ei≥2 and outputting Li when one Li is exactly divisible; such a minimum natural number ki that s×ki is 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; ki roots Ai, j of ki different Nki modulo Liei are all regarded as candidates for Pr (mod Liei); one (j) is selected for all the (i)'s; candidates for Pr module 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-1 mod ϕ (M) is found.;COPYRIGHT: (C)2003,JPO
展开▼
机译：解决的问题：提供一种计算效率优异的素数提取方法和装置。解决方案：该方法的特征在于：素数L i 和自然数e 小准备i ，以使素数乘以（L i ei ）次幂的乘积超过2 u ;通过进一步使（r）和L i 相对素数来选择L i ，条件是r和L i -1是互质素且e i ＆ge; 2并在一个L i 完全可分割时输出L i ;这样的最小自然数k i 为s＆times; k i 可被＆lambda;整除。当N不能被所有L整除时发现（L i ei ） i 的; k i 根k i 的N ki 模A的A i ， j i ei 都被视为P r 的候选者（mod L i ei ）;为所有（i）选择一个（j）;在（m）个A i ， j i 的乘积M的P r 模块的候选（i）和（j）给出的（mod L i ei ）并用中文残差定理给出;和r -1 mod＆phiv; （M）被发现。;版权：（C）2003，JPO
展开▼
