使用Python有效地查找原始根modulo？

Question

我使用下面的代碼爲在尋找primitive roots模n的Python：

代碼：

def gcd(a,b): 
    while b != 0: 
     a, b = b, a % b 
    return a 

def primRoots(modulo): 
    roots = [] 
    required_set = set(num for num in range (1, modulo) if gcd(num, modulo) == 1) 

    for g in range(1, modulo): 
     actual_set = set(pow(g, powers) % modulo for powers in range (1, modulo)) 
     if required_set == actual_set: 
      roots.append(g)   
    return roots 

if __name__ == "__main__": 
    p = 17 
    primitive_roots = primRoots(p) 
    print(primitive_roots) 

輸出：從

[3, 5, 6, 7, 10, 11, 12, 14] 

代碼片段中提取：Diffie-Hellman (Github)

---

能否primRoots方法被簡化或在存儲器使用和性能 /效率方面優化？

Answer 1

使用列表並設置推導一個快速變化：

def primRoots(modulo): 
    required_set = {num for num in range(1, modulo) if gcd(num, modulo)} 
    return [g for g in range(1, modulo) if required_set == {pow(g, powers, modulo) 
      for powers in range(1, modulo)}] 

另外一個是memoization上gcd功能：

from functools import wraps 
def cache_gcd(f): 
    cache = {} 

    @wraps(f) 
    def wrapped(a, b): 
     key = (a, b) 
     try: 
      result = cache[key] 
     except KeyError: 
      result = cache[key] = f(a, b) 
     return result 
    return wrapped 

對於做所有的過程都重複的拒絕：

@cache_gcd 
def gcd(a,b): 
    while b != 0: 
     a, b = b, a % b 
    return a 

正如在評論中提到的s，作爲更多pythoinc優化器的方式，您可以使用fractions.gcd（或用於Python-3.5 + math.gcd）。

Answer 2

基於皮特的答案Kasramvd的評論和，我可以建議是：

from math import gcd as bltin_gcd 

def primRoots(modulo): 
    required_set = {num for num in range(1, modulo) if bltin_gcd(num, modulo) } 
    return [g for g in range(1, modulo) if required_set == {pow(g, powers, modulo) 
      for powers in range(1, modulo)}] 

print(primRoots(17)) 

輸出：

[3, 5, 6, 7, 10, 11, 12, 14] 

---

變化：

• 它現在使用pow方法的模數的3-rd參數。
• 切換到gcd爲math（用於Python 3.5）定義的內置函數用於提高速度。

---

附加信息有關內置GCD是在這裏：Co-primes checking

Answer 3

在p是素的特殊情況下，下面是一個很好的快一點：

import sys 

# translated to Python from http://www.bluetulip.org/2014/programs/primitive.js 
# (some rights may remain with the author of the above javascript code) 

def isNotPrime(possible): 
    i = 2 
    while i <= possible**0.5: 
     if (possible % i) == 0: 
      return True 
     i = i + 1 
    return False 

def primRoots(theNum): 
    if isNotPrime(theNum): 
     raise ValueError("Sorry, the number must be prime.") 
    o = 1 
    roots = [] 
    r = 2 
    while r < theNum: 
     k = pow(r, o, theNum) 
     while (k > 1): 
      o = o + 1 
      k = (k * r) % theNum 
     if o == (theNum - 1): 
      roots.append(r) 
     o = 1 
     r = r + 1 
    return roots 

print(primRoots(int(sys.argv[1]))) 

Answer 4

通過使用更高效的算法，可以極大地提高您的isNotPrime函數。您可以通過對偶數進行特殊測試來加倍速度，然後僅測試奇數直到平方根，但與Miller Miller Rabin測試等算法相比，這仍然非常低效。在Rosetta Code網站上的這個版本將始終爲少於​​25位數的任何數字提供正確的答案。對於大型素數來說，這隻會在使用試驗分區所花的時間的很小一部分時間內運行。當你在處理整數時，你應該避免使用浮點指數運算符**（儘管我剛剛鏈接的Rosetta代碼也是這樣做的！）。在特定情況下，事情可能會正常工作，但當Python必須從浮點轉換爲整數時，或者當整數太大而無法精確表示浮點時，它可能是一個微妙的錯誤來源。您可以使用有效的整數平方根算法。這裏有一個簡單的例子：

def int_sqrt(n): 
    if n == 0: 
     return 0 
    x = n 
    y = (x + n//x)//2 

    while (y<x): 
     x=y 
     y = (x + n//x)//2 

    return x