2011年7月29日星期五

Primitive root

Let number g是prime p的最小power mod p餘1,若power index i等如p-1,那麼g便是p的primitive root

g i 1 mod p
例如,11的primitive root有2, 6, 7, 8:

>>> [2 ** i % 11 for i in range(1, 11)]
[2, 4, 8, 5, 10, 9, 7, 3, 6, 1]
>>> [3 ** i % 11 for i in range(1, 11)]
[3, 9, 5, 4, 1, 3, 9, 5, 4, 1]
>>> [6 ** i % 11 for i in range(1, 11)]
[6, 3, 7, 9, 10, 5, 8, 4, 2, 1]
>>> [7 ** i % 11 for i in range(1, 11)]
[7, 5, 2, 3, 10, 4, 6, 9, 8, 1]
>>> [8 ** i % 11 for i in range(1, 11)]
[8, 9, 6, 4, 10, 3, 2, 5, 7, 1]

而3並不是11的primitive root。

當找到其中一個primitive root後,要找另一個很容易,因為若g是primitive root,1/g也會是primitive root。因為g, g2, g3, ..., gp-1 (mod p) 全不相同,只要g≠1/g,它們的inverse 1/g, 1/g2, 1/g3, ...,也盡不相同。prime number 3只有一個primitive root 2,2的inverse是自己,所以大過3的prime number都有偶數數量的primitive root。

2是11的primitive root,2的inverse是6,所以6也是primitive root。

2 · 6 1 2 10 2 1 · 2 9 mod 11

要檢查r是否p的primitive root,檢查r的power 2至(p - 1)/2便可。但要找出r並不容易,由其是當p很大,


若p很大,找尋primitive root的過程會相當漫長,仍在找尋解決辦法,上上之策是有其它efficient algorithm以減低計算量;中策是用PyPy或Shed Skin等加速,但都不support Python 3;下策是用Cython,加type declaration,support Python 3但不包括Generator,犧牲code base簡約。嘗試在這篇文章High Performance Python tutorial裏找尋解決方案。

Extended Euclidean algorithm開始,再到Modular exponentiation,跟著到Is prime?,再加上今集的Primitive root,材料已準備齊全,下集入正題了。

沒有留言:

發佈留言