使用 BigInteger 查找 200 位素数

Question

一种绝对有效的方法是从 0 开始直到找到 200 位素数 numbers.In 为了做到这一点我写了这个方法：

var primeList = arrayListOf(BigInteger("2"))
fun findNextPrime(num : BigInteger): BigInteger {
    val n = num + BigInteger.ONE
    val sqrt = sqrt(num)
    for (bigInteger in primeList) {
        if(bigInteger > sqrt){
            return n
        }
        if(n % bigInteger == BigInteger.ZERO){
            return findNextPrime(num + BigInteger.ONE)
        }
    }
    return n;
}

我将找到的数字添加到 primeList 并仅检查小于 squareRoot.Even 的数字，虽然这是我能写的最快的算法但是找到一百万后需要很长时间 digits.which 只是7 digits.I 可能会死，直到它达到 200 位。（即使我的笔记本电脑是 i7 第 8 代）。所以我接下来使用的是：

n = 2 * 3 * 5 *... + 1

好吧，n 是素数，使用这种方法得到高位数字非常快，但是没有什么可以确保达到 200 位 exactly.I 得到 198 和 201 digits.But 没有 200代码很简单，但我 post 无论如何：

var all = BigInteger.ONE
primeList.forEach {
   all *= it
}
all++
println(all.toString().length)

Answer 1

1 + 前 n 个素数的乘积并不总是素数。你可能误解了它在证明有无限多个素数中的作用。如果 p_1, p_2, ..., p_n 是第一个 n 个素数，那么是正确的，那么

p_1 * p_2 * ... * p_n + 1

要么是质数，要么包含一个大于任何 p_i 的质因数，但这与合数一致。有关详细信息，请参阅 primorials 上的维基百科文章。

在尝试200位的情况下，前92个素数+1的乘积有199位，前93个素数+1的乘积有201位。在这两种情况下， Miller-Rabin test 表明它们是复合的。我一直无法分解 199 位数字，但 201 位数字因式分解为

509558935064289364432032169616857776489168568369134671296055828054188240764364761921821351373922822013621199759688858354748131233614846920025560717744496960296617420071391914813530238313960697008021211 = 11587 * 43976778723076669062918112506848863078378231498156094873224806080451216083918595142989673890905568483094951217717170825472351016968572272376418461874902646094469441621765074205016849772500275913353

对于这种数量级的数字，获得素数的唯一有效方法是随机生成目标大小的候选数字并测试它的素数（使用类似 Miller-Rabin 测试的方法）。根据素数定理，200 位素数是比较多的，所以在实践中你可以很快地找到这样一个素数。例如，我使用 Miller-Rabin 编写的 Python 脚本在不到一秒的时间内吐出以下 200 位素数：

49675218696612399034240799519655205503986657506787162015105425670413948962864456158664793804627084299081036134562339483478437262146378569515417671690110863951848724044479367633926630234074394356492223

On Edit: 这是我用来查找 200 位素数的 Python 脚本。该代码是针对 class 我教密码学的，所以我写它是为了便于讨论而不是简洁或高效：

import random

#The following function finds s and d in
#n-1 = 2^s*d with d odd
def findSD(n):
    s = 0
    d = n-1
    while d % 2 == 0:
        s = s + 1
        d = d//2
    return s,d

def checkBase(a,n):
    s,d = findSD(n)
    x = pow(a,d,n)
    if x == 1 or x == n-1:
        return "probable prime"
    else:
        for i in range(s-1):
            x = pow(x,2,n)
            if x == 1:
                return "composite"
            elif x == n-1:
                return "probable prime"
        #if you get to this stage, -1 not reached despite s-1
        #squarings -- so must be composite
        return "composite"

def MSR(n,k):
    #Implements the Miller-Selfridge-Rabin test for primality
    for i in range(k):
        a = random.randint(2,n-2)
        if checkBase(a,n) == "composite":
            return "composite"
    #if you get here n has survived k potential witnesses, so
    return "probable prime"

#The following function is slightly different from the one discussed in class:

def prime(n):
    smallPrimes = [2,3,5,7,11,13,17,19]

    for p in smallPrimes:
        if n == p:
            return True
        elif n % p == 0:
            return False

    if MSR(n,20) == "composite":
        return False
    else:
        return True

def findPrime(maxN):
    while True:
        m = random.randint(1,maxN//2)
        n = 2*m+1
        if prime(n):
            return n

例如，findPrime(10**200) 通常会给你一个 200 位的质数（尽管有可能得到 199 位甚至更小的数）。

Answer 2

在 BigInteger class 中有一个方法叫做：

isProbablePrime(int)

它使用我们朋友使用的相同算法：但它也用另一个 algorithm.It 检查结果，工作非常整洁。

使用 BigInteger 查找 200 位素数

find 200 digit prime numbers using BigInteger

java

math

primes

prime-factoring

kotlin