我們找到了新的梅森素數!
生成乙個列表(forming a list)
很容易證明，如果 2p-1 是素數，則 p 也一定是素數。因此，搜尋梅森素數的第一步就是生成乙個用於測試的素數指數列表。
試驗分解因子(trial factoring)
下一步是通過尋找小因子來排除一些指數。有乙個非常高效的演算法判斷乙個數是否能整除 2p-1。例如，讓我們看一下 47 是否能夠整除 223-1。
把指數 23 轉換成二進位制數，我們得到 10111。從 1 開始，重複以下步驟：平方，刪除指數的最左邊二進位，如果該位是 1，則將平方後得到的值乘以 2，然後計算其除以 47 後的餘數。
刪除最左如果需要就除以47
平方邊二進位乘以 2 的餘數
1*1 = 1 1 0111 1*2 = 22
2*2 = 4 0 111 no4
4*4 = 16 1 11 16*2 = 32 32
32*32 = 1024 1 1 1024*2 = 2048 27
27*27 = 729 1 729*2 = 1458 1
因此，223 = 1 mod 47。兩邊同時減 1，223-1 = 0 mod 47。因此我們知道 47 是乙個因子，從而 223-1 不是素數。
可以證明梅森數有乙個非常好的性質：2p-1 的任何因子 q 必定是 2kp+1 的形式，並且 q 除以 8 的餘數一定是 1 或者 7。最後，乙個高效的程式可以利用任何可能的因子 q 必須是素數這一事實。
gimps 程式的分解因子**使用修正的厄拉托森斯(eratosthenes)篩法，利用乙個二進位表示乙個可能的 2kp+1 形式的因子。這個篩排除能夠被大約 40,000 以下的素數整除的任何可能的因子。同樣，表示除以 8 的餘數是 3 或者 5 的可能的因子的二進位被清除。
這個過程排除大約百分之九十五的可能的因子。剩下的可能的因子使用上面描述的高效的演算法進行測試。現在唯一的問題是要試驗分解多少因子？
答案取決於三個因素：分解因子的代價、發現乙個因子的概率和素性測試的代價。我們使用以下公式：
分解因子的代價 < 發現因子的概率 * 2 * 素性測試的代價也就是說，分解因子所花費的時間必須小於期望被節省的時間。如果能夠發現乙個因子，我們就能夠避免進行首次素性測試和複查。根據以前分解因子的資料，我們知道發現乙個 2x 到 2x+1 之間的因子的概率大約是 1/x。
本程式進行素性測試和分解因子所需的時間已經被計算出來。目前，本程式試圖分解因子到：
指數上限分解因子到
3,960,000
2605,160,000 261
6,515,000 262
8,250,000 263
13,380,000 264
17,850,000 265
21,590,000 266
28,130,000 267
35,100,000 268
44,150,000 269
57,020,000 270
71,000,000 271
79,300,000 272
用 p-1 方法分解因子(p-1 factoring)
還有另外乙個方法可被 gimps 程式用來搜尋因子，因而避免進行素性測試的花費。這個方法叫做波拉德(pollard)(p-1)方法。如果 q 是某數的乙個因子，並且 q-1 是高度復合的(也就是說 q-1 只有小因子)，p-1 方法就可以找到因子 q。
該方法用於梅森數時甚至更高效。回憶一下，因子 q 只能是 2kp+1 的形式。只要 k 是高度復合時，就很容易修改 p-1 方法去搜尋因子 q。
p-1 方法是十分簡單的。在第一階段我們挑選乙個邊界 b1。只要 k 的所有因子都小於 b1(我們稱 k 為 b1-平滑(b1-smooth))，p-1 方法就能找到因子 q。
我們首先計算 e = (比 b1 小的所有素數的乘積)。然後計算 x = 3e*2*p。最後，檢查 x-1 和 2p-1 的最大公約數，就可以知道是否找到乙個因子。
使用第二個邊界 b2, 我們可以改進波拉德演算法，達到第二階段。如果 k 在 b1 到 b2之間剛好有乙個因子，而其它因子都小於 b1，我們就能夠在第二階段找到因子 q。這個階段要使用大量的記憶體。
gimps 程式使用該方法去尋找一些給人印象深刻的因子。例如：22944999-1 能夠被314584703073057080643101377 整除.
314584703073057080643101377 等於 2 * 53409984701702289312 * 2944999 + 1.值 k, 53409984701702289312, 是非常平滑的:53409984701702289312 = 25 * 3 * 19 * 947 * 7187 * 62297 * 69061gimps 如何智慧型地選擇 b1 和 b2 呢？
我們使用試驗分解因子方法中的公式的變種。我們必須使下式取得最大值：發現因子的概率 * 2 * 素性測試的代價 - 分解因子的代價發現因子的概率和分解因子的代價都依賴於 b1 和 b2 的取值。
當 k 是 b1-平滑或者 k 是 b1-平滑並且在 b1 到 b2 之間剛好有乙個因子時，迪克曼(dickman)函式(參見克努特(knuth)的《計算機程式設計藝術》第二卷(譯註:中文版第347頁))用來確定發現因子的概率。本程式嘗試許多 b1 的值，如果有足夠的可用記憶體的話也嘗試一些 b2 的值，用以確定使以上公式取得最大值的 b1 和 b2 的值。
盧卡斯-萊默測試(lucas-lehmer testing)
盧卡斯-萊默素性測試是非常簡單的：如果 p > 2， 2p-1 是素數當且僅當 sp-2 = 0，其中，s0 = 4，sn =(sn-12 - 2) mod (2p-1)。例如，證明 27 - 1 是素數的過程如下：
s0 = 4
s1 = (4 * 4 - 2) mod 127 = 14
s2 = (14 * 14 - 2) mod 127 = 67
s3 = (67 * 67 - 2) mod 127 = 42
s4 = (42 * 42 - 2) mod 127 = 111
s5 = (111 * 111 - 2) mod 127 = 0
為了高效地實現盧卡斯-萊默測試，我們必須尋找對巨大的數進行
行平方及對 2p-1 取餘的快速方法。自二十世紀六十年代後期以來，對巨大的數進行平方的最快速的演算法是：把巨大的數**成小片形成乙個大陣列，然後執行快速傅利葉變換(fft)，逐項平方，然後再進行快速傅利葉逆變換(ifft)。
參見克努特的《計算機程式設計藝術》第二卷「乘法能有多快？」一節(譯註:中文版第267頁)。
2023年1月，由理查德·克蘭多爾(richard crandall)和巴里·費金(barry fagin) 合著的題為「離散加權變換和大整數算術」的計算數學文章，引入了無理底數 fft 的概念。這個改進使得計算平方的速度提高兩倍以上，允許使用較小的 fft，並且這一過程中自動執行了對 2p-1 取餘步驟。雖然由於英特爾公司的奔騰處理器體系結構的原因，gimps 程式使用浮點 fft，但彼得·蒙哥馬利(peter montgomery)給出的乙個純整數加權變換的方法也能夠被使用。
正如上一段所提到的，gimps 使用組合語言編寫的浮點 fft 演算法，充分利用流水線和快取記憶體。因為浮點運算是不精確的，在每次迭代後浮點值捨入到整數。本來該有的整數結果和程式計算出來的浮點結果之間的差異叫做「捲摺誤差」。
如果捲摺誤差超過 0.5 則捨入將產生不正確的結果 - 這意味著必須使用更大的 fft。gimps 程式的錯誤檢查確保最大捲摺誤差不超過 0.
4。不幸地，這種錯誤檢查的代價相當高，以致於不能在每次平方後都進行檢查。存在另外一種代價很低的錯誤檢查。
fft 平方的乙個性質是：(輸入 fft 值的和)2 = (輸出 ifft 值的和)
由於我們使用浮點數，我們必須將上式中的「等於」改為「約等於」。如果上式中兩個值實質上不等，將給出乙個在 檔案中描述過的 suminp != sumout 錯誤。
如果輸入 fft 值的和是乙個非法的浮點數(例如無窮大)，將給出乙個 illegal sumout 錯誤。不幸地，這種錯誤檢查無法發現我們將在下一節中描述的所有錯誤。盧卡斯-萊默測試發現乙個新的梅森素數的概率有多大？
乙個簡單的估計是再次利用發現乙個 2x 到 2x+1 之間的因子的概率大約是 1/x 的事實。例如，你已經使用試驗分解因子證明 210000139-1 沒有比 264 小的因子，那麼它是素數的概率是: 沒有 65 二進位因子的概率 * 沒有 66 二進位因子的概率 * ...
* 沒有 5000070 二進位因子的概率，即：
64 65 500006965 66 5000070
化簡後得到：64 / 5000070，或者 1 / 78126。這個簡單的估計不是很準確，它給出的公式是:
(試驗分解因子到多大的指數) / (指數/2)。進一步的工作表明更精確公式是：(試驗分解因子到多大的指數-1) / (指數 * 尤拉常數(0.
577...))。在上例中，是 1 / 91623。
這個更精確的公式是未經證
明的。複查(double-checking)
為了核實首次的盧卡斯-萊默素性測試沒有出錯，gimps 程式執行第二次素性測試。在每次測試期間，最終的 sp-2 的最低 64 二進位，叫做餘數，被列印出來。如果它們相同，gimps 宣稱該指數已經被複查。
如果它們不相同，素性測試被再次執行直到最後出現匹配。和首次測試相匹配的複查，通常是在首次測試之後大約兩年進行。gimps分配複查給較慢的計算機，因為該指數比正在進行的首次測試的指數小，以便較慢的計算機能夠在合理的時間內完成其工作任務。
gimps 複查採取進一步的防護措施以避免程式設計錯誤。在開始盧卡斯-萊默測試之前，s0 的值被左移隨機的二進位。每次平方剛好加倍我們左移的 s 值。
注意對 2p-1 取餘的步驟僅是簡單地將第 p 位以上的位移到最低有效位，因此沒有資訊丟失。為什麼我們要自找麻煩呢？因為如果計算 fft 的程式**有錯誤，對 s 值的隨機的移位確保第二次素性測試中的 fft 演算法處理乙個和首次素性測試完全不同的值。
乙個程式設計錯誤幾乎不可能產生同樣的最終 64 二進位餘數。歷史上，盧卡斯-萊默測試執行期間沒有報告嚴重錯誤時，結果的錯誤率大致是 1.5%。
盧卡斯-萊默測試產生的錯誤被報告的比率大約是 50%。作為記錄，我沒有把「illegal sumout」作為嚴重錯誤統計。
數學速演算法
寫在前面的話 親愛的同學們，在日常生活中，你們一定常會遇到這樣的一些問題吧 去商店買幾樣東西，付錢的時候，明明知道該如何算，卻一時給懵住了，加來加去，就是算不出來 在家裡，幫助居委會的奶奶抄電表 水表，收電費 水費，總得費不少氣力才能算出來.在做數學題的時候，有 些計算題雖說不是太難，可是計算起來卻...
關於《演算法與程式設計》之對分查詢演算法的質疑與對策
摘要 浙江省教育出版社普通高中課程標準實驗教科書 演算法與程式設計 中關於對分查詢演算法的內容存在有明顯的邏輯錯誤。針對課本中的疑問，如何化解學生的疑慮，引導學生學習 理解和掌握對分查詢演算法的思想和方法，從而培養學生獨立思考 不迷信教材 不迷信權威的科學學習態度和鑽研精神，我們對教材中對分演算法進...
12演算法描述與設計
演算法分析 從1開始順次取出乙個自然數判斷它被3 5 7整除後的餘數是否為2 3 2。如果是，則這個數即是所求的數，求解結束 否則，用下乙個數再試，直到找到這個數為止。演算法描述 第一步 將n初始值賦為1 第二步 如果n被3 5 7整除後的餘數分別為2 3 2，則輸出n的值，轉到第四步。第三步 將n...