rho演算法

① c++分解質因數求教（時間復雜度一定要優秀！）

1. 「分解質因數」定義：每個合數都可以寫成幾個質數相乘的形式，其中每個質數都是這個合數的因數，把一個合數用質因數相乘的形式表示出來，叫做分解質因數，如30 = 2 × 3 × 5。質數是指在大於1的自然數中，除了1和它本身以外不再有其他因數的自然數，1 既不是質數也不是合數。

2. 簡單思路：先從n=2，3，4...開始，跟合數m取余，如果n能被m除盡，n就是m的因數，然後m = m / n，繼續分解m剩下的部分。不用擔心n增加後，n=4之類的合數也能被m除盡，因為每次都是先從2，3...開始的，跟後面4，6之類的合數取余為0的合數，跟2，3取餘一定能是0。n為1的時候，就跳出求解邏輯。這種方法不一定是最快的，但卻是最容易理解。

3. 代碼示例：

   int n = 1000;

   //1不是質數

   while (n > 1) {

   for (int i = 2; i <= n; i++) {

   if (n % i == 0) {

   cout << i << endl;

   n /= i;

   break;

   }

   }

   }

   結果：2 2 2 5 5 5

② 橢圓加密演算法的公鑰密碼系統的加密演算法ECC與RSA的對比

第六屆國際密碼學會議對應用於公鑰密碼系統的加密演算法推薦了兩種：基於大整數因子分解問題（IFP）的RSA演算法和基於橢圓曲線上離散對數計算問題（ECDLP）的ECC演算法。RSA演算法的特點之一是數學原理簡單、在工程應用中比較易於實現，但它的單位安全強度相對較低。目前用國際上公認的對於RSA演算法最有效的攻擊方法--一般數域篩(NFS)方法去破譯和攻擊RSA演算法，它的破譯或求解難度是亞指數級的。ECC演算法的數學理論非常深奧和復雜，在工程應用中比較難於實現，但它的單位安全強度相對較高。用國際上公認的對於ECC演算法最有效的攻擊方法--Pollard rho方法去破譯和攻擊ECC演算法，它的破譯或求解難度基本上是指數級的。正是由於RSA演算法和ECC演算法這一明顯不同，使得ECC演算法的單位安全強度高於RSA演算法，也就是說，要達到同樣的安全強度，ECC演算法所需的密鑰長度遠比RSA演算法低（見表1和圖1）。這就有效地解決了為了提高安全強度必須增加密鑰長度所帶來的工程實現難度的問題.

③ 安全質數的詳細介紹

安全質數在加密演算法中的運用：一些因子分解的演算法（象Pollard Rho演算法）的計算時間部份取決於被分解數的質因子減去一的因子大小，假如被分解的數以一個安全素數2p+1作為因子，因為此素數減去一有一個大素數p做為因子，計算時間會變多。可是很容易理解任何一個小於10的素數都不是真正安全的，對於任何一個有著合適演算法的現代計算機都能在適當的時間內判斷出它的素性，可是這些小一點的安全素數在加密演算法原理的教學中仍然還是很有用的。對於安全素數還沒有像對費馬素數與梅森素數一樣的特別的素性檢測方法。
開始的幾個安全素數是：
5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907
之所以叫它們是「安全」素數，是因為它們在加密演算法中的運用，很容易理解：任何一個小於1050的素數都不是真正安全的，對於任何一個有著合適演算法的現代計算機都可以在適當的時間內判斷出它的素性，但是這些小一點的安全素數在加密演算法原理的教學中仍然還是很有用的。 不過對於安全素數還沒有像對費馬素數與梅森素數一樣的特別的素性檢測方法。
除了5，還沒有即是費馬素數又是安全素數的數了。一個給定的費馬素數F，一個小小的反證就可以證明（F－1）/2會是2的平方。
除了7，還沒有即是梅森素數又是安全素數的數了。這個證明有點麻煩，不過仍然在基礎代數的范疇內，p必須是素數，2p-1才有可能是素數，那麼((2p - 1) - 1)/2 = 2p - 1 - 1,（梅森素數），因為只有當p=3時p－1才有可能是素數，即2^3-1=7。
第一類坎寧安鏈中所有的數除了最後一項都是索菲熱爾曼素數，除了第一項都是安全素數，如果安全素數是以7結尾，那麼它具有10n+7的形式。

