[工學(xué)]信息安全技術(shù)chapter6公鑰密碼學(xué)和ras算法-文庫吧
2025-09-19 23:46 本頁面
【正文】 p = 1時，a2 mod p =1 。 ? 性質(zhì) 2：設(shè) p是大于 2的素數(shù)，有 p1=2kq, k0,q為奇數(shù)。設(shè) a是整數(shù)，且 1ap1，則下面兩個條件必有一個成立： – aq模 p和 1同余。 –整數(shù) aq, a2q,….., a2k1q里存在一個數(shù)，模 p時和1同余。 MillerRabin算法 ? a test based on Fermat’s Theorem ? algorithm is: TEST (n) is: 1. Find integers k, q, k 0, q odd, so that (n–1)=2kq 2. Select a random integer a, 1an–1 3. if aq mod n = 1 then return (―maybe prime)。 4. for j = 0 to k – 1 do 5. if (a2jq mod n = n1) then return( maybe prime ) 6. return (posite) MillerRabin算法 ? 如何利用 MillerRabin算法確定某整數(shù)是或不是素數(shù)，并且要有很高的可信度？ – 對隨機(jī)選取的 a，重復(fù)調(diào)用 TEST(n)，如果某時刻 TEST返回“合數(shù)”，則 n一定不是素數(shù)；若 n為非素奇數(shù)，則 TEST返回不確定的概率小于 1/4。若 TEST連續(xù) t次返回“不確定”，則 n是素數(shù)的概率至少是 14t。 ? 隨機(jī)選取大素數(shù)的難度？也即需要進(jìn)行多少次素性測試以找到一個素數(shù)？ – 素數(shù)定理： n附近的素數(shù)分布情況為，平均每 ln(n)個整數(shù)中有一個素數(shù)。需測試的整數(shù)個數(shù)約為 (n)。另，素數(shù)的分布沒有確定的規(guī)律。 AKS算法 ? 2021年， Agrawal， Kayal和 Saxena設(shè)計 ? 該算法是多項式時間的確定算法 ? 運(yùn)算時間 O((log n)^12) ? 改善現(xiàn)代密碼系統(tǒng)的安全性 改進(jìn)算法： ? AKS－ Berrizbeitia算法，復(fù)雜度 O((log n)^6) ? AKS－ Bernstein算法，復(fù)雜度 O((log n)^4) AKS算法 離散對數(shù) ? 作用？ ? 使得 am≡1 (mod n)成立的最小正冪為 m。此時，稱 m為： – a模 n的階 – a所產(chǎn)生的周期長 – a所屬的模 n的指數(shù) ? 本原根 ? 若 a是 n的本原根，則 a的 1到 Φ(n)次冪的模 n各不相同的，且均與 n互素。 ? 當(dāng) p為素數(shù)時， 若 a是 n的本原根 a的 1到 (p1)次冪的模 p各不相同的。 a : primitive root 模 19的整數(shù)冪 離散對數(shù) ? 離散對數(shù)的定義 – 對于
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1