Как реализовать факторизацию для числа больше 300 символов?

Question

[s1eepy]

У меня проблема. Мне даны числа длиной 309 символов
N=3030642576165942514244846932017214763267597237228851423971725227852448501621494677770772626167636346836043370043776556377672612393694156650080294923491656774270297835830691819365631476152833243761676761284450810253195741763806661956295880535771914878382524356687259890302543028387814854963781707333811249106203
У меня не получается самый первый шаг: факторизовать число. Я пробую через Maple и алгоритм разложения чисел на простые множители. Эти алгоритмы работают уже 40 минут, но никакого результата нет. Как реализовать программу или через что подойти к нахождению p и q? Необходимо чтобы вычисления проводились менее 20 минут

Comments

[pfg21]

не кисло так студентиков на жизнь натягивают :)

[rPman]

pfg21, нормальная практика, давать неофитам нерешаемые задачи... вдруг кто то это решит, такое было и не раз, именно так науку и двигают

Answer 1

[rPman]

Вы хотите разложить на множители 1024бит число? за 20 минут?
https://ru.wikipedia.org/wiki/RSA-числа

RSA-240 имеет 240 десятичных знаков (795 бит) и было успешно факторизовано 2 декабря 2019 года Эмманюэлем Томе и его коллегами[6][7]. Для выполнения задачи было использовано несколько кластеров компьютеров в разных странах.

Comments

[Lynn «Кофеман»]

Я б даже сразу дал ссылку сюда =)
https://ru.wikipedia.org/wiki/RSA-%D1%87%D0%B8%D1%...

RSA-1024 имеет 1024 бита (309 десятичных знаков) и пока что не факторизовано. За факторизацию был объявлен денежный приз в 100 000 долларов США.

Answer 2

[alexalexes]

За 20 минут можно решить только с помощью алгоритма Шора.
Только есть маленькая деталь - вам понадобится квантовый компьютер с достаточным числом кубитов, чтобы работать с данным N.
А если без шуток, то могу подкинуть идею, где можно сделать научный эксперимент, хоть и получить отрицательный результат.
Берете нейронную сеть, такую, чтобы на входе подать побитово число N.
Выход нейронки нужно сделать так, чтобы она побитово отражала два числа, такой же разрядностью как N.
Эти два числа - интервал, в котором с большой вероятностью, по мнению нейронки, будет находится одно из чисел P или Q.
Обучаете нейронную сеть на N той разрядности, по которой построен ее побитовый вход. Даете возможность в ходе обучения варьировать различной ширины интервала на выходе, оцениваете ошибки попадания интервала в известное P при проверке результата обучения.
Из этой научной работы нужно вытащить график - зависимость ширины интервала факторизуемого числа от вероятности обученной нейронки определять верно этот интервал. Возможно, в графике добавите третью ось - глубина нейронных слоев.
Сделаете эту работу и вас кандидатская в кармане.