麻省理工演算法公式

1. 天才少女中的數學公式叫什麼

天才少女中的數學公式叫N-S方程。

N-S方程全稱「納維－斯托克斯方程」，原始形式在1827年被Navier提出，經過發展，在1845年由Stokes提出最終的形式。劇中外婆伊芙琳憑借探視權帶瑪麗去了麻省理工，讓教授出題考瑪麗，她要親自確認瑪麗是否真的是數學天才，就出了這個題目，最終瑪麗解出了題。

N-S方程的影響及意義：

N-S方程反映了粘性流體（又稱真實流體）流動的基本力學規律，在流體力學中有十分重要的意義。

它是一個非線性偏微分方程，求解非常困難和復雜，在求解思路或技術沒有進一步發展和突破前只有在某些十分簡單的特例流動問題上才能求得其精確解；但在部分情況下，可以簡化方程而得到近似解。

例如當雷諾數時，繞流物體邊界層外，粘性力遠小於慣性力，方程中粘性項可以忽略，N-S方程簡化為理想流動中的歐拉方程；而在邊界層內，N-S方程又可簡化為邊界層方程，等等。在計算機問世和迅速發展以來，N-S方程的數值求解才有了較大的發展。

2. 用RSA對下列數據實現加密和解密:

拜託:老大,你的家庭作業也來問?
你自己學吧:下面是課文^
RSA加密演算法
該演算法於1977年由美國麻省理工學院MIT(Massachusetts Institute of Technology)的Ronal Rivest，Adi Shamir和Len Adleman三位年輕教授提出，並以三人的姓氏Rivest，Shamir和Adlernan命名為RSA演算法。該演算法利用了數論領域的一個事實，那就是雖然把兩個大質數相乘生成一個合數是件十分容易的事情，但要把一個合數分解為兩個質數卻十分困難。合數分解問題目前仍然是數學領域尚未解決的一大難題，至今沒有任何高效的分解方法。與Diffie-Hellman演算法相比，RSA演算法具有明顯的優越性，因為它無須收發雙方同時參與加密過程，且非常適合於電子函件系統的加密。

RSA演算法可以表述如下：

(1) 密鑰配製。假設m是想要傳送的報文，現任選兩個很大的質數p與q，使得：

(12-1)；

選擇正整數e，使得e與(p－1)(q－1)互質；這里(p－1)(q－1)表示二者相乘。再利用輾轉相除法，求得d，使得：

(12-2)；

其中x mod y是整數求余運算，其結果是x整除以y後剩餘的余數，如5 mod 3 = 2。

這樣得：

(e，n)，是用於加密的公共密鑰，可以公開出去；以及

(d，n)，是用於解密的專用鑰匙，必須保密。

(2) 加密過程。使用(e，n)對明文m進行加密，演算法為：

(12-3)；

這里的c即是m加密後的密文。

(3) 解密過程。使用(d，n)對密文c進行解密，演算法為：

(12-4)；

求得的m即為對應於密文c的明文。

RSA演算法實現起來十分簡捷，據說英國的一位程序員只用了3行Perl程序便實現了加密和解密運算。

RSA演算法建立在正整數求余運算基礎之上，同時還保持了指數運算的性質，這一點我們不難證明。例如：

(12-5)；

(12-6)。

RSA公共密鑰加密演算法的核心是歐拉(Euler)函數ψ。對於正整數n，ψ(n)定義為小於n且與n互質的正整數的個數。例如ψ(6) = 2，這是因為小於6且與6互質的數有1和5共兩個數；再如ψ(7) = 6，這是因為互質數有1，2，3，5，6共6個。

歐拉在公元前300多年就發現了ψ函數的一個十分有趣的性質，那就是對於任意小於n且與n互質的正整數m，總有mψ(n) mod n = 1。例如，5ψ(6) mod 6 = 52 mod 6= 25 mod 6 =1。也就是說，在對n求余的運算下，ψ(n)指數具有周期性。

當n很小時，計算ψ(n)並不難，使用窮舉法即可求出；但當n很大時，計算ψ(n)就十分困難了，其運算量與判斷n是否為質數的情況相當。不過在特殊情況下，利用ψ函數的兩個性質，可以極大地減少運算量。

性質1：如果p是質數，則ψ(p) = (p－1)。

性質2：如果p與q均為質數，則ψ(p·q) = ψ(p)·ψ(q) = (p－1)(q－1)。

RSA演算法正是注意到這兩條性質來設計公共密鑰加密系統的，p與q的乘積n可以作為公共密鑰公布出來，而n的因子p和q則包含在專用密鑰中，可以用來解密。如果解密需要用到ψ(n)，收信方由於知道因子p和q，可以方便地算出ψ(n) = (p－1)(q－1)。如果竊聽者竊得了n，但由於不知道它的因子p與q，則很難求出ψ(n)。這時，竊聽者要麼強行算出ψ(n)，要麼對n進行因數分解求得p與q。然而，我們知道，在大數范圍內作合數分解是十分困難的，因此竊密者很難成功。

