整数因子分解方程

应用新的数学方法,通过对乘积分类,建立了描述乘积的一类不定方程,化为可解的二次同余方程,阐述该不定方程的计算量为O(nlog2n)的计算机算法,对密码破译与数论方法均有一定意义.给出任意非5k类奇数与方程的对应关系,根据方程确定变量有限连续取值区间,分类计算所有整数分解因子.论述所给分解程序的计算复杂性,讨论算法适合大数分解的理由.最后叙述筛法:求具有某一尾数一定范围内的复合数(素数)的方法.该算法把整数的素性检测和因子分解合二为一.具体特点:试除因子是连续整数的函数,用试除因子数列代替素数列作为整数素性检测序列.

Integer Factorization Equation

A new mathematical method is used to establish a new class of indefinite equation which describes multiplication product, by classifying products. The indefinite equation is converted to solvable quadratic congru- ence equation. This paper describes the calculation of O （nlog2n） and computer algorithms, having important val- ue for cryptology and number theory. Relations between arbitrary non-Sk odd numbers and equations are provided; limited value interval of variables is determined to calculate all integer factorization factors. This paper discusses the calculation complexity of factorizing process, the reason why this algorithm is good for factorization of large integers. Finally, this paper finally discusses sieve method： find a composite number （prime） method within a certain range of the mantissa. The algorithm combines integer primality testing and factor/zation. Specific features： trial division factor is a function of continuous integers. Sequence of trail division factors is used to replace that of prime numbers as integer primality testing sequence.