④ 橢圓加密演算法的方程

橢圓曲線密碼體制來源於對橢圓曲線的研究，所謂橢圓曲線指的是由韋爾斯特拉斯（Weierstrass）方程：
y2+a1xy+a3y=x3+a2x2+a4x+a6 (1)
所確定的平面曲線。其中系數ai(I=1,2,…,6)定義在某個域上，可以是有理數域、實數域、復數域，還可以是有限域GF（pr），橢圓曲線密碼體制中用到的橢圓曲線都是定義在有限域上的。
橢圓曲線上所有的點外加一個叫做無窮遠點的特殊點構成的集合連同一個定義的加法運算構成一個Abel群。在等式
mP=P+P+…+P=Q (2)
中，已知m和點P求點Q比較容易，反之已知點Q和點P求m卻是相當困難的，這個問題稱為橢圓曲線上點群的離散對數問題。橢圓曲線密碼體制正是利用這個困難問題設計而來。橢圓曲線應用到密碼學上最早是由Neal Koblitz 和Victor Miller在1985年分別獨立提出的。
橢圓曲線密碼體制是目前已知的公鑰體制中，對每比特所提供加密強度最高的一種體制。解橢圓曲線上的離散對數問題的最好演算法是Pollard rho方法，其時間復雜度為，是完全指數階的。其中n為等式(2)中m的二進製表示的位數。當n=234, 約為2117，需要1.6x1023 MIPS 年的時間。而我們熟知的RSA所利用的是大整數分解的困難問題，目前對於一般情況下的因數分解的最好演算法的時間復雜度是子指數階的，當n=2048時，需要2x1020MIPS年的時間。也就是說當RSA的密鑰使用2048位時，ECC的密鑰使用234位所獲得的安全強度還高出許多。它們之間的密鑰長度卻相差達9倍，當ECC的密鑰更大時它們之間差距將更大。更ECC密鑰短的優點是非常明顯的，隨加密強度的提高，密鑰長度變化不大。
德國、日本、法國、美國、加拿大等國的很多密碼學研究小組及一些公司實現了橢圓曲線密碼體制，我國也有一些密碼學者
做了這方面的工作。許多標准化組織已經或正在制定關於橢圓曲線的標准，同時也有許多的廠商已經或正在開發基於橢圓曲線的產品。對於橢圓曲線密碼的研究也是方興未艾，從ASIACRYPTO』98上專門開辟了ECC的欄目可見一斑。
在橢圓曲線密碼體制的標准化方面，IEEE、ANSI、ISO、IETF、ATM等都作了大量的工作，它們所開發的橢圓曲線標準的文檔有：IEEE P1363 P1363a、ANSI X9.62 X9.63、 ISO/IEC14888等。
2003年5月12日中國頒布的無線區域網國家標准 GB15629.11 中，包含了全新的WAPI(WLAN Authentication and Privacy Infrastructure)安全機制，能為用戶的WLAN系統提供全面的安全保護。這種安全機制由 WAI和WPI兩部分組成，分別實現對用戶身份的鑒別和對傳輸的數據加密。WAI採用公開密鑰密碼體制，利用證書來對WLAN系統中的用戶和AP進行認證。證書裡麵包含有證書頒發者(ASU)的公鑰和簽名以及證書持有者的公鑰和簽名，這里的簽名採用的就是橢圓曲線ECC演算法。
加拿大Certicom公司是國際上最著名的ECC密碼技術公司,已授權300多家企業使用ECC密碼技術，包括Cisco 系統有限公司、摩托羅拉、Palm等企業。Microsoft將Certicom公司的VPN嵌入微軟視窗移動2003系統中。
以下資料摘自：http://www.hids.com.cn/data.asp

⑤ 比如一個很大超過千的數怎麼才能快速分解質因數呢舉個實際例子

