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

как рассчитать 2 г, 3 г,

флаг ca
Ramin Najafi

$у^2=х^3+9х+17$ над $\mathbb{F}_{23}$, что такое дискретный логарифм $к$ из $Q=(4,5)$ на базу $P=(16,5)$?

Один (наивный) способ найти k состоит в том, чтобы вычислить кратные $P$ до тех пор $Q$ находится. Первые несколько кратных $P$ находятся:

$P=(16,5)$, $2P=(20,20)$, $3P=(14,14)$, $4P=(19,20)$, $5P=(13,10)$, $6P=(7,3)$, $7P=(8,7)$, $8P=(12,17)$, $9P=(4,5)$

С $9P=(4,5)=Q$, дискретный логарифм $Q$ на базу $P$ является $к=9$.

Как нам получить эти скалярные кратные?

$P=(16,5),2P=(20,20),3P=(14,14),4P=(19,20),5P=(13,10), 6P=(7,3),7P =(8,7),8P=(12,17),9P=(4,5)$

75
0 + 0
kelalaka avatar
флаг in
kelalaka
Вы спрашиваете, как добавляются баллы? [как эти формулы] (https://crypto.stackexchange.com/q/66288/18298)? И [скалярное умножение] (https://crypto.stackexchange.com/q/68593/18298). Обратите внимание, что повторение проще, чем скалярное умножение. Для небольших групп эллиптических кривых это 23, это легко сделать с помощью итерации, для больших групп вам могут понадобиться алгоритмы дискретного журнала, такие как Поллард $\rho$, чтобы решить до некоторой границы.
1
Ответить
Ramin Najafi avatar
флаг ca
Ramin Najafi
Да, но я не понимаю, как.
0
Ответить
kelalaka avatar
флаг in
kelalaka
Добавление точек на эллиптическую кривую имеет геометрический смысл, как вы можете видеть по одной из ссылок. Это называется правилом касательной и хорды. Доказательство правила касательной и шнура из группы, особенно ассоциативности, — долгий процесс. Прочтите [эллиптические рассказы] (https://www.amazon.com/Elliptic-Tales-Curves-Counting-Number/dp/0691163502) и/или [Вашингтонскую книгу] (https://www.amazon.com/Elliptic -Кривые-Криптография-Математика-Приложения/dp/1420071467/)
0
Ответить
kelalaka avatar
флаг in
kelalaka
Чтобы добавить две точки, нарисуйте линию и найдите третье пересечение, отразив эту точку на оси x. Можно использовать уравнение кривой и уравнение линии, чтобы алгебраически найти точку пересечения. Вы можете увидеть это просто на [картинках] (https://crypto.stackexchange.com/a/91687/18298)
0
Ответить
fgrieu avatar
флаг ng
fgrieu
Чтобы получить скалярные множители $2P$, $3P$, …$9P$: примените формулы удвоения и сложения точек, приведенные в [ответ @kelalaka] (https://crypto.stackexchange.com/a/66296/555). ), раздел "Групповой закон об аффинных координатах", случай 3, со второй формулой для $\lambda$ при вычислении $2P=P+P$ и первой формулой для $\lambda$ при последующем вычислении $k\,P =(k-1)P+P$. Напомним, что деление производится в $\mathbb F_{13}$, поэтому $u/v$ равно $u\,v^{-1}$, где $v^{-1}$ – мультипликативная обратная $w$ к $ v$, такое что $v\,w\equiv1\pmod{23}$. $w=v^{-1}$ можно вычислить с помощью расширенного алгоритма Евклида.
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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