※ 以下內容，是我在 Yahoo 奇摩知識家所評論的一篇文章 ※
轉載內容來自 http://tw.knowledge.yahoo.com/question/article?qid=1708102606874
評論對象： 如何迅速檢驗質數？

Agrawal-Kayal-Saxena 演算法：
紐約時報(New York Times)於 2002年8月8日報導了，『新的方法解開了數學的關鍵問題』，即印度科技學院的 Manindra Agrawal、Neeraj Kayal、Nitin Saxena 師徒三人提出一個能在多項士時間內，判斷任意正整數是否為質數的演算法[1]，該演算法相當乾淨且漂亮，這個結果轟動了數學界與資訊界。對於數學界而言，自從高斯以來，判斷一整數是否為質數，本來就是許多數學家所關心的問題；對於資訊界而言，由於大多數的Publick Key Cryptosystem 需要質數，而且是大質數，一個真正能在適當時間內，找到真正質數的 deterministic 演算法，為關鍵性問題。這樣的演算法實用價值不可言喻。曾經是1997年國際數學奧林匹亞競賽印度代表隊的隊員 Kayal 與 Saxena選擇了資訊系就讀，並參加Agrawal 帶領下的學生專題計畫，並在2002年夏天，開始了博士生研究，在6月10日，他們的研究達到突破性進展。他們找出對質數羃次的重要刻劃。

值的一題的是，證明是用一般基礎數論的結果，如費馬小定理等，對於有代數以及基礎數論知識的人而言，要理解該定理的證明並非難事，[2]將該結果整理一下，就可以得到下列判斷質數的演算法。

(Agrawal-Kayal-Saxena 演算法)

輸入一正整數 n > 1，並判斷其是否為質數。

bool Agrawal_Kayal_Saxena(biginteger n) // n > 1 整數

{

Step 1:  if (is Power(n))   // 若 n =a^b ，其中 b > 1

                     return 0;  // n為某數羃次，非質數

Step 2: r = min{r| ord(n, Z/r) > 4 * (log (n)^2)};

                                     // ord(n,Z/r) 表 n 在乘法群 Z/r 之秩

              for (a=2;a<=r;a++)

                  { 
                         ***=***(a,n);

                         if (***>1 && *** < n)

                         return 0; // n 為合成數，非質數
                   };

             s=floor(2*sqr (Eulerphi(r)) * log(n));

step 3: for(a=1;a<=s;a++)

                    if((x+a)^n!=x^n+a(mod x^r-1,n))

                    return 0; // n 為合成數，非質數

          return 1;  // n 為值數 
}

演算法內容節錄自[3]。
[1] Agrawal M., Kayal N. and Saxena N., 'PRIMES is in P', Preprint of Aug., 2002, http://www.cse.iitk.ac.in/news/primality.html
[2] Bornemann F., 'PRIMES Is in P: A Breakthrouth for Everyman', Notices of the AMS, May 2003.
[3] 鄧安文 編著，密碼學--加密演算法與密碼分析，全華科技圖書出版，2004年。

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课