Elliptic Curve Arithmetic

Raman · 2009-03-23, 18:22

We know that for Elliptic Curves, the group order #E lies somewhere between
$p-2\sqrt p+1$ and $p+2\sqrt p+1$
That is [#E]P = O, where P is any point on Elliptic Curve in a finite field and O is the point at infinity, the product of P with scalar #E is O.
Group order is the number of points in the elliptic curve (mod p), where p is prime.

Elliptic Curves are given by using the equation
$y^2z = x^3+Cx^2z+axz^2+bz^3$

1) What is the best coordinate system to use for Elliptic Curve Factorization Algorithm?
(a) Affine Coordinates (X, Y), z = 1.
(b) Projective Coordinates (X, Y, Z) corresponding to (X/Z, Y/Z)
(0,1,0) is the point at infinity
(c) Modified Projective Coordinates (X, Y, Z) corresponding to (X/Z², Y/Z³)
(d) Montgomery Coordinates (X, Z)

If the group order #E is (B1,B2) smooth, then [k#E]P = O (mod p) but not O (mod N). Since point at infinity is determined by using the Z coordinates, p|GCD(Z,N). The Z coordinate (mod p) would then be degenerate for any multiple of k#E, i.e. remain at 0. k#E is the LCM of all numbers upto B1, and a second stage continuation upto B2, (by using multiples of difference between the consecutive primes between B1 & B2).

2) It is given that, if we choose a curve like this:
$\sigma \ne 0, 1, 5$
$u = \sigma^2 - 5$
$v = 4 \sigma$
$C = \frac{(v-u)^2(3u+v)}{4u^3v} - 2$
then $y^2 = x^3 + Cx^2 + x$ (mod p)
the group order of this curve will always be a multiple of 12?
I tried to implement it, but it is always a multiple of 4 only, not 12.
Although it is often more likely to be smooth.

Raman · 2009-03-23, 18:48

It is given that two points in an Elliptic curve over finite field can be added by using the following formula: Affine coordinate system, which makes it an Abelian group

$(x_1,y_1) + (x_2,y_2) = (x_3,y_3)$
where
$x_3 = m^2 - C - x_1 - x_2$
$-y_3 = m(x_3-x_1)+y_1$

where the slope m =
$\frac{y_2-y_1}{x_2-x_1}\ if\ x_2 \ne x_1$
$\frac{3x_1^2+2Cx_1+A}{2y_1}\ if\ x_2 = x_1$

I have implemented that in Affine.java
Take any random elliptic curve
$y^2 = x^3 - x + 2\ (mod\ 97)$

Code:

(0,83) (0,14)
(1,83) (1,14)
(2,69) (2,28)
(4,81) (4,16)
(5,92) (5,5)
(6,55) (6,42)
(7,85) (7,12)
(9,72) (9,25)
(10,33) (10,64)
(11,35) (11,62)
(14,93) (14,4)
(15,89) (15,8)
(16,69) (16,28)
(17,57) (17,40)
(18,44) (18,53)
(21,67) (21,30)
(27,89) (27,8)
(28,95) (28,2)
(30,54) (30,43)
(32,7) (32,90)
(33,93) (33,4)
(35,68) (35,29)
(36,81) (36,16)
(37,88) (37,9)
(38,82) (38,15)
(41,77) (41,20)
(44,49) (44,48)
(45,22) (45,75)
(46,1) (46,96)
(47,52) (47,45)
(50,93) (50,4)
(51,87) (51,10)
(55,89) (55,8)
(56,34) (56,63)
(57,81) (57,16)
(58,38) (58,59)
(59,19) (59,78)
(62,91) (62,6)
(64,52) (64,45)
(67,17) (67,80)
(68,38) (68,59)
(69,0)
(71,94) (71,3)
(73,49) (73,48)
(77,49) (77,48)
(78,7) (78,90)
(79,69) (79,28)
(80,76) (80,21)
(81,44) (81,53)
(83,52) (83,45)
(84,7) (84,90)
(85,41) (85,56)
(87,51) (87,46)
(90,65) (90,32)
(94,47) (94,50)
(95,44) (95,53)
(96,83) (96,14)
Group Order is 114