有了關於ψ函數的認識，我們再來分析RSA演算法的工作原理：

(1) 密鑰配製。設m是要加密的信息，任選兩個大質數p與q，使得 ；選擇正整數e，使得e與ψ(n) = (p－1)(q－1)互質。

利用輾轉相除法，計算d，使得ed mod ψ(n) = ，即ed = kψ(n) +1，其中k為某一正整數。

公共密鑰為(e，n)，其中沒有包含任何有關n的因子p和q的信息。

專用密鑰為(d，n)，其中d隱含有因子p和q的信息。

(2) 加密過程。使用公式(12-3)對明文m進行加密，得密文c。

(3) 解密過程。使用(d，n)對密文c進行解密，計算過程為：

cd mod n = (me mod n)d mod n

= med mod n

= m(kψ(n) + 1) mod n

= (mkψ(n) mod n)·(m mod n)

= m

m即為從密文c中恢復出來的明文。

例如，假設我們需要加密的明文代碼信息為m = 14，則：

選擇e = 3，p = 5，q = 11；

計算出n = p·q = 55，(p－1)(q－1) = 40，d = 27；

可以驗證：(e·d) mod (p－1)(q－1) = 81 mod 40 = 1；

加密：c = me mod n = 143 mod 55 = 49；

解密：m = cd mod n = 4927 mod 55 = 14。

關於RSA演算法，還有幾點需要進一步說明：

(1) 之所以要求e與(p－1)(q－1)互質，是為了保證 ed mod (p－1)(q－1)有解。

(2) 實際操作時，通常先選定e，再找出並確定質數p和q，使得計算出d後它們能滿足公式(12-3)。常用的e有3和65537，這兩個數都是費馬序列中的數。費馬序列是以17世紀法國數學家費馬命名的序列。

(3) 破密者主要通過將n分解成p·q的辦法來解密，不過目前還沒有辦法證明這是唯一的辦法，也可能有更有效的方法，因為因數分解問題畢竟是一個不斷發展的領域，自從RSA演算法發明以來，人們已經發現了不少有效的因數分解方法，在一定程度上降低了破譯RSA演算法的難度，但至今還沒有出現動搖RSA演算法根基的方法。

(4) 在RSA演算法中，n的長度是控制該演算法可靠性的重要因素。目前129位、甚至155位的RSA加密勉強可解，但目前大多數加密程序均採用231、308甚至616位的RSA演算法，因此RSA加密還是相當安全的。

據專家測算，攻破512位密鑰RSA演算法大約需要8個月時間；而一個768位密鑰RSA演算法在2004年之前無法攻破。現在，在技術上還無法預測攻破具有2048位密鑰的RSA加密演算法需要多少時間。美國Lotus公司懸賞1億美元，獎勵能破譯其Domino產品中1024位密鑰的RSA演算法的人。從這個意義上說，遵照SET協議開發的電子商務系統是絕對安全的。

3. de=1modφ(n)是什麼意思

在RSA演算法中，de=1modφ(n)是指de與1關於φ(n)同餘。

對極大整數做因數分解的難度決定了RSA演算法的可靠性。對一極大整數做因數分解愈困難，RSA演算法愈可靠。

假如有人找到一種快速因數分解的演算法的話，那麼用RSA加密的信息的可靠性就肯定會極度下降。但找到這樣的演算法的可能性是非常小的。

只有短的RSA鑰匙才可能被強力方式解破。世界上還沒有任何可靠的攻擊RSA演算法的方式。只要其鑰匙的長度足夠長，用RSA加密的信息實際上是不能被解破的。

(3)麻省理工演算法公式擴展閱讀：

由於RSA演算法基於大數分解（無法抵抗窮舉攻擊），因此在未來量子計算能對RSA演算法構成較大的威脅。

一個擁有N量子比特的量子計算機，每次可進行2^N次運算，理論上講，密鑰為1024位長的RSA演算法，用一台512量子比特位的量子計算機在1秒內即可破解。

1983年麻省理工學院在美國為RSA演算法申請了專利。這個專利2000年9月21日失效。由於該演算法在申請專利前就已經被發表了，在世界上大多數其它地區這個專利權不被承認。

4. RSA演算法詳解

總括： 本文詳細講述了RSA演算法詳解，包括內部使用數學原理以及產生的過程。

相濡以沫。到底需要愛淡如水。

