Когда можно разложить на множители большое полупростое число?

При каких условиях можно разложить на множители большое полупростое число? В частности, является ли следующее 400-значное полупростое число действительно тривиальным для разложения на простые числа?

6962155154859963260211100482357357666900094513013513488352858667799199787495340476167566639530574848375895722792291996203873323650274512138128403360943634134259376986501375967452208380337012919869885380406071772232795575963202558402893589313281327208179913789760736615950818685956393838601277519011418885197723428318400763080858914698836058070301404903262955501113318317950597435778777212408626799143

Слово «тривиальный» почти наверняка не подходит для этого. Лучше спросить, разумно ли эффективно использовать фактор. Во-первых, стоит упомянуть, что ваш полупрайм равен 400. десятичный цифры. Умножив это на $\log_2(10)$, мы видим, что это $\около 1300$ биты длинные. Это намного больше, чем самая большая заявленная запись факторинга (полупростых чисел) в 829 бит. Так что ответ "нет", если только ваше полупростое число не имеет особой структуры, которая делает его "слабым".

Какую особую структуру могут иметь полупростые числа? Позволять $N = p_1p_2$ быть факторизацией. Есть несколько кандидатов, которые работают, если

1. Один из $p_i$ является небольшой (скажем, не более $\около 60$ биты), то метод эллиптических кривых разумно бежать.

2. Один из $p_i$ таков, что $p_i+1$ является гладкий, например все основные факторы $p_i+1$ ограничены некоторым разумно малым числом $В$. затем Уильямс $р+1$ алгоритм разумный.

3. Один из $p_i$ таков, что $p_i-1$ является пауэрглад, например все самое лучшее сила факторы $p_i-1$ ограничены некоторым разумно малым числом $В$. затем Полларда $p-1$ алгоритм разумно.

Возможно, есть еще несколько «особых структур», которые я упустил (кажется, я помню одну, если $p_1\приблизительно p_2$, но сейчас не могу вспомнить название). Ваш единственный реальный шанс разложить число на множители состоит в том, что оно будет сгенерировано неправильно, и все вышеперечисленное может быть примерами, поэтому, если у вас нет конкретной причины думать, что они сгенерированы неправильно (скажем, это вызов CTF), я бы не пытайся сломать его.

Если у вас есть причина думать, что это должно быть сгенерировано неправильно, существуют их реализации. Например, Мудрец имеет реализацию ECM (через GMP-ECM). в GMP-ECM сама страница, я также вижу ссылки на $p-1$ и $р+1$, но я не знаю, пытается ли sage их напрямую (поскольку они действительно полезны, только если вы подозреваете, что полупростые числа были сгенерированы неправильно).

Но не столкнувшись ни с одним из этих случаев "слабых полупростых чисел" (что крайне маловероятно, если полупростое число сгенерировано должным образом --- поэтому, если у вас нет причин думать, что это слабый RSA semiprime, наверное, даже не стоит проверять).

Используемый метод заключался в том, чтобы привести N к специальной форме, которую легко факторизовать.

Отобразил N в двоичном формате и заметил сотни нулей между 4 числами.

Это было сокращено до следующего:

Н = а2^1228+б2^875+с*2^353+д

куда а= 1506291488774150974626762365373 б = 322571915263178581 с= 576377099039115423 д = 123431

Рассматривая это как многочлен от x, где x = 2:

Н = ах^1228+бх^875+с*х^353+д

Это очень быстро влияет на:

(359561509069941х^353+77)(4189245652768553*x^875 + 1603)

В комментарии @Sam Blake задал дополнительный вопрос о факторе целого числа:

7215955072690155355400859323297730634528493510676300043022948136348249037517276095868127042993906604904230826475281383188764473510881994780947137238252071087749294743150564851420395422525735221770067605216401023

Вопрос в том, действительно ли это второе полупростое число тривиально для разложения на простые числа?

Это полупростое число не является слабым, потому что оно не очень легко отказывается от своей особой формы.

Это слабо для противника с возможностями национального государства, потому что это всего 701 бит. Рекомендуется модуль 2048 бит или выше с равной битовой длиной p и q.

Кроме того, у него нет слабости при использовании Ферма, p-1, его отношение не близко к маленькому. фракция, ECM не помогает.

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

Какие подсказки вы готовы дать? Что это полупремьер? что факторы имеют разную длину? Факторы представляют собой многочлены с членами: a0 x 2^(k0) + a1 x 2^(k1) + a2 x 2^(k2)...