常见的大素数判断算法和Miller-Rabin素判断算法的原理实现

一、摘要

大数素性检测一直是数论界和密码学界等领域经久不衰的研究方向。随着时间的推移，实现大数素性检测的算法也在不断改进和优化。目前已经出现了许多大数素性检测算法，其中 Miller-Rabin 算法尤其引人注目。本文将对常见的大素数判定算法进行调研，并详细介绍 Miller-Rabin 大素数判定算法的原理。接着，结合相关的数论知识，以生成一个 1024 位的大素数为例，编写程序实现了该算法的判定过程。

二、引言

1 研究的问题及其背景

随着计算机技术的不断发展，我们能够处理的数字规模也越来越大，这也体现了人们对大数素性检测算法的研究变得越来越重要。在密码学中，我们需要使用大质数来生成公钥和私钥，以保证信息的安全性。如果生成的大质数不是素数，那么加密算法将变得非常容易被攻破。因此，如何高效、准确地判断一个给定的大数是否为素数，一直是密码学、计算机科学和数学领域中一个重要的研究方向。

在过去的几十年里，人们提出了许多不同的大数素性检测算法，其中一些算法能够高效地处理非常大的数，而另一些算法则更适用于较小的数。例如，最早的质数测试算法是试除法，但这种算法效率低下，只适用于小规模的数。随后，费马小定理和 Miller-Rabin 算法等算法被开发出来，它们在处理较大的数时具有更高的效率和可靠性。

2 研究的目的及意义

大素数判定算法是为了判断一个数是否为素数而研究出来的一种算法。在实际应用中，我们经常需要使用大素数来保证密码学、通信和安全领域的安全性。例如，在RSA加密算法中，我们需要使用两个大质数来生成一个公钥和一个私钥，这两个大质数必须是素数才能保证加密的安全性。因此，判断一个大数是否为素数是非常关键的。

然而，对于大数而言，判断它是否为素数变得异常困难，传统的素性检测算法已经无法胜任。因此，研究大素数判定算法就显得非常必要。这些算法可以高效地判断一个大数是否为素数，从而保证了密码学、通信和安全领域的安全性。此外，大素数判定算法也在其他领域有着广泛的应用，例如质因数分解和离散对数问题等。因此，研究大素数判定算法具有重要的理论和实际意义。

三、研究方法

本次研究主要使用了文献研究法、经验总结法和实验研究法。首先阅读大数素性判断相关领域的文献，对大数素性判断的问题背景和常见方法有基本了解。同时，从文献中汲取前人研究智慧，总结前人研究经验，在前人研究的基础之上让自己的研究更加具有科学性和严谨性。最后，根据之前阅读的文献和总结的经验，编写代码实现Miller-Rabin算法，并不断调试和优化，最终得到实现Miller-Rabin大素数判定的程序。

以下是研究内容和过程：

1 常见的大素数判定算法

本次研究调研了四种大数素性判断算法，分别为费马素性测试算法、AKS 素性测试算法、Solovay-Strassen 素性测试算法、Miller-Rabin 素性测试算法，其中AKS属于确定性素性检测算法，其余三种属于概率型素性检测算法。在实际应用中，Miller-Rabin 素性测试算法是最常用的素数测试算法之一，它不仅判断速度较快，而且误判率也比较低。

1） Solovay-Strassen 素性测试算法

Solovay-Strassen 素性测试算法也是一种概率型算法，可以在多项式时间内判断一个数是否为素数。

Solovay-Strassen 素性测试算法的步骤如下：

1 随机选择一个整数 a，使得 1 < a < n。

2 计算 Jacobi 符号 J(a,n)。

3 根据欧拉判别准则，如果，则 n 可能是素数；否则，n 不是素数。

其中，Jacobi 符号是数论中的一种函数，定义为 J(a,n) = (a/n)，其中 a 是整数，n 是正奇数。欧拉判别准则是指，对于一个正奇数 n 和整数 a，如果 a 是模 n 的二次剩余，则 Jacobi 符号等于模 n 的平方根的正负性；如果 a 不是模 n 的二次剩余，则 Jacobi 符号等于 -1。该算法的时间复杂度为，其中 k 是测试的次数。

Solovay-Strassen 素性测试算法的优点在于其判定错误率极低，然而，相对于 Miller-Rabin 素性测试算法，Solovay-Strassen 素性测试算法在实现上稍微困难一些，并且在大数判定时相对于 Miller-Rabin 素性测试算法速度较慢。

