密碼學(xué)第7章公鑰密碼算法與數(shù)字簽名算法-閱讀頁
2024-08-24 20:00本頁面
【正文】 設(shè) p是素數(shù)， a是任一正整數(shù)，則 ap≡a mod p。若 n是素數(shù)，則顯然有 φ(n)=n1。Euler定理 若 a和 n互素，則 aφ(n)≡1 mod n。對于大數(shù)的素性檢驗來說沒有簡單直接的方法。引理的逆否命題為：如果方程 x2≡1 mod p有一解 x0? {1,1}， 那么 p不為素數(shù)。 9. 歐幾里得算法173。而推廣的 Euclid算法不僅可求兩個正整數(shù)的最大公因子，而且當(dāng)兩個正整數(shù)互素時，還可求出其中一個數(shù)關(guān)于另一個數(shù)的模乘逆元。 數(shù)論 歐幾里得算法 —— 求最大公因子可假定算法的輸入是兩個正整數(shù)，設(shè)為 d， f，并設(shè) f d。 Y←d ；2. if Y=0 then return X=gcd(f,d)；3. R=X mod Y；4. X=Y；5. Y=R；6. goto 2。(Y1,Y2,Y3)←(0,1,d)。3. if Y3=1 then return Y3=gcd(f, d)； Y2=d1 mod f。6. (X1,X2,X3)←(Y1,Y2,Y3)。8. goto 2
物理相關(guān)推薦
鄂ICP備17016276號-1