Регистрация Войти
Рейтинг:1
Dimitri Koshelev avatar Crypto

Факторизация произведения двух конкретных простых чисел

флаг id
Dimitri Koshelev

Помоги мне, пожалуйста.

Рассмотрим конкретные простые числа $р = х^{д} + 1$ и $д = х^{е} + 1$ для некоторых $x, d, e \in \mathbb{N}$. Может ли их продукт $n = pq$ разложить на множители быстрее, чем произведение общих простых чисел? Другими словами, существует ли алгоритм факторизации, более подходящий для таких $р$, $q$ чем современные алгоритмы для простых чисел общего вида?

Заранее благодарю за ответ.

73
0 + 0
Рейтинг:4
poncho avatar Crypto
флаг my
poncho

Другими словами, существует ли алгоритм факторизации, более подходящий для таких $р, д$ чем современные алгоритмы для простых чисел общего вида?

Если вы знаете, что $n$ имеет форму $(х^d+1)(х^е+1)$, факторизация должна быть тривиальной.

$n = x^{d+e} + x^d + x^e + 1 \приблизительно x^{d+e}$ (если только $х^д$ или же $х^е$ маленький). Мы можем легко просмотреть возможные значения $\sqrt[d+e]{n}$ для различных возможных значений $d+e$, и найдите тот, который дает близкое к целому значение $х$; что дает нам $х$ и $d+e$; на данный момент мы знаем $n - (x^{d+e} + 1) = x^d + x^e$, отсюда, восстановление $д$ и $е$ легко.

А если (скажем) $х^д$ мал, то простой поиск по мелким множителям (либо перебором, либо, если хотите, пофантазировать, ЭЦМ) быстро найдет $х^д+1$

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

0 + 0
Dimitri Koshelev avatar
флаг id
Dimitri Koshelev
пончо, спасибо. Что, если $p = x^d + 1$, но $q$ — обычное простое число?
0
Ответить
poncho avatar
флаг my
poncho
@DimitriKoshelev: на самом деле все простые числа $p$ имеют такую ​​форму (с $d=1$ :-)
0
Ответить
Dimitri Koshelev avatar
флаг id
Dimitri Koshelev
что если $x$ мало?
0
Ответить
Рейтинг:1
Einar Rødland avatar Crypto
флаг pk
Einar Rødland

Вот дополнение к ответу пончо.

Обратите внимание, что $n-1=x^{d+e}+x^d+x^e$ который кратен $ х ^ {\ мин (д, д)} $. Пока не $х$ велико, его легко найти, ища малые множители $n-1$; далее, во сколько раз эти маленькие множители делят $n-1$, который должен быть $\мин(д,д)$ раз (кроме частного случая $х=2$ и $д=е$).

Этот метод особенно эффективен для небольших $х$. И если он не дает решения с малым или относительно небольшим значением $х$, вы находитесь в обстановке, где подход пончо будет очень эффективным.

0 + 0
Dimitri Koshelev avatar
флаг id
Dimitri Koshelev
Эйнар Рёдланд, спасибо. Что, если $p = x^d+1$, но $q$ — обычное простое число?
0
Ответить
Einar Rødland avatar
флаг pk
Einar Rødland
@DimitriKoshelev: Вы можете позволить $d=1$, $x=p-1$, и нет никаких ограничений на $p$. Если $x$ мало, а $p$ велико, то возможные значения $p$ более ограничены. Не могу сразу придумать ничего лучше, чем метод проб и неудач.
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.