關于什么是RSA成福，可以查看這篇文章, 今天主要是講一下RSA底層用的一些算法原理棉姐，其實都是一些數(shù)學概念，誰讓RSA算法是三個數(shù)學家發(fā)明的没佑。
互質關系
如果兩個整數(shù)（或者兩個以上的整數(shù)）的最大公約數(shù)是1鸵赖，則稱他們?yōu)?a target="_blank" rel="nofollow">互質务漩。也就是說兩個整數(shù)，除了1以外它褪，沒有其它的最大公約數(shù)了饵骨，這兩個整數(shù)就叫做互質關系。
比如說7列赎，11他們的最大公約數(shù)只有1宏悦，所以他們互質镐确；8包吝，10他們的最大公約數(shù)為1，2源葫，所以這兩數(shù)不是互質關系诗越。
歐拉函數(shù)
歐拉函數(shù)φ(n)是小于或等于n的正整數(shù)中與n互質的數(shù)的數(shù)目，稱為歐拉函數(shù)
比如說當n=8時息堂，與8能形成互質關系的數(shù)有4個嚷狞，分別是1块促，3，5床未，7竭翠，所以φ(8)=4
具體φ(n)函數(shù)的計算公式，可以分為以下四種情況：
情況一： 當n=1薇搁，φ(1)=1
因為1與任何整數(shù)都是互質關系斋扰，所以當n=1時，φ(1)=1
情況二：當n為質數(shù)啃洋，φ(n)=n-1
因為質數(shù)與小于它的每一個數(shù)传货，都構成互質關系，所以當n為質數(shù)時宏娄，φ(n)=n-1 问裕。
比如說n=3時，1孵坚，2都跟他是互質關系粮宛， n=7時，1卖宠，2窟勃，3，4逗堵，5秉氧，6都跟他是互質關系。
情況三：n = p^k (p為質數(shù)蜒秤，k為指數(shù)汁咏，且大于等于1)，n是質數(shù)的k次方作媚，則φ(p^k) = p^k - p^(k-1) = p^k（1 - 1/p）
比如：φ(8) = φ(2^3) = 2^3 - 2^2 = 4
φ(27) = φ(3^3) = 3^3(1 - 1/3) = 18
情況四： n是兩個互質的整數(shù)之積攘滩，如：n = p1 * p1，則 φ(n) = φ(p1p2) = φ(p1)φ(p2)
比如：φ(56)=φ(8×7)=φ(8)×φ(7)=4×6=24
情況五：歐拉函數(shù)通式：[圖片上傳失敗...(image-5f0fb9-1523323180027)]
其展開式為： [圖片上傳失敗...(image-5d9beb-1523323180027)]%3Dn(1-%5Cfrac%7B1%7D%7Bp_%7B1%7D%7D)(1-%5Cfrac%7B1%7D%7Bp_%7B2%7D%7D)...(1-%5Cfrac%7B1%7D%7Bp_%7Br%7D%7D)&chs=60)
比如纸泡，用通式計算72的歐拉函數(shù)為：[圖片上傳失敗...(image-58676a-1523323180027)]
1323的歐拉函數(shù)為：[圖片上傳失敗...(image-68ae5e-1523323180027)]%3D%5Cphi(3%5E%7B3%7D%5Ctimes7%5E%7B2%7D)%3D1323(1-%5Cfrac%7B1%7D%7B3%7D)(1-%5Cfrac%7B1%7D%7B7%7D)%3D756&chs=60)
同余定理
給定一個正整數(shù)n漂问，如果兩個整數(shù)a和b滿足a-b能夠被n整除，即(a-b)/n得到一個整數(shù)女揭，那么就稱整數(shù)a與b對模n同余蚤假，記作a≡b(mod n)。這就是同余定理吧兔。
例如：26≡2(mod 12)磷仰， 26%12 余2， 2%12余2境蔼， 26-2/12 = 0灶平，所以26與2對模12同余
歐拉定理
在數(shù)論中伺通，歐拉定理是一個關于同余的性質,其性質如下：
若n,a為正整數(shù)，且n,a互質逢享，則: [圖片上傳失敗...(image-eb8acd-1523323180027)]
首先看一個基本的例子罐监，令a = 3, n = 5
