内容

• 脚步
• 第 1 部分（共 3 部分）：简单性测试
• 第 2 部分（共 3 部分）：简单性测试的工作原理
• 第 3 部分（共 3 部分）：使用中国剩余定理
• 提示
• 你需要什么

质数是只能被自身和 1 整除的数。所有其他数称为合数。判断一个数是否为素数的方法有很多种，各有优缺点。一方面，有些方法非常准确，但如果您处理大量数字，则它们非常复杂。另一方面，有更快的方法，但它们可能导致不正确的结果。选择合适的方法取决于您使用的数字有多大。

脚步

第 1 部分（共 3 部分）：简单性测试

笔记： 在所有公式中 n 表示要检查的数字。

1. 1 除数的枚举。 分开就够了 n 到从 2 到舍入值 (${ displaystyle { sqrt {n}}}$).
2. 2 费马小定理。 警告：有时测试会错误地将合数识别为质数，即使对于 a 的所有值也是如此。
   • 让我们选择一个整数 一种使得 2 ≤ a ≤ n - 1。
   • 如果 a (mod n) = a (mod n) 那么这个数可能是素数。如果不满足等式，则数 n 为合数。
   • 检查多个值的给定相等性 一种增加被测试的数字确实是素数的可能性。
3. 3 米勒-拉宾测试。 警告：有时，尽管很少，对于 a 的多个值，测试会错误地将合数识别为质数。
   • 找出数量 s 和 d 使得 ${ displaystyle n-1 = 2 ^ {s} * d}$.
   • 选择一个整数 一种 在 2 ≤ a ≤ n - 1 的范围内。
   • 如果 a = +1 (mod n) 或 -1 (mod n)，则 n 可能是素数。在这种情况下，请转到测试结果。如果等式不成立，则转到下一步。
   • 平方你的答案（${ displaystyle a ^ {2d}}$）。如果你得到 -1 (mod n)，那么 n 可能是一个质数。在这种情况下，请转到测试结果。如果等式失败，则重复 (${ displaystyle a ^ {4d}}$ 等等）直到 ${ displaystyle a ^ {2 ^ {s-1} d}}$.
   • 如果在对数字进行平方之后的某个步骤而不是 ${ displaystyle pm 1}$ (mod n)，你得到 +1 (mod n)，所以 n 是一个合数。如果 ${ displaystyle a ^ {2 ^ {s-1} d} neq pm 1}$ (mod n)，则 n 不是素数。
   • 测试结果：如果n通过测试，则对其他值重复测试 一种以增加信心。

第 2 部分（共 3 部分）：简单性测试的工作原理

1. 1 除数的枚举。 根据定义，数 n 仅当它不能被 2 和除 1 和它本身以外的其他整数整除时才是简单的。上面的公式可以让你去掉不必要的步骤，节省时间：例如，检查一个数是否可​​以被3整除后，就不需要检查它是否可以被9整除。
   • floor (x) 函数将 x 舍入到小于或等于 x 的最接近的整数。
2. 2 了解模算术。 运算“x mod y”（mod是拉丁词“modulo”的缩写，即“module”）的意思是“将x除以y并求余数”。换句话说，在模算术中，当达到某个值时，称为 模块，数字再次“变”为零。例如时钟用模块12倒计时：它显示10、11和12小时，然后回到1。
   • 许多计算器都有一个 mod 键。本节末尾将向您展示如何手动计算大数的此函数。
3. 3 了解费马小定理的陷阱。 不满足测试条件的所有数字都是合数，但其余的数字只是 大概 很简单。如果您想避免错误的结果，请搜索 n 在“Carmichael numbers”（满足此测试的复合数）和“Fermat pseudoprime numbers”（这些数字仅对某些值满足测试条件）列表中 一种).
4. 4 如果方便，请使用 Miller-Rabin 测试。 这种方法虽然对于人工计算比较繁琐，但在计算机程序中经常使用。与 Fermat 方法相比，它提供了可接受的速度和更少的错误。如果对超过 1/4 的值进行计算，则合数不会被视为质数 一种...如果你随机选择不同的值 一种 并且对于所有这些测试都会给出阳性结果，我们可以相当高的置信度假设 n 是素数。
5. 5 对于大数，请使用模算术。 如果您手边没有 mod 计算器，或者计算器不是为处理如此大的数字而设计的，请使用幂属性和模算术来简化计算。下面是一个例子 ${ displaystyle 3 ^ {50}}$ 模式 50：
   • 以更方便的形式重写表达式： ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50. 手动计算可能需要进一步简化。
   • ${ 显示样式 (3 ^ {25} * 3 ^ {25})}$ 模式 50 = ${ 显示样式 (3 ^ {25}}$ 模组 50 ${ displaystyle * 3 ^ {25}}$ mod 50) mod 50。这里我们考虑了模乘的性质。
   • ${ 显示样式 3 ^ {25}}$ 模数 50 = 43。
   • ${ 显示样式 (3 ^ {25}}$ 模组 50 ${ displaystyle * 3 ^ {25}}$ 模 50) 模 50 = ${ 显示样式 (43 * 43)}$ 模式 50。
   • ${ displaystyle = 1849}$ 模式 50。
   • ${ 显示样式 = 49}$.

