資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學資訊安全中的素性測試是什麼？
素性測試是一種確定輸入數字是否為素數的演算法。一些素性測試是確定性的。它們總是能夠正確地判斷一個數字是素數還是合數。
已知最快的確定性素性測試演算法發明於2004年。三位計算機科學家，Agrawal、Kayal和Saxena發明了AKS素性測試，其執行時間為O˜ (log(n)6 )，其中O˜ (f(n))表示為O(f(n).log(f(n))k)，k為某個整數[1]。雖然這是一個重大突破，但與資訊安全的要求相比，這個速度相當慢。
素數的優勢在於它們被用於密碼學。其中一種標準密碼系統——RSA演算法需要素數作為金鑰，通常超過1024位以提供更高的安全性。
處理如此大的數字時，這種方法肯定不好用。處理如此大的數字並不容易，尤其是在素性測試期間執行/和%運算時。
因此，目前產生的最佳素性測試演算法只能判斷提供的數字是“可能的素數”還是合數。
素性測試主要有以下幾種型別：
**確定性演算法** - 確定性素性測試演算法接受一個整數並始終輸出素數或合數。該演算法總是給出正確的答案。
**可分性演算法** - 最簡單的素性測試如下：
給定輸入數字n，檢查從2到n-1的任何整數是否能整除n。如果n能被任何m整除，則n是合數；否則，n是素數。但是，不必測試所有m直到n-1，只需要測試到√n即可。如果n是合數，則它可以分解為兩個值，其中至少一個應該小於或等於√n。
**機率演算法** - 機率演算法提供的答案大多數情況下是正確的，但並非所有情況下都是正確的。這些測試確定n是否滿足所有素數都應滿足的一個或多個條件。機率演算法返回素數或合數取決於以下規則：
如果待測試整數實際上是素數，則演算法肯定返回素數。
如果待測試整數實際上是合數，則它以1 − ε的機率返回合數，但它也可能以ε的機率返回素數。如果可以執行該演算法'm'次，則錯誤機率可以降低到Σm。
**費馬素性測試** - 費馬素性測試源於費馬小定理，該定理指出，如果n是素數，則an−1 ≡ 1 (mod n)。給定輸入n和a < n，可以檢查an−1 ≡ 1 (mod n)是否成立。如果不成立，則n是合數；如果成立，則n可能是素數。不幸的是，費馬素性測試的錯誤率很高，許多合數都被認為可能是素數。
6K+ 瀏覽量