2) AKS 素性测试算法

AKS 素性测试算法是一种确定性算法，可以在多项式时间内判断一个数是否为素数。

AKS 素数测试主要是基于以下定理：

整数n(≥ 2)是素数，当且仅当这个同余多项式对所有与n互素的整数a均成立。

这个定理是费马小定理的一般化，但是为了减少计算复杂度，实际AKS算法使用的是这个同余多项式。

AKS素性测试的步骤如下：

对于一个正整数 n，选择一个较小的质数 r，计算 r 的阶，即最小的 k 使得。

如果 n 是平方数，或者，其中 a 和 b 都是大于 1 的整数，则 n 不是素数。

如果对于所有小于 r 的质数 a，都有，则 n 不是素数。

如果，则 n 是素数；否则，进入下一步。

利用多项式算法计算，其中，如果存在一个整数 a，使得上式不等于，则 n 不是素数；否则，n 是素数。

该算法的时间复杂度为，比以往的素性检验算法都要快，而且可以对任意大小的数进行素性检验。然而，该算法在实际应用中并不常用，因为其常数项较大，实际运行速度较慢。

3) 费马素性测试算法

费马素性测试算法是一种概率型算法，可以在多项式时间内判断一个数是否为素数。

首先，我们知道，有费马小定理：

如果 p是一个素数，且整数 a不是 p的倍数，那么

因此，如果对于一个给定的整数 n，我们能够找到一个整数 a，使得，那么 n 一定不是质数。

费马素性检验的步骤如下：

随机选择一个整数 a，使得 1 < a < n。

计算。

如果结果不等于 1，则 n 不是素数；如果等于 1，则需要重新选择另一个 a 进行判断

重复进行这个过程，直到满足一定的检验次数或者判断出 n 不是质数为止。该算法的时间复杂度为，其中 k 是测试的次数。

虽然费马素性检验算法比较简单，但其正确性不是完全保证的，存在一定的概率错误。特别地，存在一些合数，使得算法无法正确判断其为合数，这些数被称为卡迈克尔数（Carmichael number）。因此，在实际应用中，通常需要结合其他的素性检验算法来进行判断。

尽管费马素性检验的精确性有限，但其优势在于简单和高效。它适用于快速筛选大数的素性，尤其适合于生成随机的大质数，例如生成安全的密钥。

4）Miller-Rabin 素性测试算法的详细介绍

Miller-Rabin 素性测试算法是一种概率型算法，可以在多项式时间内判断一个数是否为素数。

Miller-Rabin 素性测试算法基于费马小定理和二次探测定理。

费马小定理指出，如果是一个质数，是不被整除的整数，那么。因此，如果我们对于一个不被整除的随机整数，计算的结果为，那么可能是素数。

二次探测定理指出，如果是一个奇素数，是不被整除的整数，那么的充要条件是或者。因此，如果我们对于一个不被整除的随机整数，计算的结果为，那么可能是合数。如果结果不为但是为，那么可能是素数。

Miller-Rabin 素性测试算法的步骤如下：

对于一个奇数 n，可以将它表示为的形式，其中 s 和 d 都是正整数，d 是一个奇数。

选择随机整数 $，$ 。

计算，如果或者，则 n 是素数，进入下一轮测试；否则，进入步骤 4。

For to :
计算，如果，则 n 是素数，进入下一轮测试；否则，令

n不是素数，结束

该算法的时间复杂度为，其中 k 是测试的次数。Miller-Rabin测试的特点是错误素数的数量比应用费马和Solovay-Strasen测试的情况要少。该算法被广泛应用于实际中的素数测试。

举一个例子：

假设我们要测试数字是否为素数，我们选择进行测试：

首先，我们计算，即，使用快速幂算法可以得到。

然后，我们计算，即，使用快速幂算法可以得到。

因为且，所以不是素数。

接下来，我们可以选择另一个值进行测试，例如。计算，，因此我们可以认为是素数。

使用随机数一次判定其为素数并不能确定该数就是一个素数，此时我们将这个随机数称为“强伪证”。

下面是一个Miller-Rabin判定合数的例子，其中选取的就是一个“强伪证”：

假设221是我们需要检验的数，则