Taking any random point on P it, (1,14)
I want to calculate [3]P
(1,14) + (1,14) = (47,45)
(1,14) + (47,45) = (1,14)
I am getting back P, so [3]P = P? [2]P = O.
Well, it happens for every point in my implementation:
(0,14) + (0,14) = (85,56)
(0,14) + (85,56) = (0,14)
Where am I going wrong?

Well, even I don't get [#E]P = O.
Let P = (1,14)
[2]P = (47,45)
[4]P = (57,16)
[8]P = (15,89)
[7]P = [8]P - P = (15,89) + (1,83) = (2,28)
[14]P = (21,30)
[28]P = (67,80)
[56]P = (36,16)
[57]P = [56]P + P = (36,16) + (1,14) = (6,42)
[114]P = (81,44)

Help me up, right up that way.

Raman · 2009-03-23, 19:56

Oops, sorry that I missed that minus sign in my implementation for
$-y_3 = m(x_3-x_1)+y_1$

Now, that it all works fine.
$y^2 = x^3-x+2\ (mod\ 97)$
P = (1,14)
[2]P = (47,52)
[3]P = (55,89)
[4]P = [2]P + [2]P = [3]P + P = (57,16)
[8]P = (15,8)
[7]P = [8]P - P = (15,8) + (1,83) = (32,90)
[14]P = (44,48)
[28]P = (81,53)
[56]P = (33,93)
[57]P = (33,93) + (1,14) = (69,0)
[114]P = (69,0) + (69,0) = O.

Just answer the following questions:
What coordinate system is best to use for Elliptic Curve Factoring Algorithm? Affine/Projective/Modified Projective/Montgomery?

In my opinion, it should certainly not be affine, because there is no Z-coordinate. Point at infinity is best determined by using the Z coordinate, because it vanishes. For P = O (mod p) and not P = O (mod N), we could determine p = GCD(Z,N).

Addition in projective coordinates are somewhat harder to do so:
$(X_1,Y_1,Z_1) + (X_2,Y_2,Z_2) = (X_3,Y_3,Z_3)$

$\alpha = X_2Z_1 - X_1Z_2$
$\beta = X_2Z_1 + X_1Z_2$
$\gamma = Y_2Z_1 - Y_1Z_2$
$\delta = Y_2Z_1 + Y_1Z_2$
$\zeta = Z_1Z_2$

$X_3 = \alpha (\gamma^2 \zeta - \alpha^2 \beta)$
$Y_3 = \frac{1}{2} (\gamma (3\alpha^2 \beta - \gamma^2 \zeta) - \alpha^3 \delta)$
$Z_3 = \alpha^3 \zeta$

If Montgomery coordinates are better for Elliptic Curve factoring algorithm, than the Projective coordinates because of the fact that Y doesn't matter at all for the point at the infinity.

Addition in Montgomery coordinates is much more harder than that in projective coordinates?
Because of the fact that $X_3$ makes use of $\gamma$ , that in turn, makes use of $Y_1$ & $Y_2$ .

$y^2 = x^3 - x + 2\ (mod\ 97)$
(1,14,1) + (4,16,1) = (71,19,27)
(1,14,1) + (0,14,1) = (1,14,96)
(1,14,1) + (1,14,1) = (0,0,0)

$y^2 = x^3 - x + 1\ (mod\ 97)$
(3,5,1) + (17,12,1) = (29,12,28)

Code:

(0,1) (0,96)
(1,1) (1,96)
(3,92) (3,5)
(4,35) (4,62)
(5,11) (5,86)
(17,85) (17,12)
(20,67) (20,30)
(22,65) (22,32)
(24,67) (24,30)
(25,88) (25,9)
(26,73) (26,24)
(28,87) (28,10)
(31,51) (31,46)
(32,57) (32,40)
(35,89) (35,8)
(36,35) (36,62)
(41,37) (41,60)
(42,91) (42,6)
(43,33) (43,64)
(44,13) (44,84)
(45,17) (45,80)
(46,0)
(48,81) (48,16)
(51,83) (51,14)
(52,95) (52,2)
(53,67) (53,30)
(56,66) (56,31)
(57,35) (57,62)
(58,52) (58,45)
(62,61) (62,36)
(63,93) (63,4)
(67,26) (67,71)
(68,52) (68,45)
(69,22) (69,75)
(70,91) (70,6)
(71,69) (71,28)
(72,55) (72,42)
(73,13) (73,84)
(74,51) (74,46)
(76,49) (76,48)
(77,13) (77,84)
(78,57) (78,40)
(82,91) (82,6)
(84,57) (84,40)
(85,82) (85,15)
(89,51) (89,46)
(90,76) (90,21)
(92,47) (92,50)
(96,1) (96,96)
Group Order is 98

