solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看2239次
Finding Large Primes. (arXiv:1709.09963v1 [math.GM])
来源于:arXiv
In this paper we present and expand upon procedures for obtaining large d
digit prime number to an arbitrary probability. We use a layered approach. The
first step is to limit the pool of random number to exclude numbers that are
obviously composite. We first remove any number ending in 1,3,7 or 9. We then
exclude numbers whose digital root is not 3, 6, or 9. This sharply reduces the
probability of the random number being composite. We then use the Prime Number
Theorem to find the probability that the selected number n is prime and use
primality tests to increase the probability to an arbitrarily high degree that
n is prime. We apply primality tests including Euler's test based on Fermat
Little theorem and the Miller-Rabin test. We computed these conditional
probabilities and implemented it using the GNU GMP library. 查看全文>>