The Montgomery Curve is introduced by Peter L. Montgomery for speeding up the Pollard and Elliptic Curve Methods of integer factorization. Montgomery Curves are in the form $By^2=x^3+Ax^2+x$ and it is also represented as $M_{A,B}$.
Addition and Doubling Formulas of Montgomery Curves
Given Montgomery Curve $By^2=x^3+Ax^2+x$ and the point $P_1 = (x_1,x_1)$ and $P_2 = (x_2,x_2)$ than the addition and doubling, $P_3 = (x_3,x_3) = P_1+P_2$ as follows
- Addition formula in Affine Coordinates: $(P1 \neq \pm P2)$
\begin{align}
\alpha & = (y_2 − y_1)/(x_2 − x_1)\\
x_3 & = B \alpha^2 − A − x_1 − x_2\\
y_3 & = \alpha (x_1 − x_3) − y_1
\end{align}
- Doubling formula in Affine Coordinates: $(P1 = P2)$
\begin{align}
\alpha & = (3x_1^2 + 2 A x_1 + 1)/(2 B y_1)\\
x_3 & = B\alpha^2 − A − 2x_1\\
y_3 & = \alpha (x_1 − x_3) − y_1
\end{align}
As usual, these are calculated from the geometrical meaning of addition.
Montgomery Ladder
The Montgomery Ladder is an algorithm to calculate $[x]P$ for a given scalar $x$ and a point $P$.
Represent $x$ in binary $x= x_0 + 2x_1 + 2^2x_2 + \cdots + 2^mx_m $ and let $m= \lfloor \log_2 x \rfloor$.
R0 = 0
R1 = P
for i from m downto 0 do
if xi = 0 then
R1 = point_add(R0, R1)
R0 = point_double(R0)
else
R0 = point_add(R0, R1)
R1 = point_double(R1)
return R0
Calculation
Now, $x=3 = 1 + 2\cdot 1$, i.e. $x_0=1$ and $x_1 =1$
$m= \lfloor \log_2 3 \rfloor = 1$. Therefore, we visit the loop twice.
since $x_i =1$ we will be always in the else case, or simply we run the below.
1. R0 = 0
2. R1 = P
3. R0 = point_add(R0, R1)
4. R1 = point_double(R1)
5. R0 = point_add(R0, R1)
6. R1 = point_double(R1)
7. return R0
- $R_0 = \mathcal{O}$
- $R_1 = P$
- $R_0 = \mathcal{O} + P = P$
- $R_1 = P + P = [2]P$
- $R_0 = [2]P+P = [3]P$
- $R_1 = [2]P+[2]P = [4]P$
- return $R_0 = [3]P$
The given Montgomery Curve $3y^2=x^3+x^2+x$ than it is $M_{1,3}$ so $A=1,B=3$ and $P=(9,8)$
$[2]P = (1,10)$ by the below simple sage math point doubling.
k.<a> = GF(11, modulus="primitive")
k.modulus()
A = k(1)
B = k(3)
x1 = k(9)
y1 = k(8)
alpha = (3*x1^2 + 2 *A * x1 + 1)/(2 * B * y1)
x3 = B * alpha^2 - A - 2 * x1
y3 = alpha *(x1 - x3) - y1
print x3
print y3
$[3]P = [2]P+P = (5,2)$ by the below simple sage math point addtion.
k.<a> = GF(11)
A = k(1)
B = k(3)
x1 = k(9)
y1 = k(8)
x2 = k(1)
y2 = k(10)
alpha = (y2 - y1)/(x2 - x1)
x3 = B * alpha^2 - A - x1 - x2
y3 = alpha * (x1 - x3) - y1
print x3
print y3
Notes :