之前寫過一篇文章 SSL協議之數據加密過程 ，裡面詳細講述了數據加密的過程以及需要的演算法。SSL協議很巧妙的利用對稱加密和非對稱加密兩種演算法來對數據進行加密。這篇文章主要是針對一種最常見的非對稱加密演算法——RSA演算法進行講解。其實也就是對私鑰和公鑰產生的一種方式進行描述。首先先來了解下這個演算法的歷史：

RSA是1977年由 羅納德·李維斯特 （Ron Rivest）、 阿迪·薩莫爾 （Adi Shamir）和 倫納德·阿德曼 （Leonard Adleman）一起提出的。當時他們三人都在 麻省理工學院 工作。RSA就是他們三人姓氏開頭字母拼在一起組成的。

但實際上，在1973年，在英國政府通訊總部工作的數學家 克利福德·柯克斯 （Clifford Cocks）在一個內部文件中提出了一個相同的演算法，但他的發現被列入機密，一直到1997年才被發表。

所以誰是RSA演算法的發明人呢？不好說，就好像貝爾並不是第一個發明電話的人但大家都記住的是貝爾一樣，這個地方我們作為旁觀者倒不用較真，重要的是這個演算法的內容：

RSA演算法用到的數學知識特別多，所以在中間介紹這個演算法生成私鑰和公鑰的過程中會穿插一些數學知識。生成步驟如下：

隨意選擇兩個大的質數p和q，p不等於q，計算N=p*q;

什麼是質數?我想可能會有一部分人已經忘記了，定義如下：

比如2，3，5，7這些都是質數，9就不是了，因為3*3=9了

r = φ(N) = φ(p)φ(q) = (p-1)(q-1) 。

這里的數學概念就是什麼是歐拉函數了，什麼是歐拉函數呢？

歐拉函數 的定義：

互質 的定義：

例如： φ(8) = 4 ，因為 1,3,5,7 均和 8 互質。

推導歐拉函數:

（1）如果 n = 1 , φ(1) = 1 ；(小於等於1的正整數中唯一和1互質的數就是1本身)；

（2）如果 n 為質數， φ(n) = n - 1 ；因為質數和每一個比它小的數字都互質。比如5，比它小的正整數1,2,3,4都和他互質；

(3) 如果 n 是 a 的 k 次冪，則 φ(n) = φ(a^k) = a^k - a^(k-1) = (a-1)a^(k-1) ；

(4) 若 m , n 互質，則 φ(mn) = φ(m)φ(n)

證明： 設 A , B , C 是跟 m , n , mn 互質的數的集，據 中國剩餘定理 (經常看數學典故的童鞋應該了解，剩餘定理又叫韓信點兵，也叫孫子定理)， A * B 和 C 可建立雙射一一對應)的關系。（或者也可以從初等代數角度給出 歐拉函數積性的簡單證明 ） 因此的φ(n)值使用 算術基本定理 便知。（來自維基網路）

選擇一個小於r並與r互質的整數e，求得e關於r的模反元素，命名為 d （ ed = 1(mod r) 模反元素存在，當且僅當e與r互質）， e 我們通常取65537。

模反元素：

比如 3 和 5 互質， 3 關於 5 的模反元素就可能是2，因為 3*2-1=5 可以被5整除。所以很明顯模反元素不止一個，2加減5的整數倍都是3關於5的模反元素 {...-3, 2,7,12…} 放在公式里就是 3*2 = 1 (mod 5)

上面所提到的歐拉函數用處實際上在於歐拉定理：

歐拉定理：

歐拉定理就可以用來證明模反元素必然存在。

由模反元素的定義和歐拉定理我們知道， a 的 φ(n) 次方減去1，可以被n整除。比如，3和5互質，而 5 的歐拉函數 φ(5) 等於4，所以 3 的 4 次方 (81) 減去1，可以被 5 整除（ 80/5=16 ）。

小費馬定理：

此時我們的 (N , e) 是公鑰， (N, d) 為私鑰，愛麗絲會把公鑰 (N, e) 傳給鮑勃，然後將 (N, d) 自己藏起來。一對公鑰和私鑰就產生了，然後具體的使用方法呢？請看： SSL協議之數據加密過程詳解

我們知道像RSA這種非對稱加密演算法很安全，那麼到底為啥子安全呢？
我們來看看上面這幾個過程產生的幾個數字：

N 和 e 我們都會公開使用，最為重要的就是私鑰中的 d ， d 一旦泄露，加密也就失去了意義。那麼得到d的過程是如何的呢？如下:

所以得出了在上篇博客說到的結論，非對稱加密的原理：

將a和b相乘得出乘積c很容易，但要是想要通過乘積c推導出a和b極難。即對一個大數進行因式分解極難

目前公開破譯的位數是768位，實際使用一般是1024位或是2048位，所以理論上特別的安全。

RSA演算法的核心就是歐拉定理，根據它我們才能得到私鑰，從而保證整個通信的安全。