冰情工作室

[模運算]

對於一個數字 (> 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)

先使用 65536-bit 模運算, 需時 122644 ms

而使用 262144-bit 模運算, 需時 507112 ms

比例為 1: 4.1348, 這讓長度再增加的話, 可能會變成好幾天算完

於是分析原模運算的演算法, 是使用 bitwise 的減法, 但這運算法的運算量 O((bits^2)/4), 當長度變成 4 倍, 運算量自然變為 4 倍, 時間也就變成 4 倍

所以就用分段除法來解決,

注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)
            [info] muls= 31, elps=0, avg= 0.000, prc= 0.000
            [info] mods= 32, elps=0, avg= 0.000, prc= 0.000
   [2021/12/15 20:14:55]  20! + 1 is COMPOSITE !!!! (a= 23) (elps= 10) (bit=62 /65536)
            (sig= 00000000 00000000 00000000 00000000 00000000 00000000 01533577 B06083DE
            [info] muls= 82, elps=2, avg= 0.024, prc= 20.000

注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)
            [info] muls= 47, elps=0, avg= 0.000, prc= 0.000
            [info] mods= 48, elps=1, avg= 0.021, prc= 50.000
[*][2021/12/15 18:38:06]  14! - 1 is PRIME     !!!! (a= 17) (elps= 3, avg= 3.000) (bit=37 /65536)
            [info] muls= 56, elps=0, avg= 0.000, prc= 0.000
            [info] mods= 57, elps=3, avg= 0.053, prc= 100.000

range .N  = 40001 ~ 50000
range .PDM= 1 ~ 210000 (range.P= 1 ~ 2.1e10)
count .P  = 9351
maxcnt.N  = 49017
maxcnt.P  = 8
nofacs.N  = 3931

  n= 40001 | p[1]= 10163541961
  n= 40002 | p[0]= 
  n= 40003 | p[1]= 2587779101
  n= 40004 | p[0]= 

range .N  = 30001 ~ 40000
range .PDM= 1 ~ 210000 (range.P= 1 ~ 2.1e10)
count .P  = 9728
maxcnt.N  = 32512
maxcnt.P  = 6
nofacs.N  = 3820

  n= 30001 | p[1]= 2615260619
  n= 30002 | p[2]= 98387.116243
  n= 30003 | p[1]= 268729
  n= 30004 | p[0]= 

range .N  = 20001 ~ 30000
range .PDM= 1 ~ 210000 (range.P= 1 ~ 2.1e10)
count .P  = 9918
maxcnt.N  = 21437
maxcnt.P  = 6
nofacs.N  = 3783

  n= 20001 | p[1]= 1725032797
  n= 20002 | p[1]= 1796761
  n= 20003 | p[1]= 4638239
  n= 20004 | p[1]= 824609

炮竹連聲辭舊歲 恭賀金句迎新年 風和日麗春已近 花開富貴喜滿顏
悠閒時光度朝陽 平常人家慶餘田 國泰民安來開運 更上瑞峰笑連綿

10月10日 是中華民國的誕生之日 百年前的一聲槍響 無數革命志士的鮮血骨肉 鑄造了這個中華民族期盼已久的民主共和國

然而歷經了許多風雨波折 艱苦困頓 而今雖只能在台灣一隅 毅然屹立著 堅定不移的實行三民主義 恪遵總理遺訓 堅守中華民國憲法 勵行民主法治 期能將中華民國的民主種子 散播到全中華民族的人民身上 讓自由民主 法治共和的安和樂利 真正使中國人得到國富民強與長治久安 在這個莊嚴肅穆的日子裡 不要忘記前賢英烈們 拋頭顱灑熱血所捍衛的民主成果 用血肉築長城來抵禦外侮而表現的堅忍意志 今天海內外的華人 必須以總理遺囑: 革命尚未成功 同志仍須努力! 為畢生職志 為所有中國人建立一個康樂強盛的中華民國而繼續奮鬥不息!
 

清末腐敗無能 民心思變已亟 國父倡議革命 志士拋灑熱血
推翻帝制封建 解開千年桎梏 清除復辟餘孽 維護民主共和
蔣公奮臂疾呼 黃埔英傑輩出 組織北伐行列 結束軍閥割據
日寇侵襲東北 列強環伺狼顧 赤禍綿延千里 亡國滅種在即
八年血肉長城 英烈前仆後繼 盧溝血戰禦侮 南京卅萬冤屈
戰亂人民苦痛 兵燹河山變色 鮮血染紅長江 骨肉鑄就堅強

質數: 一個正整數 N, 除了1與N沒有其他的因數, N即為質數

------

質數類型: 依據歐拉定理, 質數個數是無限多個, 也是無限大, 所以就將質數分類成許多一定規則的類型,

    例如: 多項式 f(a) = a^2+a+41, a= [0,40], f(a) 都是質數, 數學家一直都在找尋表達更多質數的多項式

    以下列出我感興趣且已寫過計算程式的類型 (這些類型, 也在 GIMPS 網站上列出發現序列與最新結果):

------

1. 梅森質數 (Mersenne Primes)

    定義梅森數: M(p) = 2^p - 1 , p 為質數, 若 M(p) 是質數, 則稱為梅森質數, 這是以17世紀法國數學家馬蘭.梅森(Marin Mersenne)之名命名, 目前已知最新幾個質數皆是由  GIMPS 所屬發現的, 最大的 M(82589933) 有 24852048 位數, 每每發現就是刷新最大質數的紀錄, 也是基底為2的 Repunit 質數, 已知只有質數個1 (2進位)的數字才可能是質數, 到目前為止, GIMPS 已經找到 16 個梅森質數, 位數也是越來越大, 期待第53個梅森質數的出現, 日後我會列出梅森質數的總列表, 以及梅森數的分解質因數表

------

2. 費馬質數 (Fermat Primes)