随机选取一个，使其满足，此处选择

因为, 所以要么确实是一个素数，要么是一个“强伪证”。

我们再选取l另一个随机数，于是有：

即是为合数的一个凭证，而是一个“强伪证”。

即221是一个合数

2 Miller-Rabin大素数判定的程序实现

使用Java及其自带库编写一个Miller-Rabin大素数判定程序：该程序接收一个输入数字，可以为大整数，将其进行50轮Miller-Rabin大素数判定测试，最终输出结果是素数prime或者合数composite

源码见附录，此处展示程序截图：

对于该算法，首先对小数进行测试：

可以看到，该Miller-Rabin素数判断程序对上述输入的数字进行判断的结果都是正确的。

接下来我们输入一个1024bits的大素数进行测试。

首先我们需要生成一个大素数，使用Java自带的SecureRandom类进行实现：指定生成大素数位数为1024bits

源码见附录，此处展示程序截图：

生成一个1024bits的大素数：

将这个大素数输入上面的Miller-Rabin素性检测程序：

程序成功判定这是一个大素数

程序性能分析

代码使用Java构建，Java支持大整数 BigIntegar类型，方便输入1024bits的大整数。同时，利用Java自带的随机数生成方法，可以很轻松的生成测试需要的随机整数。设置测试轮数k=50，可以实现准确性与性能的综合平衡。

四、研究结果及其分析

根据上面的研究，我们可以知道，Miller-Rabin 素性测试算法是一种快速可靠的素性测试算法，它可以用来判断一个大数是否是素数。相较于其它的几种素性测试方法，Miller-Rabin 素性测试算法具有更高的效率和更强的可靠性。它的理论基础是由Fermat定理引申而来，因此它具备了Fermat检测算法的优势，同时进一步降低了判断的错误率。因此，Miller-Rabin 素性测试算法被广泛应用于加密算法、密码学和数论等领域。

同时，在调研和测试过程中也获知了 Miller-Rabin 素性测试算法的一些优缺点：

优点：

时间复杂度比较低，仅为，其中为测试精度，为待测试的数。
可以通过控制测试精度来平衡算法的速度和准确性，使得算法可以在可接受的时间内得到可靠的结果。
在实际应用中，Miller-Rabin 素性测试算法的错误概率非常小，可以满足大多数实际需求。

缺点：

在极少数情况下，Miller-Rabin 素性测试算法可能会出现误判，即将一个合数误认为素数。不过这种情况的概率非常小，可以通过增加测试精度来进一步降低误判率。

在使用Java程序进行Miller-Rabin 素性测试时速度很快。同时，Java自带的随机素数生成类也使用了Miller-Rabin素性测试，使用Java自带的随机数生成类生成随机数时速度较快，即使是1024bits如此大的素数都可以在1秒内得到，这体现了Miller-Rabin素性测试的优越性和应用的广泛性。

当然，本次研究还有需要改进的地方，本次研究中使用的编程语言是Java，使用了Java中的大整数BigIntegar类，但是作为优化，使用整数范围没有最大值限制的Python语言可以使程序更加精简和易读，调用更少，处理速度更快，因此程序还可以使用Python编辑进行性能改进，改进的代码已附在附件中。

五、结论

研究结果表明，Miller-Rabin 素性测试算法是一种非常实用和有效的素性测试算法，尤其适用于对大数进行素性测试的场景，其速度快、正确率高。在实际应用中，我们需要根据具体需求来选择测试精度和算法参数，以平衡算法的准确性和速度。

本次研究解决的问题：本次研究基本完成任务，完成了题目的要求。本次研究中调查了常见的大素数判断算法，了解到了常见素数判定算法的基本原理和性能，以及各种算法的优劣。仔细调研了Miller-Rabin素判定原理并实际操作编程实现了Miller-Rabin的功能，深刻了解和认识了Miller-Rabin素判定原理。

本次研究说明的问题：设计程序时选择使用合适的编程语言可以大大提高解决问题的效率，未来笔者将在编写其它程序前将仔细思考此类问题，以提高自身的编程效率和程序的运行效率。

要进一步研究的问题：Miller-Rabin算法仍存在极少数情况无法正确判定的情况，未来笔者将学习更多的相关知识，寻求解决此办法的方案。

六、参考文献

