mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-03-23, 18:22   #1
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts
Default 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
File Type: zip Elliptic Curves.zip (7.0 KB, 98 views)
Raman is offline   Reply With Quote
Old 2009-03-23, 18:48   #2
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

125710 Posts
Default 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.
Raman is offline   Reply With Quote
Old 2009-03-23, 19:56   #3
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts
Default

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
Attached Files
File Type: txt Affine.txt (6.9 KB, 157 views)

Last fiddled with by Raman on 2009-03-23 at 20:00
Raman is offline   Reply With Quote
Old 2009-03-24, 19:56   #4
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3·419 Posts
Default Please give quick reply, not links or references

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
Raman is offline   Reply With Quote
Old 2009-03-24, 21:29   #5
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

1001001110012 Posts
Default

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?
wblipp is offline   Reply With Quote
Old 2009-04-04, 16:18   #6
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3·419 Posts
Default

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
{
(U:V) = addh(T:W, U:V, X:Z)
(T:W) = doubleh(T:W)
}
else if(kj = 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.
Attached Files
File Type: txt ECM.txt (8.4 KB, 121 views)

Last fiddled with by Raman on 2009-04-04 at 16:20
Raman is offline   Reply With Quote
Old 2009-04-04, 17:04   #7
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

23518 Posts
Default 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
{
Sd = addh(Sd-1,S1,Sd-2)
\betad = 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[tex]\delta[/tex]))(Z(R) + Z(S[tex]\delta[/tex])) - \alpha + \betad) 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
Attached Files
File Type: txt Don't see this.txt (270 Bytes, 106 views)

Last fiddled with by Raman on 2009-04-04 at 17:53
Raman is offline   Reply With Quote
Old 2009-04-05, 00:18   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by Raman View Post
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)
\betad = 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[tex]\delta[/tex]))(Z(R) + Z(S[tex]\delta[/tex])) - \alpha + \betad) 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
Read his doctoral dissertation.
R.D. Silverman is offline   Reply With Quote
Old 2009-04-13, 19:20   #9
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

23518 Posts
Default

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
File Type: txt ecm.txt (8.4 KB, 121 views)
Raman is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 17:51.

Tue Apr 13 17:51:26 UTC 2021 up 5 days, 12:32, 1 user, load averages: 4.49, 4.95, 4.88

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.