[模運算]
對於一個數字 (> 64 bits), 其四則運算與模運算, 都需要特殊處理
為此, 我已對 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144 bits 等長度的數字, 做四則運算與模運算的類別, 對大數分解, 達到簡潔程式碼與重複利用的目的
但由於長度不斷增加, 運算量 O(k^2) 會急遽增加 (k=bits/64), 平均每增加一倍長度, 用時會多一倍
以 y= 1477!+1 (13426 bits) 為例, 計算 z = 1481^((y-1)/2) mod y 的結果 (正確結果為 -1)
注1: 格式, [*][date-time] n!+1 is PRIME/COMPOSITE !!!! (a= x) (elps= y, avg= z) (bit= b /65536) (sig= 256-bit)
注2: [*] 為判定質數會寫出, date-time 為結果產出時間, n 為經過篩選後尚無質因數者, sig 為非質數者 256-bit 簽章
注3: a 需大於 n 的質數用來計算 a^((n!+1)/2) mod (n!=1), elps 為總計時(ms), avg 為每個 a 的平均時, b=floor[log2((n!+1)/2)]
注4: 此記錄目前使用超長整數 65536-bit 進行計算, 模運算採用 32-bit 摺疊法 (folding for 32-bit)
[*][2021/12/15 20:14:55] 11! + 1 is PRIME !!!! (a= 13) (elps= 1, avg= 1.000) (bit=26 /65536)
注1: 格式, [*][date-time] n!-1 is PRIME/COMPOSITE !!!! (a= x) (elps= y, avg= z) (bit= b /65536) (sig= 256-bit)
注2: [*] 為判定質數會寫出, date-time 為結果產出時間, n 為經過篩選後尚無質因數者 , sig 為非質數者 256-bit 簽章
注3: a 需大於 n 的質數用來計算 a^((n!-1)/2) mod (n!-1), elps 為總計時(ms), avg 為每個 a 的平均時, b=floor[log2((n!-1)/2)]
注4: 此記錄目前使用超長整數 65536-bit 進行計算, 模運算採用 32-bit 摺疊法 (folding for 32-bit)
[*][2021/12/15 18:38:06] 12! - 1 is PRIME !!!! (a= 13) (elps= 2, avg= 2.000) (bit=29 /65536)
range .N = 40001 ~ 50000
range .PDM= 1 ~ 210000 (range.P= 1 ~ 2.1e10)
count .P = 9351
maxcnt.N = 49017
maxcnt.P = 8
range .N = 30001 ~ 40000
range .PDM= 1 ~ 210000 (range.P= 1 ~ 2.1e10)
count .P = 9728
maxcnt.N = 32512
maxcnt.P = 6
range .N = 20001 ~ 30000
range .PDM= 1 ~ 210000 (range.P= 1 ~ 2.1e10)
count .P = 9918
maxcnt.N = 21437
maxcnt.P = 6
炮竹連聲辭舊歲 恭賀金句迎新年 風和日麗春已近 花開富貴喜滿顏
悠閒時光度朝陽 平常人家慶餘田 國泰民安來開運 更上瑞峰笑連綿
10月10日 是中華民國的誕生之日 百年前的一聲槍響 無數革命志士的鮮血骨肉 鑄造了這個中華民族期盼已久的民主共和國
然而歷經了許多風雨波折 艱苦困頓 而今雖只能在台灣一隅 毅然屹立著 堅定不移的實行三民主義 恪遵總理遺訓 堅守中華民國憲法 勵行民主法治 期能將中華民國的民主種子 散播到全中華民族的人民身上 讓自由民主 法治共和的安和樂利 真正使中國人得到國富民強與長治久安 在這個莊嚴肅穆的日子裡 不要忘記前賢英烈們 拋頭顱灑熱血所捍衛的民主成果 用血肉築長城來抵禦外侮而表現的堅忍意志 今天海內外的華人 必須以總理遺囑: 革命尚未成功 同志仍須努力! 為畢生職志 為所有中國人建立一個康樂強盛的中華民國而繼續奮鬥不息!
大數分解: 對於位數過大的正整數進行質因數分解, 會因為位數範圍與數字結構而選擇適當的分解方法
------
以下介紹幾個方法:
------
1. 費馬平方差法 (Fermat Method, Square Subtraction)
range .N = 10001 ~ 20000
range .PDM= 1 ~ 210000 (range.P= 1 ~ 2.1e10)
count .P = 10508
maxcnt.N = 16425
maxcnt.P = 7
range .N = 40001 ~ 50000
range .PDM= 1 ~ 210000 (range.P= 1 ~ 2.1e10)
count .P = 9362
maxcnt.N = 46265
maxcnt.P = 7
