Сколько труда найти таких $n$?

Позволять $W$ быть случайным $200$ битовое число. Сколько работы потребуется, чтобы найти полупростое $n=p_1\cdot p_2$ такой, что $p_1,p_2 > 2^{50} $ и $|W-n|<2^{12}$?

В более общем случае пусть $W_b$ быть случайным целым числом с $b$ биты. Сколько работы потребуется, чтобы найти полупростое $n=p_1\cdot p_2$ такой, что $p_1,p_2 > \sqrt[4]{W_b} $ и $|W_b-n|<\sqrt[8]{W_b}$?

Лучший способ найти такие числа, о котором я знаю, это Алгоритм 3 из статьи Марка Джоя. Модули RSA с заданной частью: методы и приложения. В этом случае, принимая $n=200$, $n_0=150$ и $\каппа'=188$. Первоначальные требования к задаче агрессивны, и вполне возможно, что существуют 200-битные значения $W$ для которого в этом интервале не существует подходящего полупростого числа.Исследование Джоя исследовало сложность метода только экспериментальным путем. Я прочитаю и попытаюсь придумать эвристику.

Несложно описать и эвристически проанализировать «фольклорный» метод выбора 50-битного $р$, параметр $q_0=\lceil W/p\rceil$ и тестирование $q_0$ для первобытности. Это должно занять около 105 различных вариантов $р$ найти простое число $q$ из 150 бит. Для этой пары будут совпадать верхние 150 битов $W$ и с вероятностью около $2^{-38}$ совпадут старшие 188 бит. Это дает общий рабочий бюджет в 44-45 бит тестов на простоту. Метод Джоя, безусловно, улучшит это, но анализ будет более продолжительным.

По общему вопросу с $q\приблизительно\корень 4\n$ и длина интервала $\корень 8\n$, мы ожидаем около $\frac14\корень 8\n\log n$ проверки простоты чисел вокруг $\корень 4\n$ в размере для фольклорного метода, но опять же Джой должен улучшить это.

Если вы используете существующие функции факторинга, эту проблему можно решить за считанные минуты. для 200-битных случайных чисел. Например, функции факторинга от Pari/GP.

Приведенный ниже алгоритм не просто факторизует последовательные числа. Смотри ниже.

Вот общий алгоритм, который был преобразован в рабочий программа:

Сгенерировать W, случайное 200-битное число

предел сетки = 250 праймлимит = 2000000

предварительно вычислить pr = произведение первых предельных простых чисел

Для n1 = от W+1 до W+предел сита

Если n1 имеет вид 6k+1 или 6k+5

 если gcd(n1,pr) равен 1

   f = коэффициент (n1)

      если число факторов n1 равно 2 и оба >2^50   
          распечатать решение f  

Петля

Линия:

если gcd(n1,pr) равен 1

— это быстрый способ пропустить числа с простыми множителями ниже 2-миллионного простого числа.

Шаг precompute pr оптимизирован в Pari/GP и занимает всего 7,785 секунды на медленном оборудовании.

Для наихудшего случая 200-битного числа факторная функция в Pari/GP использует метод MPQS и занимает менее 30 секунд на старом оборудовании.

Вот случайное 200-битное число W: 1567470448908230034126591070540826459978233372650796513704199

Программа факторизует только одно число W+10 и находит решение

р1 = 5346955435967300929
р2 = 293151956787285973328498761492202409914321  

p1 — 63 бита, p2 — 138 бит, n = p1*p2

|W-n| = 10, |W-n|< 2^12