 mersenneforum.org > Math Elliptic Curve Arithmetic
 User Name Remember Me? Password
 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
and
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

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:

then (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, 98 views)   2009-03-23, 18:48 #2 Raman Noodles   "Mr. Tuch" Dec 2007 Chennai, India 125710 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 where where the slope m = I have implemented that in Affine.java Take any random elliptic curve 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 P (1,14) + (1,14) = (47,45) (1,14) + (47,45) = (1,14) I am getting back P, so P = P? 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) P = (47,45) P = (57,16) P = (15,89) P = P - P = (15,89) + (1,83) = (2,28) P = (21,30) P = (67,80) P = (36,16) P = P + P = (36,16) + (1,14) = (6,42) 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

Now, that it all works fine.

P = (1,14)
P = (47,52)
P = (55,89)
P = P + P = P + P = (57,16)
P = (15,8)
P = P - P = (15,8) + (1,83) = (32,90)
P = (44,48)
P = (81,53)
P = (33,93)
P = (33,93) + (1,14) = (69,0)
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:

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 makes use of , that in turn, makes use of & .

(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) (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, 157 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

3·419 Posts 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

which ignores y coordinates, and makes group order always a multiple of 4,
if and
then it is given that are the x-coordinates of
If , then

and if , then

1) Now, tell me that
what are and
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?

Now that, what are , , , ? 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 1001001110012 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

3·419 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

For a random sigma value

we take

Then the group order is always a multiple of 12.
We take the starting point to be mod N.

If and are the X and Z coordinates of , then we define the addition operation as follows: Function addh, 6 arguments.

Then, for doubling a point P1, let and be the X and Z coordinates of P1. Then, we define the double operation as follows. Function doubleh, 2 arguments.

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(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 P, we have P, and we can calculate P by doubling it. P = addh(P, P, P), 4P = doubleh(P). Thus, we have that P = addh(P, P, 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, 121 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

23518 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
{
Sd = addh(Sd-1,S1,Sd-2)
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
{
= X(R) * Z(R) mod N
For each prime q between r+2 and r+2D
{
= (q-r)/2
g = g((X(R) - X(S$$\delta$$))(Z(R) + Z(S$$\delta$$)) - + 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
Attached Files Don't see this.txt (270 Bytes, 106 views)

Last fiddled with by Raman on 2009-04-04 at 17:53   2009-04-05, 00:18   #8
R.D. Silverman

Nov 2003

22×5×373 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) 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 { = X(R) * Z(R) mod N For each prime q between r+2 and r+2D { = (q-r)/2 g = g((X(R) - X(S$$\delta$$))(Z(R) + Z(S$$\delta$$)) - + 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
Read his doctoral dissertation.   2009-04-13, 19:20   #9
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

23518 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, 121 views)  Thread Tools Show Printable Version Email this Page 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 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.