Существует ли быстрый алгоритм для функции Эйлера для больших чисел (128 бит)? - PullRequest
Новая
       14

Существует ли быстрый алгоритм для функции Эйлера для больших чисел (128 бит)?

0 голосов
/ 10 сентября 2018

Мне нужно получить фи-функцию (Эйлера) некоторых случайно сгенерированных 128-битных чисел.Я попытался использовать этот код ниже, но компьютер просто слишком много думает. 

import fractions

def phi(n):
    amount = 0        
    for k in range(1, n + 1):
        if fractions.gcd(n, k) == 1:
            amount += 1
    return amount

Есть ли что-то быстрее?

1 Ответ

0 голосов
/ 10 сентября 2018

Для 128-битных чисел вы захотите эффективно вычислить простую факторизацию n, а затем использовать 

totient = n
for factor in prime_factors(n):
    totient -= totient // factor

Сложной является факторизация. Для 128-битных чисел простое пробное деление будет ужасно неэффективным. Что-то вроде факторизации эллиптической кривой или квадратичного сита было бы лучше, но писать их вручную сложно. Вероятно, лучше использовать библиотеку.

Лучшая реализация Python для алгоритма факторизации большого числа, который я нашел, это, верите вы этому или нет, этот ответ от primo на codegolf.stackexchange.com. Это многочленное квадратичное сито.

primefac (Python 2) и labmath (Python 3) включают квадратичное сито, но оно основано на старой, несколько медленной и ошибочной версии кода Гольф ответ. Если вы хотите фиксированную версию, вы можете перейти к ответу Code Golf. (Также имейте в виду, что labmath.factorint по умолчанию не использует реализацию mpqs.) labmath и primefac также включают факторизацию эллиптической кривой и некоторые другие алгоритмы, которые с меньшей вероятностью будут полезны для этого входного размера.

Кроме этого, есть sympy.ntheory.factorint, но у него были проблемы с большими факторами в моих тестах, и у него только пробное деление, Polard Rho и факторизация P-1 Polard.

В любом случае, используйте один из этих существующих вариантов факторизации, или реализуйте свой собственный, или какой-либо другой, а затем создайте свою функцию totoent. Например, используя primefac: 

# primefac.factorint(n) returns a factor:multiplicity dict
from primefac import factorint

def totient(n):
    totient = n
    for factor in factorint(n):
        totient -= totient // factor
    return totient
...