Вычисление функции Эйлера занимает очень много времени для 1024-х битного числа

Если сможете найти функцию Эйлера для вашего числа, будьте так добры, киньте сюда описание алгоритма, хорошо? Мы быстренько замутим ломалку для RSA ;)

А если серьезно, то вычисление функции Эйлера выполняется через разложение числа на простые множители. У вас число длиной 1024 бит. Если оно состоит из двух множителей по 512 бит, то ... Такие задачи человечество решать пока не умеет. Если вы сумеете разложить, то можете претендовать на приз в 100 тысяч долларов На сегодняшний день пока лучшее достижение - это 829 бит, потребовавшее 2700 ядро-лет, причем это не тривиальный перебор как у вас, а весьма продвинутые методы решета числового поля.

Кто над вами так недобро пошутил?

РАЗМИНКА

Если вы всерьёз настроились вычислять функцию Эйлера для больших чисел, потренируйтесь для начала на кошечках.

• кошечка поменьше: 90377629292003121684002147101760858109247336549001090677693

• кошечка побольше: 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139

Ответы в конце этого поста.

ВАРИАНТ ПОПРОЩЕ: РЕШЕТО ЭРАТОСФЕНА

Самый простой способ ускорить разложение на множители - взять готовую таблицу простых чисел и делить.

Я скачал отсюда архив с простыми числами от 0 до 10 миллиардов (размер 758 мегабайт, в распакованном виде 5,2 гига :) , всего 455 миллионов чисел), распаковал и прогнал

import glob

target = 303064257616594251424484693201721476326759723722885142397172522785244850162149467777077262616763634666043370043776556377672612393694156650080294923491656774270297835830691819365631476152833243761676761284450810253195741763806661956295880535771914878382524356687259890302543028387814854963781707333811249106203
# target = 303064257616594251424484693201721476326759723722885

files = glob.glob("./*_to_*.txt")
files_count = len(files)
for i, name in enumerate(files):
    print("%.2f%%" % ((i + 1) / files_count * 100))

    with open(name) as f:
        for num_bytes in f.readlines():
            num = int(num_bytes.strip())
            if target % num == 0:
                print(num)
                exit(0)

Среди первых 455 миллионов простых чисел делители не обнаружены.

upd Проверил ещё 427 миллионов простых чисел (от 10 млрд до 20 млрд) - делителей нет.

upd И ещё 417 миллионов простых чисел (от 20 млрд до 30 млрд) - делителей нет.

upd дальше перебирать делители не буду, мой компьютер устал :)

Подозреваю, что вы пытаетесь хакнуть 1024-х битный приватный ключ RSA. Единственное, чем могу помочь, это пожелать удачи и долгих лет жизни. Делителей мало, но вы держитесь!

BTW: для начала в онлайновом тесте Миллера-Рабина убедился, что число составное.

ВАРИАНТ ПОСЛОЖНЕЕ: РО-МЕТОД ПОЛЛАРДА, ФАКТОРИЗАЦИЯ НА ЭЛЛИПТИЧЕСКИХ КРИВЫХ, КВАДРАТИЧНОЕ РЕШЕТО

Решето Эратосфена - простой, универсальный, ограниченно полезный способ разложения на множители. С его помощью можно разложить числа до 10^25 -- для больших чисел таблицы не поместятся на диск.

В 70-е годы были изобретены несколько существенно более эффективных методов факторизации - ро-метод Полларда, p−1-метод Полларда, факторизация на эллиптических кривых, квадратичное решето.

Некоторые из них можно объяснить на пальцах, некоторые требуют знания алгебры на уровне первого курса мехмата, но их все объединяет тот факт, что добрые люди реализовали эти методы для python и даже собрали в один пакет: https://pypi.org/project/primefac/

Функция multifactor из этого пакета стартует несколько параллельных процессов, каждый из которых пытается разложить число одним из этих алгоритмов.

Вычисление функции Эйлера средствами primefac можно реализовать вот как:

from primefac import multifactor, isprime, ispower

