Gennadiy UsovBarloneпропущено...
Большое. Для числа с 5000 десятичных знаков еще можно дождаться результата (несколько минут). Для чисел порядка используемых в RSA криптографии ответ за меньше секунды.Тогда, получается, нет проблем с выбором простого числа рядом со случайным числом для RSA?

И тогда зачем поиск любого решета?
Обратите внимание на возведение в степень по модулю.
https://www.programiz.com/python-programming/methods/built-in/pow

Gennadiy Usovmaytonпропущено...
Обратите внимание на возведение в степень по модулю.
https://www.programiz.com/python-programming/methods/built-in/pow А при чём здесь возведение в степень?

Ведь было
Gennadiy UsovПолучается, что формируется число 2^(4566373287117-1), которое представляет собой двоичное число, длиной (4566373287117-1), у которого первая цифра 1, а остальные цифры 0.Формируем такое число без возведения в степень ...
Я комментирую формулу которую привел Барлон.
Он не возводит двойку в степень. Он возводит двойку в степень по модулю 4566373287117.
Это другая операция которая может использовать другие алгоритмы и требовать к примеру
меньше памяти чем просто операция степени.

На самом деле я не знаю как под капотом она реализована. Я просто акцентирую твоё внимание.
Ведь ты всё время спрашиваешь - возможно-ли... сколько займет времени.

Мог бы зайти на ideone.com и просто попробовать.