冰情工作室

[模運算]

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

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

[32-bit摺疊法]

首先用 32-bit 為一段, 稱為 32-bit 摺疊法(預測法):

以 a= 1481^((b-1)/2) (26852 bits) 為被除數與 b= 1477!+1 (13426 bits) 為除數

step 1:先取 x= b >> (13426-32) [x 為 32 bits]

step 2: 再取 w= a >> (26852-64) [w 為 64 bits]

step 3: 得到 q= int(w/x)

step 4: 計算 e= b*q << (26852-13426-(64-32))

step 5: 再計算 r= a-e (理論上每次減少 32 bits, 測試上減少 32 ~ 38 bits)

step 6: 令 a= r, 若 r <= a, 就得到 a mod b = r or 0; 若其他, 回到 step 2

[64-bit摺疊法]

首先用 64-bit 為一段, 稱為 64-bit 摺疊法(預測法):

以 a= 1481^((b-1)/2) (26852 bits) 為被除數與 b= 1477!+1 (13426 bits) 為除數

step 1:先取 x= b >> (13426-64) [x 為 64 bits]

step 2: 再取 w= a >> (26852-127) [w 為 127 bits]

step 3: 得到 q= int(w/x)

step 4: 計算 e= b*q << (26852-13426-(127-64))

step 5: 再計算 r= a-e (理論上每次減少 64 bits, 測試上減少 62 ~ 72 bits)

step 6: 令 a= r, 若 r <= a, 就得到 a mod b = r or 0; 若其他, 回到 step 2

[128-bit摺疊法]

首先用 128-bit 為一段, 稱為 128-bit 摺疊法(預測法):

以 a= 1481^((b-1)/2) (26852 bits) 為被除數與 b= 1477!+1 (13426 bits) 為除數

step 1:先取 x= b >> (13426-128) [x 為 128 bits]

step 2: 再取 w= a >> (26852-255) [w 為 255 bits]

step 3: 得到 q= int(w/x)

step 4: 計算 e= b*q << (26852-13426-(255-128))

step 5: 再計算 r= a-e (理論上每次減少 128 bits, 測試上減少 125 ~ 134 bits)

step 6: 令 a= r, 若 r <= a, 就得到 a mod b = r or 0; 若其他, 回到 step 2

[256-bit摺疊法]

首先用 256-bit 為一段, 稱為 256-bit 摺疊法(預測法):

以 a= 1481^((b-1)/2) (26852 bits) 為被除數與 b= 1477!+1 (13426 bits) 為除數

step 1:先取 x= b >> (13426-256) [x 為 256 bits]

step 2: 再取 w= a >> (26852-511) [w 為 511 bits]

step 3: 得到 q= int(w/x)

step 4: 計算 e= b*q << (26852-13426-(511-256))

step 5: 再計算 r= a-e (理論上每次減少 256 bits, 測試上減少 254 ~ 262 bits)

step 6: 令 a= r, 若 r <= a, 就得到 a mod b = r or 0; 若其他, 回到 step 2

[512-bit摺疊法]

首先用 512-bit 為一段, 稱為 512-bit 摺疊法(預測法):

以 a= 1481^((b-1)/2) (26852 bits) 為被除數與 b= 1477!+1 (13426 bits) 為除數

step 1:先取 x= b >> (13426-512) [x 為 512 bits]

step 2: 再取 w= a >> (26852-1023) [w 為 1023 bits]

step 3: 得到 q= int(w/x)

step 4: 計算 e= b*q << (26852-13426-(1023-512))

step 5: 再計算 r= a-e (理論上每次減少 512 bits, 測試上減少 510 ~ 515 bits)

step 6: 令 a= r, 若 r <= a, 就得到 a mod b = r or 0; 若其他, 回到 step 2

[1024-bit摺疊法]

首先用 1024-bit 為一段, 稱為 1024-bit 摺疊法(預測法):

以 a= 1481^((b-1)/2) (26852 bits) 為被除數與 b= 1477!+1 (13426 bits) 為除數

step 1:先取 x= b >> (13426-1024) [x 為 1024 bits]

step 2: 再取 w= a >> (26852-2047) [w 為 2047 bits]

step 3: 得到 q= int(w/x)

step 4: 計算 e= b*q << (26852-13426-(2047-1024))

step 5: 再計算 r= a-e (理論上每次減少 1024 bits, 測試上減少 1022 ~ 1028 bits)

step 6: 令 a= r, 若 r <= a, 就得到 a mod b = r or 0; 若其他, 回到 step 2

[2048-bit摺疊法]

首先用 2048-bit 為一段, 稱為 2048-bit 摺疊法(預測法):

以 a= 1481^((b-1)/2) (26852 bits) 為被除數與 b= 1477!+1 (13426 bits) 為除數

step 1:先取 x= b >> (13426-2048) [x 為 2048 bits]

step 2: 再取 w= a >> (26852-4095) [w 為 4095 bits]

step 3: 得到 q= int(w/x)

step 4: 計算 e= b*q << (26852-13426-(4095-2048))

step 5: 再計算 r= a-e (理論上每次減少 2048 bits, 測試上減少 2046 ~ 2048 bits)

step 6: 令 a= r, 若 r <= a, 就得到 a mod b = r or 0; 若其他, 回到 step 2

[結論]

以上 32-bit 摺疊法, 得到 287714 ms, 比 bitwise 減少 219398 ms (-43.26%)

以上 64-bit 摺疊法, 得到 159131 ms, 比 bitwise 減少 347981 ms (-68.62%)

以上 128-bit 摺疊法, 得到 84740 ms, 比 bitwise 減少 422372 ms (-83.29%)

以上 256-bit 摺疊法, 得到 48544 ms, 比 bitwise 減少 458568 ms (-90.43%)

以上 512-bit 摺疊法, 得到 33064 ms, 比 bitwise 減少 474048 ms (-93.48%)

以上 1024-bit 摺疊法, 得到 30646 ms, 比 bitwise 減少 476466 ms (-93.96%)

以上 2048-bit 摺疊法, 得到 60970 ms, 比 bitwise 減少 446142 ms (-87.98%)

由以上幾種摺疊法, 分段長度越大, 減少時間比例越小, 所以每種長度應使用適當 bit 摺疊法

而比對後, 128-bit 摺疊法, 做 262144 bits 模運算比用 65536 bits 模運算(使用 bitwise 減法), 也減少 34691 ms (-28.29%)

綜上可知, 使用 1024-bit 摺疊法會得到最大的減幅, 幾乎是 bitwise 的 19 倍,

後來測試 4205!+1 (-bits) 在 bitwise 用了 5329679 ms, 但改用 512-bit 僅需 594844 ms, 減少 4734935 ms (-88.84%) 

而改用 1024-bit 也需 612560 ms, 減少 4717119 ms (-88.51%)

顯然 512-bit 與 1024-bit 可能都適用於 10000 bits 以上的數字

[預測]

最後, 我預估 130000 bits 以上, 可用 2048-bit 摺疊法或更高, 但減少的幅度預估在 60%, 但需要驗證