Raman · 2009-03-24, 19:56

Quote:

Happy Equinox! (Spring in Northern Hemisphere, Fall/Autumn in Southern Hemisphere)

In the Montgomery parameterization of the Elliptic Curve
$gy^2 = x^3 + Cx^2 + Ax + B$
which ignores y coordinates, and makes group order always a multiple of 4,
if $P_1 = (x_1, y_1)$ and $P_2 = (x_2, y_2)$
then it is given that $x_\pm$ are the x-coordinates of $P_1 \pm P_2$
If $x_1 \ne x_2$ , then
$x_+x_- = \frac{(x_1x_2-A)^2 - 4B(x_1+x_2+C)}{(x_1-x_2)^2}$
and if $x_1 = x_2$ , then
$x_+ = \frac{(x_1^2-A)^2 - 4B(2x_1+C)}{4(x_1^3+Cx_1^2+Ax_1+B)}$

1) Now, tell me that
what are $x_+x_-$ and $x_+$
Is the left one sum of two points or product of P₁+P₂ and P₁-P₂?
Is the right one double of a point or just sum of two points.
It is not clear according to me, in the any case.

2) And how to avoid inversion with Montgomery coordinates? Inversion is like GCD, and if taken (mod p) every time, consumes a lot of time. To avoid inversion, should we keep the Numerator for X and denominator should be multiplied with the Z coordinate?

$X_+ = Z_-((X_1X_2-AZ_1Z_2)^2 - 4B(X_1Z_2 + X_2Z_1 + CZ_1Z_2)Z_1Z_2)$
$Z_+ = X_-(X_1Z_2-X_2Z_1)^2$

Now that, what are $X_+$ , $X_-$ , $Z_+$ , $Z_-$ ? Please tell, say clearly.

Addition and subtraction of points P₁ and P₂ and then their resulting X and Z coordinates?

Feeling like as if I were Giddy.

wblipp · 2009-03-24, 21:29

I don't know much about this, but lately there has been a lot of talk about Edwards Curves, and they aren't on your list at all. Have you dismissed them or just missed them?

Raman · 2009-04-04, 16:18

Finally, I tried to implement the Elliptic Curve Factoring Algorithm (although only stage 1 works fine, I have to check for stage 2 though).

Montgomery coordinates are used, that is (X:Z), irrespective of the value of Y.
The Elliptic Curve has the form
$y^2 = x^3 + Cx^2 + x\ (mod\ N)$
For a random sigma value
$\sigma \ne -1, 0, 1, 5$
we take
$u = \sigma^2 - 5$
$v = 4 \sigma$
$C = \frac{(v-u)^3(3u+v)}{4u^3v} - 2$
Then the group order is always a multiple of 12.
We take the starting point to be $(u^3:v^3)$ mod N.

If $X_{\pm}$ and $Z_{\pm}$ are the X and Z coordinates of $P1 \pm P2$ , then we define the addition operation as follows: Function addh, 6 arguments.
$addh(X_1, Z_1, X_2, Z_2, X_-, Z_-)$

$X_+ = Z_- ((X_1X_2 - AZ_1Z_2)^2 - 4B(X_1Z_2 + X_2Z_1 + CZ_1Z_2) Z_1Z_2)$
$Z_+ = X_- (X_1Z_2 - X_2Z_1)^2$

Then, for doubling a point P1, let $X_+$ and $Z_+$ be the X and Z coordinates of [2]P1. Then, we define the double operation as follows. Function doubleh, 2 arguments.
$doubleh(X_1, Z_1)$

$X_+ = (X_1^2 - AZ_1^2)^2 - 4B(2X_1 + CZ_1)Z_1^3$
$Z_+ = 4Z_1 (X_1^3 + CX_1^2Z_1 + AX_1Z_1^2 + BZ_1^3)$

Then we define the multiplication operation for a point P (X:Z) by k, by using the following algorithm:

Code:

If k = 0, then return O
If k = 1, return (X:Z)
If k = 2, return doubleh(X:Z)