def simplify(p):
    # Некоторые методы возвращают степень простого делителя
    # В этой функции возвращается собственно простой делитель
    while not isprime(p):
        pp = ispower(p)
        if pp is None:
            break
        if isinstance(pp, tuple):
            p, _ = pp
            continue
        if isinstance(pp, int):
            if pp > 0:
                p = pp
            else:
                return p
    return p

def factor(n):
    # Возвращает список простых делителей
    dividers = []
    while n > 1 and not isprime(n):
        p, _ = multifactor(n)
        p = simplify(p)
        while (n % p == 0):
            n = n//p
            dividers.append(p)
    if n > 1:
        dividers.append(n)
    return dividers

def phi(dividers):
    # Вычисляет функцию Эйлера по списку простых делителей
    dividers = sorted(dividers)
    result = 1
    last = 1
    for p in dividers:
        if p == last:
            result *= p
        else:
            result *= (p-1)
            last = p
    return result

Численный эксперимент - разложение нескольких мелких и нескольких больших чисел

def test(n):
    dividers = factor(n)
    print(n, '=', " * ".join([str(p) for p in dividers]))
    print("phi(", n, ") = ", phi(dividers))


for n in [625, 1021, 1023, 1024, 12345678901, 1111222222222222222132191110000000000000089789, 90377629292003121684002147101760858109247336549001090677693]:
    test(n)

Результат

625 = 5 * 5 * 5 * 5
phi( 625 ) =  500
1021 = 1021
phi( 1021 ) =  1020
1023 = 33 * 31
phi( 1023 ) =  960
1024 = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2
phi( 1024 ) =  512
12345678901 = 857 * 14405693
phi( 12345678901 ) =  12331272352
1111222222222222222132191110000000000000089789 = 11112222222222222222211 * 99999999999999999991999
phi( 1111222222222222222132191110000000000000089789 ) =  1111222222222222222132079997777777777777875580
90377629292003121684002147101760858109247336549001090677693 = 773951836515617 * 588120598053661 * 760926063870977 * 260938498861057
phi( 90377629292003121684002147101760858109247336549001090677693 ) =  90377629292002386108576103662584609670781701742006747791360

Скорость факторизации очень сильно зависит от размеров числителей. Так, 60-значное число 90377629292003121684002147101760858109247336549001090677693 раскладывается в разы быстрее 45-значного 1111222222222222222132191110000000000000089789.

ВАРИАНТ СОВСЕМ СЛОЖНЫЙ: ОБЩЕЕ РЕШЕТО ЧИСЛОВОГО ПОЛЯ

Для действительно больших чисел изобретены специализированные методы факторизации, названия которых крутятся вокруг сочтания "решето числового поля". Математика там продвинутая, в двух словах не объяснишь. Но стараниями французских математиков воспользоваться этими продвинутыми методами может каждый желающий.

Пакет CADO-NFS использовать проще простого:

• скачать исходники отсюда: https://cado-nfs.gitlabpages.inria.fr/download.html
• распаковать и выполнить команду make
• после того, как всё скомпилируется, скрипт cado-nfs.py будет готов щёлкать большие числа.

Пакет CADO-NFS пожалуй, самый быстрый способ считать функцию Эйлера для больших чисел размером от 60 десятичных цифр.

ОТВЕТЫ ПРО КОШЕЧЕК

Все эксперименты проводились на 16-ядерном сервере с 64 Гб ОЗУ

90377629292003121684002147101760858109247336549001090677693 = 
  760926063870977 * 588120598053661 * 773951836515617 * 260938498861057
phi = 90377629292002386108576103662584609670781701742006747791360

60 десятичных знаков, время факторизации 33 секунды

1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 = 
  37975227936943673922808872755445627854565536638199 * 
  40094690950920881030683735292761468389214899724061
phi = 1522605027922533360535618378132637429718068114961302618739020630025169470650904690557756570255643880

100 десятичных знаков, время факторизации 33 минуты в пакете CADO-NFS, primefac вообще не справился.