生成具有指定最后数字的大质数

Question

想知道如何生成512位(155位十进制数)素数,其中五位十进制数被指定/固定(例如.***28071)？

在没有任何规范的情况下生成简单素数的原则是可以理解的,但我的情况更进一步.

至少,我应该从哪里开始提示？

Java或C#是首选.

谢谢!

Answer 1

我想唯一的办法就是首先生成一个150个十进制数字的随机数,然后将28071附加到它后面number = randomnumber * 100000 + 28071然后只是用它之类的东西强制它

while (!IsPrime(number))
    number += 100000;

当然这可能需要一段时间来计算;-)

Answer 2

您是否尝试生成此类数字并进行检查？我希望这个速度可以接受.素数密度仅作为数字的对数减小,所以我希望你尝试几百个数字,直到你达到一个素数.ln(2^512) = 354所以350左右的一个数字将是素数.

粗略地说,素数定理指出如果选择一些大数N附近的随机数,则它的素数的概率约为1/ln(N),其中ln(N)表示N的自然对数.例如在N = 10,000附近,大约九分之一的数字是素数,而在N = 1,000,000,000附近,每21个数字中只有一个是素数.换句话说,N附近素数之间的平均差距大约是ln(N)

(来自http://en.wikipedia.org/wiki/Prime_number_theorem)

您只需要注意最终数字的数字.但我认为这就像检查最后一个数字不能被2或5整除一样容易(即它是1,3,7或9).

根据这个性能数据,您可以对每秒512位数据执行2000次ModPow操作,并且由于简单的质数测试是检查2^(p-1) mod p=1哪个是一个ModPow操作,因此您应该能够生成具有每秒属性的多个素数.

所以你可以做(​​伪代码):

BigInteger FindPrimeCandidate(int lastDigits)
{
    BigInteger i=Random512BitInt;
    int remainder = i % 100000;
    int increment = lastDigits-remainder;
    i += increment;
    BigInteger test = BigInteger.ModPow(2, i - 1, i);
    if(test == 1)
      return i;
    else
      return null;
}

并对该函数的结果进行更广泛的质检.