If k > 2 then we define as follows
{
(U:V) = (X:Z)
(T:W) = doubleh(X:Z)

Let k be represented as a B-bit integer in binary notation.


for j = B-2 down to 0
{
if(k_j = 1) then
{
(U:V) = addh(T:W, U:V, X:Z)
(T:W) = doubleh(T:W)
}
else if(k_j = 0) then
{
(T:W) = addh(U:V, T:W, X:Z)
(U:V) = doubleh(U:V)
}
}
Return (U:V)
}

For example, to calculate [7]P, we have P, and we can calculate [2]P by doubling it. [3]P = addh([2]P, P, P), 4P = doubleh([2]P). Thus, we have that [7]P = addh([7]P, [4]P, [3]P)

For stage 1, we need to calculate [R]P, where R is the LCM of all numbers below B1, i.e. the product of (the largest powers of primes below B1) below B1.

Raman · 2009-04-04, 17:04

Can someone check the following algorithm for Stage 2? I am unable to detect the error. If stage 2 is implemented, lots of bigger factors (ranging from 25 to 30 digits) will be returned much easily.

My program, that I have tested so far, has never returned any factor within stage 2, that are returned by using the same parameterization of curves in GMP-ECM. Let P be the original starting point, (u³:v³), and Q be the point obtained by multiplying P by R, the LCM of all numbers below B1. Then, we have the following algorithm for the Stage 2 process? For some reasons, it does not work at all. So, please check it up, thus. Let me denote X(P1), Z(P1) to be the X and Z coordinates of P1 respectively.

S₁ = doubleh(Q)
S₂ = doubleh(S1)

For d from 3 to D
{
S_d = addh(S_d-1,S₁,S_d-2)
$\beta$ _d = X(S_d) * Z(S_d) mod N
}

g = 1
B = B1 - 1 if B1 is even; B should always be odd
T = [B-2D]Q
R = [b]Q

For r = B to B2; r = r + 2D
{
$\alpha$ = X(R) * Z(R) mod N
For each prime q between r+2 and r+2D
{
$\delta$ = (q-r)/2
g = g((X(R) - X(S_{[tex]\delta[/tex]}))(Z(R) + Z(S_{[tex]\delta[/tex]})) - $\alpha$ + $\beta$ _d) mod N
}
(R, T) = (addh(R,S_D,T), R)
}
g = gcd(g, n)

If 1 < g < n, then return g
Else, change the sigma value and then try some other curve, thus

R.D. Silverman · 2009-04-05, 00:18

Quote:

Originally Posted by Raman

Can someone check the following algorithm for Stage 2? I am unable to detect the error. If stage 2 is implemented, lots of bigger factors (ranging from 25 to 30 digits) will be returned much easily.

My program, that I have tested so far, has never returned any factor within stage 2, that are returned by using the same parameterization of curves in GMP-ECM. Let P be the original starting point, (u³:v³), and Q be the point obtained by multiplying P by R, the LCM of all numbers below B1. Then, we have the following algorithm for the Stage 2 process? For some reasons, it does not work at all. So, please check it up, thus. Let me denote X(P1), Z(P1) to be the X and Z coordinates of P1 respectively.

S₁ = doubleh(Q)
S₂ = doubleh(S1)

For d from 3 to D
{
S_d = addh(S_d-1,S₁,S_d-2)
$\beta$ _d = X(S_d) * Z(S_d) mod N
}

g = 1
B = B1 - 1 if B1 is even; B should always be odd
T = [B-2D]Q
R = [b]Q

For r = B to B2; r = r + 2D
{
$\alpha$ = X(R) * Z(R) mod N
For each prime q between r+2 and r+2D
{
$\delta$ = (q-r)/2
g = g((X(R) - X(S_{[tex]\delta[/tex]}))(Z(R) + Z(S_{[tex]\delta[/tex]})) - $\alpha$ + $\beta$ _d) mod N
}
(R, T) = (addh(R,S_D,T), R)
}
g = gcd(g, n)

If 1 < g < n, then return g
Else, change the sigma value and then try some other curve, thus

Read Peter Montgomery's 1987 Math. Comp. paper
Read his doctoral dissertation.

Raman · 2009-04-13, 19:20

Glad that the stage 2 for ECM now works fine. Luckily, it automatically got fixed up. It successfully gives all the factors that GMP-ECM gives in stage 2 for any given sigma value.

