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

Найдите простое число $p$, уязвимое для полига-Хеллмана

флаг kg
kira

Мне нужно найти простое число $р$ со следующими ограничениями:

  • $р$ по крайней мере $1000$ биты длинные
  • $p-1$ является гладким числом с наибольшим делителем ниже $1000$
  • любой фактор $p-1$ может присутствовать несколько раз

Этот номер существует? и если да, то есть ли алгоритм его поиска?

44
0 + 0
fgrieu avatar
флаг ng
fgrieu
Добро пожаловать в крипто-SE.Это похоже на домашнее задание, поэтому я дам только (сильный) намек: предложите простой алгоритм, который строит $r$ со случайным начальным числом с характеристиками, требуемыми для $p-1$ (включая размер), игнорируя пока требование, что $p$ — простое число; затем выведите, используя [Теорему о простых числах] (https://en.wikipedia.org/wiki/Prime_number_theorem) правдоподобную нижнюю границу вероятности того, что $p=r+1$ является простым числом, и из этого приблизительную правдоподобную верхнюю границу ожидаемой стоимости теперь очевидного вероятностного алгоритма. Разумно ответить на свой вопрос.
2
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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