Curva de Edwards torcida

Seja ${\displaystyle \mathbb {K} }$ um corpo com característica diferente de 2. Sejam ${\displaystyle (x_{1},y_{1})}$ e ${\displaystyle (x_{2},y_{2})}$ pontos na curva de Edwards torcida. A equação da curva de Edwards torcida é escrita como;

${\displaystyle E_{E,a,d}}$: ${\displaystyle ax^{2}+y^{2}=1+dx^{2}y^{2}}$.

A soma desses pontos ${\displaystyle (x_{1},y_{1}),(x_{2},y_{2})}$ em ${\displaystyle E_{E,a,d}}$ é:

${\displaystyle (x_{1},y_{1})+(x_{2},y_{2})=\left({\frac {x_{1}y_{2}+y_{1}x_{2}}{1+dx_{1}x_{2}y_{1}y_{2}}},{\frac {y_{1}y_{2}-ax_{1}x_{2}}{1-dx_{1}x_{2}y_{1}y_{2}}}\right)}$

O elemento neutro é (0,1) e o negativo de ${\displaystyle (x_{1},y_{1})}$ é ${\displaystyle (-x_{1},y_{1})}$.

Essas fórmulas também funcionam para duplicação. Se a é um quadrado em ${\displaystyle \mathbb {K} }$ e d é um não quadrado em ${\displaystyle \mathbb {K} }$, essas fórmulas são completas: isso significa que podem ser usadas para todos os pares de pontos sem exceções; portanto, elas funcionam para duplicação também, e elementos neutros e negativos são aceitos como entradas.^[3]

Exemplo de adição

Dada a seguinte curva de Edwards torcida com a = 3 e d = 2:

${\displaystyle 3x^{2}+y^{2}=1+2x^{2}y^{2}}$

é possível somar os pontos ${\displaystyle P_{1}=(1,{\sqrt {2}})}$ e ${\displaystyle P_{2}=(1,-{\sqrt {2}})}$ usando a fórmula dada acima. O resultado é um ponto P₃ que possui as coordenadas:

${\displaystyle x_{3}={\frac {x_{1}y_{2}+y_{1}x_{2}}{1+dx_{1}x_{2}y_{1}y_{2}}}=0,}$

${\displaystyle y_{3}={\frac {y_{1}y_{2}-ax_{1}x_{2}}{1-dx_{1}x_{2}y_{1}y_{2}}}=-1.}$

A duplicação pode ser realizada com exatamente a mesma fórmula da adição. A duplicação de um ponto ${\displaystyle (x_{1},y_{1})}$ na curva ${\displaystyle E_{E,a,d}}$ é:

${\displaystyle 2(x_{1},y_{1})=(x_{3},y_{3})}$

onde

${\displaystyle {\begin{aligned}x_{3}&={\frac {x_{1}y_{1}+y_{1}x_{1}}{1+dx_{1}x_{1}y_{1}y_{1}}}={\frac {2x_{1}y_{1}}{ax_{1}^{2}+y_{1}^{2}}}\\[6pt]y_{3}&={\frac {y_{1}y_{1}-ax_{1}x_{1}}{1-dx_{1}x_{1}y_{1}y_{1}}}={\frac {y_{1}^{2}-ax_{1}^{2}}{2-ax_{1}^{2}-y_{1}^{2}}}.\end{aligned}}}$

Os denominadores na duplicação são simplificados usando a equação da curva ${\displaystyle dx^{2}y^{2}=ax^{2}+by^{2}-1}$ (nota: ajustado do formato original dependendo da curva). Isso reduz a potência de 4 para 2 e permite um cálculo mais eficiente.

Exemplo de duplicação

Considerando a mesma curva de Edwards torcida dada no exemplo anterior, com a=3 e d=2, é possível dobrar o ponto ${\displaystyle P_{1}=(1,{\sqrt {2}})}$. O ponto 2P₁ obtido usando a fórmula acima tem as seguintes coordenadas:

${\displaystyle x_{3}={\frac {2x_{1}y_{1}}{ax_{1}^{2}+y_{1}^{2}}}={\frac {2{\sqrt {2}}}{5}},}$

${\displaystyle y_{3}={\frac {y_{1}^{2}-ax_{1}^{2}}{2-ax_{1}^{2}-y_{1}^{2}}}={\frac {1}{3}}.}$

É fácil ver, com alguns pequenos cálculos, que o ponto ${\displaystyle P_{3}=\left({\frac {2{\sqrt {2}}}{5}},{\frac {1}{3}}\right)}$ pertence à curva ${\displaystyle 3x^{2}+y^{2}=1+2x^{2}y^{2}}$.

As coordenadas do ponto ${\displaystyle (X_{1}:Y_{1}:Z_{1})}$ são chamadas de coordenadas de Edwards torcidas invertidas na curva ${\textstyle (X^{2}+aY^{2})Z^{2}=X^{2}Y^{2}+dZ^{4}}$ com ${\textstyle X_{1}Y_{1}Z_{1}\neq 0}$; este ponto mapeia para o afim ${\displaystyle (Z_{1}/X_{1},Z_{1}/Y_{1})}$ em ${\displaystyle E_{E,a,d}}$. Bernstein e Lange introduziram essas coordenadas invertidas para o caso a=1 e observaram que as coordenadas economizam tempo na adição.

A equação para a curva de Edwards torcida projetiva é dada como: ${\displaystyle (aX^{2}+Y^{2})Z^{2}=Z^{4}+dX^{2}Y^{2}}$ Para Z₁ ≠ 0 o ponto (X₁:Y₁:Z₁) representa o ponto afim (x₁ = X₁/Z₁, y₁ = Y₁/Z₁) em E_E,a,d.

Expressar uma curva elíptica na forma de Edwards torcida economiza tempo na aritmética, mesmo quando a mesma curva pode ser expressa na forma de Edwards.

A duplicação na curva torcida projetiva é dada por

(X₃:Y₃:Z₃) = 2(X₁:Y₁:Z₁).

Isto custa 3 Multiplicações + 4 elevações ao Quadrado (Squarings) + 1D + 7 adições, onde 1D é uma multiplicação por a.

Algoritmo

B = (X₁ + Y₁)²

C = X₁²

D = Y₁²

E = aC

F = E + D

H = Z₁²

J = F − 2H

X₃ = (B − C − D).J

Y₃ = F · (E − D)

Z₃ = F · J^[1]