冰情工作室

[模運算]

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

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

質數: 一個正整數 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)

大數分解: 對於位數過大的正整數進行質因數分解, 會因為位數範圍與數字結構而選擇適當的分解方法

------

以下介紹幾個方法:

------

1. 費馬平方差法 (Fermat Method, Square Subtraction)

    n, a, b 為正整數, 滿足 n= a^2 - b^2, 即 n 是 a,b 兩數的平方差, 則可得知 n = (a+b).(a-b), a+b 與 a-b 皆為 n 的因數

    若 a+b 與 a-b 的差距很小, 則 n 被分解的速度會更快, 也就是 b = [(a+b)-(a-b)]/2 可從 0 開始嘗試, 則 n 即可被分解

    另, 發現 p 是 b 的奇質因數, 需滿足 (n/p)L = 1 or 0 (注1)

    另, a+b 與 a-b 若是 n 的因數, 其差距為 c.log2(n), c 為常數, 即可稱為幾乎相等 (注2)

      ////  注1: (n/p)L 是勒讓得符號, (n/p)L  =1 代表 n 是 p 的二次剩餘, (n/p)L  = 0 代表 n 是 p  的倍數, (n/p)L  = -1 代表 n 不是 p 的二次剩餘  ////