mersenneforum.org > Math Elliptic Curve Arithmetic
 Register FAQ Search Today's Posts Mark Forums Read

2009-03-23, 18:22   #1
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

3·419 Posts
Elliptic Curve Arithmetic

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.
Attached Files
 Elliptic Curves.zip (7.0 KB, 198 views)

 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.
2009-03-23, 19:56   #3
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts

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.

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
Attached Files
 Affine.txt (6.9 KB, 274 views)

Last fiddled with by Raman on 2009-03-23 at 20:00

2009-03-24, 19:56   #4
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

125710 Posts

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 P1+P2 and P1-P2?
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 P1 and P2 and then their resulting X and Z coordinates? Feeling like as if I were Giddy.

Last fiddled with by Raman on 2009-03-24 at 19:59

 2009-03-24, 21:29 #5 wblipp     "William" May 2003 New Haven 45058 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?
2009-04-04, 16:18   #6
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

4E916 Posts

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.
$k_{B-1}k_{B-2}k_{B-3}...k_1k_0$

for j = B-2 down to 0
{
if(kj = 1) then
{
(T:W) = doubleh(T:W)
}
else if(kj = 0) then
{
(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.
Attached Files
 ECM.txt (8.4 KB, 224 views)

Last fiddled with by Raman on 2009-04-04 at 16:20

2009-04-04, 17:04   #7
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts
Need so help for the Stage 2 process

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, (u3:v3), 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.

S1 = doubleh(Q)
S2 = doubleh(S1)

For d from 3 to D
{
$\beta$d = X(Sd) * Z(Sd) 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$$\delta$$))(Z(R) + Z(S$$\delta$$)) - $\alpha$ + $\beta$d) mod N
}
}
g = gcd(g, n)

If 1 < g < n, then return g
Else, change the sigma value and then try some other curve, thus
Attached Files
 Don't see this.txt (270 Bytes, 198 views)

Last fiddled with by Raman on 2009-04-04 at 17:53

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

"Bob Silverman"
Nov 2003
North of Boston

2×3×29×43 Posts

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, (u3:v3), 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. S1 = doubleh(Q) S2 = doubleh(S1) For d from 3 to D { Sd = addh(Sd-1,S1,Sd-2) $\beta$d = X(Sd) * Z(Sd) 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$$\delta$$))(Z(R) + Z(S$$\delta$$)) - $\alpha$ + $\beta$d) mod N } (R, T) = (addh(R,SD,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

2009-04-13, 19:20   #9
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts

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.
Attached Files
 ecm.txt (8.4 KB, 214 views)

 Similar Threads Thread Thread Starter Forum Replies Last Post burrobert GMP-ECM 6 2012-11-08 13:05 fivemack Math 0 2010-08-22 14:52 Dirac Factoring 11 2007-11-01 14:01 Unregistered Information & Answers 2 2007-01-18 17:13 bongomongo Factoring 5 2006-12-21 18:19

All times are UTC. The time now is 05:36.

Mon Oct 3 05:36:04 UTC 2022 up 46 days, 3:04, 1 user, load averages: 1.39, 1.05, 1.02