20090323, 18:22  #1 
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
10011101001_{2} 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, pGCD(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. 
20090323, 18:48  #2 
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
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 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. 
20090323, 19:56  #3 
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
4E9_{16} Posts 
Oops, sorry that I missed that minus sign in my implementation for
Now, that it all works fine. 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 Zcoordinate. 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 Last fiddled with by Raman on 20090323 at 20:00 
20090324, 19:56  #4  
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
4E9_{16} Posts 
Please give quick reply, not links or references
Quote:
which ignores y coordinates, and makes group order always a multiple of 4, if and then it is given that are the xcoordinates 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 P_{1}+P_{2} and P_{1}P_{2}? 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 P_{1} and P_{2} and then their resulting X and Z coordinates? Feeling like as if I were Giddy. Last fiddled with by Raman on 20090324 at 19:59 

20090324, 21:29  #5 
"William"
May 2003
New Haven
3×7×113 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?

20090404, 16:18  #6 
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 [2]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 Bbit integer in binary notation. for j = B2 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 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. Last fiddled with by Raman on 20090404 at 16:20 
20090404, 17:04  #7 
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 GMPECM. Let P be the original starting point, (u^{3}:v^{3}), 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_{1} = doubleh(Q) S_{2} = doubleh(S1) For d from 3 to D { S_{d} = addh(S_{d1},S_{1},S_{d2}) _{d} = X(S_{d}) * Z(S_{d}) mod N } g = 1 B = B1  1 if B1 is even; B should always be odd T = [B2D]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 { = (qr)/2 g = g((X(R)  X(S_{[tex]\delta[/tex]}))(Z(R) + Z(S_{[tex]\delta[/tex]}))  + _{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 Last fiddled with by Raman on 20090404 at 17:53 
20090405, 00:18  #8  
"Bob Silverman"
Nov 2003
North of Boston
2·3·29·43 Posts 
Quote:
Read his doctoral dissertation. 

20090413, 19:20  #9 
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 GMPECM gives in stage 2 for any given sigma value.
But, the only thing is that the program is extremely slow when compared to GMPECM, 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. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Elliptic curve arithmetic  burrobert  GMPECM  6  20121108 13:05 
Ellipticcurve Lfunction question  fivemack  Math  0  20100822 14:52 
Elliptic curve method  Dirac  Factoring  11  20071101 14:01 
Linear recurrence on elliptic curve  Unregistered  Information & Answers  2  20070118 17:13 
Elliptic factoring with points *NOT* on the curve  bongomongo  Factoring  5  20061221 18:19 