But, the only thing is that the program is extremely slow when compared to GMP-ECM, both within stage 1 and stage 2. Perhaps, implementation of FFT algorithm might speed up the program to some extent.

Does anyone have figures on how much the program will speed up when FFT algorithms are implemented to the ECM multiplication? What are the materials from which I could learn so, about these FFT based multiplication and squaring algorithms? Please give me books and suitable references!

I think that I can implement the FFT algorithm within my Java program itself. I am unable to compile any program that is being written under the usage of the GMP library.

2009-03-23, 18:48	#2
Raman Noodles "Mr. Tuch" Dec 2007 Chennai, India 3×419 Posts	Need help with Elliptic Curve Addition It is given that two points in an Elliptic curve over finite field can be added by using the following formula: Affine coordinate system, which makes it an Abelian group $(x_1,y_1) + (x_2,y_2) = (x_3,y_3)$ where $x_3 = m^2 - C - x_1 - x_2$ $-y_3 = m(x_3-x_1)+y_1$ where the slope m = $\frac{y_2-y_1}{x_2-x_1}\ if\ x_2 \ne x_1$ $\frac{3x_1^2+2Cx_1+A}{2y_1}\ if\ x_2 = x_1$ I have implemented that in Affine.java Take any random elliptic curve $y^2 = x^3 - x + 2\ (mod\ 97)$ Code: (0,83) (0,14) (1,83) (1,14) (2,69) (2,28) (4,81) (4,16) (5,92) (5,5) (6,55) (6,42) (7,85) (7,12) (9,72) (9,25) (10,33) (10,64) (11,35) (11,62) (14,93) (14,4) (15,89) (15,8) (16,69) (16,28) (17,57) (17,40) (18,44) (18,53) (21,67) (21,30) (27,89) (27,8) (28,95) (28,2) (30,54) (30,43) (32,7) (32,90) (33,93) (33,4) (35,68) (35,29) (36,81) (36,16) (37,88) (37,9) (38,82) (38,15) (41,77) (41,20) (44,49) (44,48) (45,22) (45,75) (46,1) (46,96) (47,52) (47,45) (50,93) (50,4) (51,87) (51,10) (55,89) (55,8) (56,34) (56,63) (57,81) (57,16) (58,38) (58,59) (59,19) (59,78) (62,91) (62,6) (64,52) (64,45) (67,17) (67,80) (68,38) (68,59) (69,0) (71,94) (71,3) (73,49) (73,48) (77,49) (77,48) (78,7) (78,90) (79,69) (79,28) (80,76) (80,21) (81,44) (81,53) (83,52) (83,45) (84,7) (84,90) (85,41) (85,56) (87,51) (87,46) (90,65) (90,32) (94,47) (94,50) (95,44) (95,53) (96,83) (96,14) Group Order is 114 Taking any random point on P it, (1,14) I want to calculate [3]P (1,14) + (1,14) = (47,45) (1,14) + (47,45) = (1,14) I am getting back P, so [3]P = P? [2]P = O. Well, it happens for every point in my implementation: (0,14) + (0,14) = (85,56) (0,14) + (85,56) = (0,14) Where am I going wrong? Well, even I don't get [#E]P = O. Let P = (1,14) [2]P = (47,45) [4]P = (57,16) [8]P = (15,89) [7]P = [8]P - P = (15,89) + (1,83) = (2,28) [14]P = (21,30) [28]P = (67,80) [56]P = (36,16) [57]P = [56]P + P = (36,16) + (1,14) = (6,42) [114]P = (81,44) Help me up, right up that way.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Elliptic curve arithmetic	burrobert	GMP-ECM	6	2012-11-08 13:05
Elliptic-curve L-function question	fivemack	Math	0	2010-08-22 14:52
Elliptic curve method	Dirac	Factoring	11	2007-11-01 14:01
Linear recurrence on elliptic curve	Unregistered	Information & Answers	2	2007-01-18 17:13
Elliptic factoring with points NOT on the curve	bongomongo	Factoring	5	2006-12-21 18:19

2009-03-24, 21:29	#5
wblipp "William" May 2003 Near Grandkid 5³·19 Posts	I don't know much about this, but lately there has been a lot of talk about Edwards Curves, and they aren't on your list at all. Have you dismissed them or just missed them?