第 3 部分（共 3 部分）：使用中国剩余定理

1. 1 选择两个数字。 其中一个数字必须是合数，另一个必须是您想要简单测试的数字。
   • 数字 1 = 35
   • 数字 2 = 97
2. 2 选择两个大于零和分别小于数字 Number1 和 Number2 的值。 这些值一定不一样。
   • 值 1 = 1
   • 值 2 = 2
3. 3 计算 Number1 和 Number2 的 MMI（数学乘法逆）。
   • 计算MMI
     • MMI1 = Number2 ^ -1 Mod Number1
     • MMI2 = Number1 ^ -1 Mod Number2
   • 仅适用于质数（这将为合数提供一个数字，但不会是他的 MMI）：
     • MMI1 = (Number2 ^ (Number1-2))% Number1
     • MMI2 = (Number1 ^ (Number2-2))% Number2
   • 例如：
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. 4 为每个 MMI 创建一个表，直到 log2 模块：
   • 对于 MMI1
     • F (1) = Number2% Number1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Number1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Number1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Number1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Number1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Number1 = 1 * 1% 35 = 1
   • 计算配对数 1 - 2
     • 35 -2 = 33 (10001) 基数 2
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 mod 35
     • 人机界面1 = 27
   • 对于MMI2
     • F (1) = Number1% Number2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% Number2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Number2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Number2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Number2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Number2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Number2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Number2 = 35 * 35 mod 97 = 61
   • 计算配对数 2 - 2
     • 97 - 2 = 95 = (1011111) 基数 2
     • MMI2 = (((((F (64) * F (16)% 97) * F (8)% 97) * F (4)% 97) * F (2)% 97) * F (1)% 97)
     • MMI2 = (((((35 * 35)% 97) * 61)% 97) * 35% 97) * 61% 97) * 35% 97)
     • 人机界面2 = 61
5. 5 计算 (Value1 * Number2 * MMI1 + Value2 * Number1 * MMI2)% (Number1 * Number2)
   • 答案 = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • 答案 = (2619 + 4270)% 3395
   • 答案 = 99
6. 6 检查 Number1 不是质数
   • 计算 (Answer - Value1)% Number1
   • 99 – 1 % 35 = 28
   • 由于 28 大于 0，因此 35 不是质数。
7. 7 检查 Number2 是否为素数。
   • 计算（答案 - Value2）% Number2
   • 99 – 2 % 97 = 0
   • 由于 0 是 0，因此 97 很可能是素数。
8. 8 重复步骤 1 到 7 至少两次。
   • 如果在第 7 步中得到 0：
     • 如果 Number1 不是质数，请使用不同的 Number1。
     • 如果 Number1 是素数，则使用另一个 Number1。在这种情况下，您应该在第 6 步和第 7 步中得到 0。
     • 使用不同的含义 1 和含义 2。
   • 如果在第 7 步中您始终得到 0，则数字 2 很可能是素数。
   • 如果 Number1 不是质数并且 Number2 是 Number1 的除数，则步骤 1 到 7 可能会导致错误。当两个数字都是素数时，所描述的方法适用于所有情况。
   • 您需要重复步骤 1 到 7 的原因是因为在某些情况下，即使 Number1 和 Number 2 不是素数，在步骤 7 中您也会得到 0（对于一个或两个数字）。这种情况很少发生。选择另一个 Number1（复合），如果 Number2 不是素数，那么在第 7 步中 Number2 将不等于 0（除了 Number1 是 Number2 的除数的情况——这里的素数在第 7 步中总是等于 0）。

提示

• 从 168 到 1000 的质数：2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79 , 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 19, 19, 19 19 , 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 3, 3, 3, 3, 3, 3, 3, 39 , 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 4, 7, 4, 5, 4, 59, 9 , 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 6, 6, 6, 6, 6, 6, 36, 5 , 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 8, 8, 3, 8, 82, 82 , 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 9.983, 9
• 虽然蛮力测试在处理大量数字时是一项乏味的测试，但它对于小数字非常有效。即使在大数的情况下，也从测试小除数开始，然后转向更复杂的方法来检查数字的简单性（如果没有找到小除数）。

你需要什么

• 纸、笔或电脑