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

Нахождение элемента $\mathbb{Z}_p$, если известен порядок этого элемента

флаг cn
mangart

У меня есть два простых числа $р$ (1024 бита) и $q$ (160 бит), так что $q$ делит $p-1$. Теперь я хочу найти элемент $b$ в $\mathbb{Z}_p$ с заказом $q$. Что означает, что $b^q \эквив 1 \mod p$.

я пытался выбрать $b$ случайным образом, а затем проверить, выполняется ли сравнение, но кажется, что это не очень хороший подход, поскольку он не дает ответа за разумное время. Так есть ли способ найти $b$ эффективно?

32
0 + 0
флаг us
Mikero
Я думаю, это другой вопрос, потому что найти генератор методом проб и ошибок будет гораздо проще, чем найти элемент с другим порядком. Я думаю, что вероятность попадания в элемент с нетривиальным порядком равна $1 - \varphi(n)/n$, что, как правило, пренебрежимо близко к нулю (вероятность попадания в генератор равна $\varphi(n)/n$). Это говорит о необходимости более эффективного подхода, чем метод проб и ошибок, который работает для поиска генератора.
0
Ответить
kelalaka avatar
флаг in
kelalaka
**Из ответа Пончо:** Одним из простых способов выбора генератора случайных чисел является выбор случайного значения $h$ между 2 и $p-1$ и вычисление $h^{(p-1)/q} \bmod р$; если это значение не равно 1 (и с высокой вероятностью не будет), то $h^{(p-1)/q} \bmod p$ — ваш генератор случайных чисел.
2
Ответить
mangart avatar
флаг cn
mangart
@kelalaka Насколько я знаю, генератор — это элемент, который может генерировать все элементы группы, поэтому порядок этого элемента будет $p-1$, но я пытаюсь найти элемент $b$, который имеет порядок $q$, который много меньше $p-1$, а также $b$ по этому определению не является генератором группы.
0
Ответить
kelalaka avatar
флаг in
kelalaka
Вот что включает в себя ответ. Внимательно прочитайте.
1
Ответить
mangart avatar
флаг cn
mangart
@kelalaka О, я вижу, ответ на самом деле находится в статье Википедии, связанной с этим ответом, о группе Шнорра. Так что это фактически отвечает на мой вопрос. Большое спасибо и извините, что не прочитали предложенный вами вопрос более внимательно в первый раз.
0
Ответить
poncho avatar
флаг my
poncho
Если $q$ простое число, мой ответ правильный. Если это не так, но известна его факторизация, то мой ответ (который работает на некоторых простых пост-тестах). Если факторизация неизвестна, то я не верю, что существует способ, который работает все время (но вы можете найти способ, который работает с вероятностью $> 0,99$).
1
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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