Miller-Rabin質(zhì)數(shù)測(cè)試算法是一種基于隨機(jī)化的算法，用于判斷一個(gè)數(shù)是否為質(zhì)數(shù)。該算法具有高效性和強(qiáng)健性，通常被用于加密算法中生成大素?cái)?shù)。

該算法基于以下兩個(gè)事實(shí)：對(duì)于質(zhì)數(shù)$p$和任意整數(shù)$a$，有$a^{p?1}\equiv 1(\mathrm{mod}p)$；對(duì)于任意整數(shù)$n$，如果$n$不是質(zhì)數(shù)，則$n?1$可以表示為$2^{r}d$的形式，其中$r\ge 1$，$d$是奇數(shù)。因此，我們可以選擇一個(gè)隨機(jī)整數(shù)$a$，計(jì)算$a^d,a^{2d},\dots ,a^{2^{r?1}d}$，如果其中任何一個(gè)模$n$等于$1$，或者等于$n?1$，則$n$可能是質(zhì)數(shù)；否則，$n$一定不是質(zhì)數(shù)。

由于Miller-Rabin質(zhì)數(shù)測(cè)試算法具有高效性和強(qiáng)健性，通常被用于生成大素?cái)?shù)，特別是在RSA等加密算法中。在實(shí)際應(yīng)用中，一般會(huì)對(duì)該算法進(jìn)行多次迭代，以增加正確性的概率。

import randomdef is_prime(n, k=5):# 如果 n <= 1，則返回 Falseif n <= 1:return False# 檢查 n 是否等于小于 100 的質(zhì)數(shù)small_primes = [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]if n in small_primes:return Truefor p in small_primes:if n % p == 0:return False# 找到 r 和 d 以滿足 n-1 = 2^r * dr, d = 0, n-1while d % 2 == 0:r += 1d //= 2# 進(jìn)行 k 次測(cè)試for i in range(k):a = random.randint(2, n-2)x = pow(a, d, n)if x == 1 or x == n-1:continuefor j in range(r-1):x = pow(x, 2, n)if x == n-1:breakelse:return Falsereturn Truedef generate_prime_number(length):while True:# 生成一個(gè)長(zhǎng)度為 length 的隨機(jī)奇數(shù)num = random.getrandbits(length)num |= (1 << length - 1) | 1# 檢查 num 是否為質(zhì)數(shù)if is_prime(num):return numprint(generate_prime_number(2048))

該代碼中的is_prime函數(shù)實(shí)現(xiàn)了Miller-Rabin質(zhì)數(shù)測(cè)試算法。函數(shù)接受兩個(gè)參數(shù)，n表示要測(cè)試的數(shù)，k表示測(cè)試次數(shù)。該函數(shù)首先檢查n是否小于等于1，或者是否能夠被小于100的質(zhì)數(shù)整除。如果n不滿足這些條件，就找到一個(gè)r和d，使得$n?1=2^r?d$。然后，它對(duì)于$k$個(gè)隨機(jī)的整數(shù)$a$執(zhí)行Miller-Rabin測(cè)試。如果對(duì)于所有的測(cè)試$a$都有$x=1$或$x=n?1$，則n很可能是一個(gè)質(zhì)數(shù)。如果對(duì)于任何一個(gè)$a$，都有$x\ne 1$且$x\ne n?1$，則n不是質(zhì)數(shù)。如果在所有測(cè)試中都沒(méi)有發(fā)現(xiàn)n不是質(zhì)數(shù)的證據(jù)，則n很可能是一個(gè)質(zhì)數(shù)。

generate_prime_number函數(shù)生成一個(gè)長(zhǎng)度為length的隨機(jī)奇數(shù)，然后檢查它是否為質(zhì)數(shù)。如果是，就返回它；否則，就