Can you summarize the following document?
        
  首先介紹一個相關的引理。我們發現formula_1 和 formula_2總是得到 formula_3,我們稱-1和1是formula_4的“平凡平方根”,當formula_5是素數且formula_6時,不存在formula_4 的“非平凡平方根”。為了證明該引理,首先假設formula_8是formula_4的平凡平方根,於是有  formula_10  formula_11  也就是說,素數 formula_5 能夠整除 formula_13 或者formula_14,根據歐幾里得引理,formula_15 或者 formula_16能夠被 formula_5 整除,即 formula_18 或 formula_19,  即 formula_8 是 formula_4 的平凡平方根。  現在假設formula_22是一個素數,且 formula_23。於是formula_24是一個偶數,可以被表示為formula_25 的形式,formula_26和formula_27都是正整數且formula_27是奇數。對任意在formula_29 範圍內的 formula_30 和formula_31,必滿足以下兩種形式的一種:  formula_32 formula_33  因為由於 費馬小定理,對於一個素數formula_22,有  formula_35  又由於上面的引理,如果我們不斷對formula_36取平方根後,我們總會得到 1 或 -1。如果我們得到了 -1,意味著2式成立,formula_22 是一個素數。如果我們從未得到 -1,那麼通過這個過程我們已經取遍了所有2的冪次,即1式成立。  米勒-拉賓素性測試就是基於上述原理的逆否,也就是說,如果我們能找到這樣一個 formula_30,使得對任意formula_31以下兩個式子均滿足:  formula_40formula_41那麼 formula_22 就不是一個素數。這樣的 formula_30 稱為 formula_22 是合數的一個憑證(witness)。否則 formula_30 可能是一個證明 formula_22 是素數的“強偽證”(strong liar),即當formula_22確實是一個合數,但是對當前選取的 formula_30 來說上述兩個式子均不滿足,這時我們認為formula_22是基於formula_30的大概率素數。  每個奇合數 formula_22 都有很多個對應的憑證 formula_30,但是要生成這些 formula_30 並不容易。當前解決的辦法是使用概率性的測試。我們從集合formula_29中隨機選擇非零數 formula_30,然後檢測當前的 formula_30 是否是 formula_22 為合數的一個憑證。如果 formula_22 本身確實是一個合數,那麼大部分被選擇的 formula_30 都應該是 formula_22 的憑證,也即通過這個測試能檢測出 formula_22 是合數的可能性很大。然而,仍有極小概率的情況下我們找到的 formula_30 是一個“強偽證”(反而表明了 formula_22 可能是一個素數)。通過多次獨立測試不同的 formula_30,我們能減少這種出錯的概率。  對於測試一個大數是否是素數,常見的做法隨機選取基數formula_30,畢竟我們並不知道憑證和偽證在formula_66這個區間如何分佈。典型的例子是 Arnault 曾經給出了一個397位的合數formula_22,但是所有小於307的基數formula_30都是formula_22是素數的“強偽證”。不出所料,這個大合數通過了 Maple 程式的codice_1 函式(被判定為素數)。這個函式通過檢測 formula_70 這幾種情況來進行素性檢驗。

  假設我們需要檢驗 formula_71 是否是一個素數。首先formula_72,於是我們得到了formula_73和formula_74.我們隨機從formula_75中選取formula_30,假設formula_77,於是有:  formula_78formula_79因為我們得到了一個 -1,所以要麼formula_71確實是一個素數,要麼formula_77是一個“強偽證”。我們再選取formula_82,於是有:  formula_83formula_84即formula_82是formula_71為合數的一個憑證,而formula_77是一個“強偽證”。  選取特定的整數可以在一定範圍內確定(而非單純基於概率猜測)某個整數是質數還是合數。對於小於formula_88的情形,選取formula_89共三個憑據可以做到這一點;對於小於formula_90的情形,選取formula_91共七個憑據可以做到這一點。

  這一演算法可以被表示成如下虛擬碼:  使用,這個演算法的時間複雜度是formula_92,formula_93是我們測試的不同的 formula_30 的值。也就是說,這是一個高效的多項式時間演算法。使用快速傅立葉變換能夠將這個時間推進到 O("k" log"n" log log "n" log log log "n") = Õ("k" log"n").  如果我們加入最大公因數演算法到上述演算法中,我們有時候可以得到 formula_22 的因數,而不僅僅是證明 formula_22 是一個合數。例如,若 formula_22 是一個基於formula_30 的可能的素數,但不是一個大概率素數,則formula_99或formula_100將得到 formula_22 的因數。如果因式分解是必要的,這一formula_102演算法可以加入到上述的演算法中,代價是增加了一些額外的運算時間。  例如,假設 formula_103,則formula_104.於是formula_105,這也告訴我們 formula_22 不是一個大概率素數,即 formula_22 是一個合數。如果這個時候我們求最大公因數,我們可以得到一個formula_103的因數:formula_109.這時可行的,因為formula_103是一個基於2的偽素數,但不是一個“強偽素數”。

  下面是根據以上定義而使用Magma語言編寫的“米勒-拉賓”檢驗程式。
米勒-拉賓質數判定法是一種質數判定法則,利用隨機化演算法判斷一個數是合數還是"可能是"素數。卡內基梅隆大學的計算機系教授Gary Lee Miller首先提出了基於廣義黎曼猜想的確定性演算法,由於廣義黎曼猜想並沒有被證明,其後由以色列耶路撒冷希伯來大學的Michael O. Rabin教授作出修改,提出了不依賴於該假設的隨機化演算法。