algorithm - 如果 p 是素数，如何使用快速算法检查 ap + b 是否是素数？

Question

我们有三个数字a、b 和p。 p 是一个大质数，但 a 和 b 比 p 小得多。

如何使用快速算法判断ap + b是否为素数？

我们不想使用 BigInteger 类和类似的东西。

请注意，我们还可以了解一些关于p 的其他信息。例如，如果 m 很小，则可以很容易地计算出 p % m。

Answer 1

这个问题更适合数学伙伴论坛。

如果 gcd(a, b) != 1 那么它不是素数。

如果 (a + b) % 2 != 1 那么它不是素数。

查看 3.7 + 4 不是质数会导致另一个规则。

所以做一些数学，即

(a % b) * (p % b)

必须是质数，尽管 p % b 是不可能的。