Solovay-Strassen及Miller-Rabin算法改进后的代码

以下是Solovay-Strassen算法和Miller-Rabin算法改进后的Python代码：

#### Solovay-Strassen算法改进版

import random
from math import gcd

def legendre(a, p):
    if a == 0:
        return 0
    if a == 1:
        return 1
    if a % 2 == 0:
        return legendre(a // 2, p) * pow(-1, ((p * p - 1) // 8))
    else:
        return legendre(p % a, a) * pow(-1, ((a - 1) * (p - 1) // 4))

def solovay_strassen(n, k=10):
    if n == 2 or n == 3:
        return True
    if n < 2 or n % 2 == 0:
        return False
    for i in range(k):
        a = random.randint(2, n - 1)
        x = legendre(a, n)
        if x == 0 or pow(a, (n - 1) // 2, n) != x % n:
            return False
    return True

#### Miller-Rabin算法改进版

import random
from math import gcd

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

这里的k表示进行测试的次数，一般取10次即可满足大部分情况的需求。