[1]Goran Dordevic; Milan Markovic.”On Optimization of Miller-Rabin Primality Test on TI TMS320C54x Signal Processors”[R].International Conference on Systems, Signals and Image Processing, IWSSIP,27-30 June 2007

[2]M. O. Rabin.“Probabilistic algorithm for testing primality” [J]. Number Theory 12 (1980), 128–138.

[3]谢日敏.素数判定设计与实现[J].福建商业高等专科学校学报. 2007(02)

[4]许斌,张艳硕,吕正宏.常见素性检验算法的比较分析[J]北京电子科技学院学报. 2021,29(04)

七、附录

1 程序有关文件

见作业附带文件：

Miller-Rabin素判定程序：MillerRabinTest.java

随机1024bits大素数生成程序：RandomPrimeGenerator.java

使用Python优化的Miller-Rabin素判定程序：Miller-Rabin.py

2 程序源码

MillerRabinTest.java

import java.math.BigInteger;
import java.util.Random;
import java.util.Scanner;

public class MillerRabinTest {

    public static boolean isPrime(BigInteger n, int k) { //素数判定
        // 判断特殊情况：如果 n 小于等于 1 或者为偶数，则一定不是素数
        if (n.compareTo(BigInteger.ONE) <= 0 || n.mod(BigInteger.TWO).equals(BigInteger.ZERO)) {
            return false;
        }

        // 将 n - 1 分解为 d * 2^r 的形式
        BigInteger d = n.subtract(BigInteger.ONE);
        int r = 0;
        while (d.mod(BigInteger.TWO).equals(BigInteger.ZERO)) {
            d = d.divide(BigInteger.TWO);
            r++;
        }

        // 进行 k 次测试
        for (int i = 0; i < k; i++) {
            BigInteger a = getRandomNumberInRange(BigInteger.TWO, n.subtract(BigInteger.TWO));
            BigInteger x = a.modPow(d, n);

            if (x.equals(BigInteger.ONE) || x.equals(n.subtract(BigInteger.ONE))) {
                continue;
            }

            for (int j = 0; j < r - 1; j++) {
                x = x.modPow(BigInteger.TWO, n);
                if (x.equals(BigInteger.ONE)) {
                    return false;
                }
                if (x.equals(n.subtract(BigInteger.ONE))) {
                    break;
                }
            }

            if (!x.equals(n.subtract(BigInteger.ONE))) {
                return false;
            }
        }

        return true;
    }

    private static BigInteger getRandomNumberInRange(BigInteger min, BigInteger max) {//生成范围在[2,n-1)的随机数
        Random random = new Random();
        BigInteger range = max.subtract(min).add(BigInteger.ONE);
        BigInteger randomNum = new BigInteger(range.bitLength(), random);
        while (randomNum.compareTo(range) >= 0) {
            randomNum = new BigInteger(range.bitLength(), random);
        }
        return randomNum.add(min);
    }

    public static void main(String[] args) {//主方法
        Scanner in = new Scanner(System.in);
        String a;
        a = in.next();
        BigInteger n = new BigInteger(a);
        int k = 50;
        if (isPrime(n, k)) {
            System.out.println(n + " is prime.");
        } else {
            System.out.println(n + " is composite.");
        }
    }
}

RandomPrimeGenerator.java

public class RandomPrimeGenerator {

    private static final int BIT_LENGTH = 1024; // 生成的大素数位数
    private static final int CERTAINTY = 100;   // Miller-Rabin 素性测试的精度
    private static final SecureRandom random = new SecureRandom();

    public static void main(String[] args) {
        BigInteger prime = generateRandomPrime();
        System.out.println("Generated prime: " + prime);
    }

    public static BigInteger generateRandomPrime() {
        BigInteger prime;
        do {
            prime = new BigInteger(BIT_LENGTH, CERTAINTY, random);
        } while (!prime.isProbablePrime(CERTAINTY));
        return prime;
    }
}

Miller-Rabin.py

# -*- coding: utf-8 -*-
import random


def is_prime(n, k):
    if n <= 1:
        return False
    if n <= 3:
        return True
    d = n - 1
    r = 0
    while d % 2 == 0:
        d //= 2
        r += 1
    for _ in range(k):
        a = random.randint(2, n - 2)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True


n = input()
n = int(n)
k = 50  # 测试精度
if is_prime(n, k):
    print("{} is prime".format(n))
else:
    print("{} is composite".format(n))