運用Pollard-Rho演算法，復雜度為O(n^1/4)，不過這個演算法只能夠判斷2^63以內的，更大
的限於long long int本身的約束，無法進行判斷了

⑥ 如何快速簡便的判斷一個多位數是不是質數

1. 簡單的隨機演算法的話有 Miller-Rabin 演算法2. 整數分解現在沒有多項式演算法，簡單演算法有Pollard Rho演算法，比暴力試除快。

⑦ 為什麼要進行大數分解

rho演算法其實是一種概率上的演算法，雖然是靠概率，但是其准確率非常高（99.9%），更重要的是，該演算法效率極高。其主要基於密碼學當中的一個「生日悖論「來進行演算法的設計。簡單來講就是，我們將N的兩個因子x和y（就假設它有兩個）從一大堆數里挑出來的概率非常小，但是如果我們挑滿足x-y等於某個數的話，概率就要大很多。更進一步，如果我們找gcd(|x-y| ,N)呢？那麼概率就會更大，就是這么個道理。
————————————————
版權聲明：本文為CSDN博主「the__apollo」的原創文章，遵循CC 4.0 BY-SA版權協議，轉載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/The__Apollo/article/details/80279716

⑧ 哪些演算法讓你感覺醍醐灌頂

貝葉斯定理

比如這樣一個問題：你喜歡上一個人的概率，你覺得一個人某方面好的概率，你喜歡上一個人然後覺得這個人某方面好的概率，你覺得一個人某方面好然後喜歡上這個人的概率，這4個之間有什麼關系呢？

用數學語言表達：P(喜歡上一個人), P(覺得一個人某方面好), P(覺得這個人某方面好|喜歡上一個人) 和 P(喜歡上這個人|覺得一個人某方面好) 有什麼關系呢？

我們生活中遇到的很多概率其實都是條件概率/後驗概率(在某一條件下成立的事件的概率)，貝葉斯定理揭示了不同的條件概率之間的關系: )

一瞬間，感覺讓你發現了世界運行了某些奧秘

KMP非常優美，SIFT 圖像匹配演算法很強大，plsa語義相似度計算也讓我震撼，不過最讓我震撼的還是mathematica里的fullsimplify背後的演算法。

Fullsimplify這玩意能搞定很多人都搞不定的公式，我說的搞不定是指該問題本身人可以在三五步之內求解，但卻是很難求解的問題，例如某些三角函數的積分需要巧妙地作換元積分才能得解。

從思想上看，最深刻的是遞歸，以及求泛函極值的最小作用量。基於這兩種思想的演算法，比如快排、HMM中的Baum-Welch，都是精美的演算法，但背後的思想根基並非首創。動態規劃、蒙特卡洛類的演算法也屬此列。

此外，有「道法自然」意味的模擬退火、蟻群、遺傳、粒子群這些，思想方法上有創新，但是演算法設計上與神經網路、SVM、HMM相比，就略顯粗糙。

⑨ 安全質數的釋義

安全素數（安全質數）是滿足2p+1形式的一類數，在這里p也應是素數。（相反地，素數p叫做索菲熱爾曼素數。）詳細介紹之所以叫它們是「安全」素數，是因為它們在加密演算法中的運用：某些因子分解的演算法（如Pollard Rho演算法）的計算時間的部份取決於被分解數的質因子減去一的因子大小，而若被分解的數以一個安全素數2p+1作為因子，由於此素數減去一有一個大素數p做為因子，計算時間將會變多。但是很容易理解任何一個小於10的素數都不是真正安全的，因為對於任何一個有著合適演算法的現代計算機都能在適當的時間內判斷出它的素性，但是這一些小一點的安全素數在加密演算法原理的教學中仍然還是很有用的。

⑩ 判斷整數是否分解成兩個質素的高效演算法

這個問題，首先用小質數測試。 通過之後：
然後，嘗試用Pollard-Rho演算法進行分解因子。當然你必須准備一個好的 素數測試演算法。素數測試演算法，可用Miller-Rabin對付~