Эффективный поиск примитивных корней по модулю n с использованием Python?

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] 

---

Изменения:

• В настоящее время используется 3-й аргумент метода pow для модуля.
• Переведено на gcd встроенная функция, определенная в math (для Python 3.5) для ускорения скорости.

---

Дополнительная информация о встроенных НОД здесь:Co-primes checking

Answer 3

В частном случае, когда р является простым, следующий хороший немного быстрее:

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, используя более эффективный алгоритм. Вы можете удвоить скорость, выполнив специальный тест для четных чисел, а затем тестируя нечетные числа до квадратного корня, но это все еще очень неэффективно по сравнению с таким алгоритмом, как тест Миллера Рабина. Эта версия на сайте 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