素数判定与整数分解

The generation of RSA cryptosystem uses large primes and factoring directly RSA modulus is a natural method attacking against RSA cryptosystem.This shows that primality testing and integer factorization are two important theoretical computational problems and they also have practical value. This project will study these two basic problems, including (1) to determine more values about the least strong pseudoprime ψm by using the first m primes as bases; (2) to study the lower bound of the pseudoprimes which pass simultaneously the Miller-Rabin test and the Lucas test;（3）to obtain a quadratic time deterministic primality testing algorithm for some special numbers by using the general Eisenstein reciprocity law;（4）to give an affirmative answer to the Bosma problem which concerns primality testing;（5）to study the running time estimate for a new factoring algorithm proposed by us and to study fast algorithm for computing the value of the binomial coefficients modulo n;（6）to study new method for generating small quadratic residues modulo n.

RSA密码体制的生成用到了大素数，直接分解RSA模数是攻击RSA密码体制最自然的方法。这些表明素数判定与整数分解是具有重要理论意义和实际价值的计算问题。本项目集中研究这两个基本问题，主要研究：（1）确定以前m个素数为基的最小强伪素数ψm的更多的值；（2）研究同时通过Miller-Rabin判别法和Lucas判别法的伪素数的下界；（3）利用一般的Eisenstein互反律给出某些特殊数的素数判定的二次时间的确定性算法；（4）解决更多情形下素数判定Bosma问题的肯定回答；（5）研究我们提出的整数分解算法的时间复杂性估计，研究计算二项式系数mod n的值的快速算法；（6）研究生成小的二次剩余mod n的新方法。

RSA密码体制的生成用到了大素数，直接分解RSA模数是攻击RSA密码体制最自然的方法。这些表明素数判定与整数分解是具有重要理论意义和实际价值的计算问题。本项目集中研究这两个基本问题，主要研究成果为：（1）利用一般的Eisenstein互反律给出了某些特殊数的素数判定的二次时间确定性算法；（2）解决了素数判定Bosma问题的新情形；（3）提出了新的整数分解算法，为了估计其时间复杂性，对算法涉及的组合和进行了系统的研究。