Рейтинг:2

Есть ли причина искать значения Z, отличные от 1, при преобразовании X, Y в якобианское представление точки EC?

флаг om

При обмене открытым ключом я обычно получаю сжатую форму Х, У координаты. Чтобы использовать некоторые ускорения, мне нужно было бы представить это в якобинском х, у, г форма.

Z=1 все устраивает и глядя на прибавки скорости(https://en.wikibooks.org/wiki/Cryptography/Prime_Curve/Jacobian_Coordinates, http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html) Я не вижу очевидной причины, почему Z=1 будет медленнее (или быстрее?), чем любой другой Z, это законный вопрос? Можете ли вы указать мне какое-либо направление насчет того, "есть ли вообще смысл искать Z кроме 1?".

kelalaka avatar
флаг in
Разве не ясно? $Z^4$, то есть 1, когда $Z=1$, а для остальных случаев нужно 3 удвоения.
T. Rossi avatar
флаг om
спасибо за быстрый ответ, когда я умножаю точку на большое число, я делаю кучу сложений, удваиваю, утраиваю и т. д., и мне было интересно, повлияет ли выбор другого z. Я не уверен, что это имеет смысл, как вопрос, еще раз спасибо за терпение.
kelalaka avatar
флаг in
При скалярном умножении точка добавляется снова и снова (удвоение и сложение), здесь нет фиксированной точки.
Рейтинг:2
флаг in

Для удвоения очков (ссылка вики) требуется Z^4 и при использовании с алгоритмом двойного сложения (необходимым для вычисления общедоступных точек, ECDH и подписей на основе EC) с использованием $Z=1$ упрощает расчет Z^4 в противном случае может потребоваться 3 удвоения. Метод двойного сложения, при котором разрешение не фиксируется для экономии времени. Удвойте и добавьте Википедию версия;

let bits = bit_representation(s) # вектор битов (от MSB до LSB), представляющий s
let res = O # точка в бесконечности
для бит в битах:
    res = res + res # двойной
    если бит == 1:            
        res = res + P # добавить
    я = я - 1
вернуть разрешение

Это начало длинной истории. "м-кратное двойное" (повторное удвоение) вычисляет $[2^м]P$ и только вычисляет Z^4 однажды. Когда ты нуждаешься $[к]П$, вам может потребоваться представить $к$ в двоичной форме, затем при необходимости используйте m-кратное удвоение. Чтобы извлечь из этого выгоду, нужно рассчитать стоимость, прежде чем решить, использовать m-fold double или нет.

Ответ не является простым и полным, поскольку Вот этот требует Z1=Z2 с 5М + 2С для дополнения версия Wiki имеет 12М + 4С Стоимость. 5М + 2С все еще Z1 умножение и если Z1=1 что имеет нулевую стоимость.

Короче говоря, в общем, Z1=1 упрощает уравнения.

С $(X_1:Y_1:Z_1)$ представляет собой $(Z/Z^2,Y/Z^3)$ и $(X_1:Y_1:Z_1)$ является отношением эквивалентности, которое $$(X_1:Y_1:Z_1) \sim (\лямбда X_1:\лямбда Y_1:\лямбда Z_1)$$ можно просто преобразовать $Z_1 =1$ с $$(X_1/Z_1:Y_1/Z_1:1)$$

Имейте в виду, что 1/Z1 это не деление, а обратное Z1 на определяющем поле.

Z1 с другой стороны, не остается там с Z1=1 под операции. Чтобы воспользоваться этим, нужно найти обратное и выполнить два умножения. С другой стороны, поиск обратного — это то, чего мы не хотим, поскольку это дорого.

Итак, по крайней мере, есть преимущество в начале скалярного умножения.

T. Rossi avatar
флаг om
Большое тебе спасибо!!
kelalaka avatar
флаг in
Однако далеко не идеальный ответ...

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

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