在 Mathematica 中寻找大素数

Question

我是 Mathematica 的新手，我正在尝试寻找可以仅使用数字 0、1、2 和 3 编写的大质数，并且这些数字的一半以上必须为 0。例如100003 符合条件。

我正在考虑将 Prime[n] 函数与一堆 if "If" 语句一起使用，但我想知道是否有更有效的方法来解决这个问题。提前致谢。

Answer 1

你可以去钓鱼了。首先生成所需模式的大整数，然后测试它们的素数。我没有 Mathematica，但这是 Python:

中的一个快速而肮脏的实现

import random

def rand_candidate(n):
    #assumes n > 4
    while True:
        s = [random.choice(['1','2','3'])]
        for i in range(n-2):
            s.append(random.choice(['0','0','0','1','2','3']))
        s.append(random.choice(['1','3']))
        if s.count('0') > n/2: return int(''.join(s))

前面的函数首先选择non-zero个前导数字，然后以偏0的方式选择中间数字，然后选择最后一个数字使其成为奇数，检查整体结果是否所需数量的零。

对于素性测试，我懒得用 Fermat pseudo-prime 测试。以下测试用于（并且可能仍在使用）RSA 的 PGP 实现。它证明合数为质数的概率非常低。在 Mathematica 中，您当然可以求助于更复杂的测试：

def prob_prime(n):
    tests = [2,3,5,7]
    return all(n % p != 0 and pow(p,n-1,n) == 1 for p in tests)

将它们放在一起：

def go_fishing(n):
    while True:
        p = rand_candidate(n)
        if prob_prime(p): return p

典型输出：

>>> go_fishing(20)
23002001032200000101
>>> go_fishing(100)
1100200103020002000000000020232222230321210000103030031022000000200001001300020010012122020101020113

计算机代数系统 Derive（我的机器上确实有）证明以上两者都是素数。

Answer 2

要获得好的答案，请在 http://mathematica.stackexchange.com

提出这个问题

要获得某种答案，请继续阅读...

函数

myTestQ[num_Integer] := 
   And[DigitCount[num][[10]] > Plus @@ DigitCount[num][[1 ;; 3]], PrimeQ[num]]

returns True 当它传递一个整数时 (i) 比 1s、2s 和 3s 和 (ii) 是质数。 And 按顺序评估其参数，而 short-circuits 因此应避免测试数字计数不正确的数字的素数。

在实践中，您的计算时间将主要由素数测试决定；生成和丢弃大量具有错误数字计数的整数是足够便宜的，您可以忽略程序那部分的低效率。

现在测试仅由 0,1,2,3 位数字组成的整数范围。有一整个整数族只使用这些数字，即所有以 base-4 编写的整数。所以让我们生成那些：

IntegerString[Range[lo, hi, 2], 4]

这将以 2 的步长生成表示从第 lo 到第 hi 的所有 base-4 整数的字符串（你不会对任何偶数感兴趣数）。例如

IntegerString[Range[1, 13, 2], 4]

产生

{"1", "3", "11", "13", "21", "23", "31"}

即字符串形式的1st, 3rd, 5th, ..., 13th base-4 numbers。当然，您需要将它们作为整数返回以测试它们，为此我们将使用 ToExpression。

将它们混合在一起，你会得到类似

的东西

Select[ToExpression[IntegerString[Range[lo, hi, 2], 4]], myTestQ]

将 lo 和 hi 替换为您喜欢的任何值，但要确保 lo 是奇数。

在 Mathematica 中寻找大素数

Finding large primes in Mathematica

primes

wolfram-mathematica