20061215, 10:07  #1 
2×23×181 Posts 
Elliptic factoring with points *NOT* on the curve
The elliptic curve factoring algorithm seems to work with points
*NOT* on the curve. Pick a random POINT=[x,y] that is not on the curve in Fp and perform point addition and multiplication as if POINT were on the curve. The point at infinity is hit, giving a cyclic group structure with order different from the points on the curve. As in this example: <> Code:
p=19; a=14;b=10; e1=ellinit([0,0,0,a,b]); x0=random(p);y0=random(p);while(ellisoncurve(e1,Mod(1,p)*[x0,y0]),x0=random(p);y0=random(p)); po1=Mod(1,p)*[x0,y0];print(" point=",po1," on curve=",ellisoncurve(e1,po1)," ellap=",ellap(e1,p));for(i=1,p+2,po2=centerlift(ellpow(e1,po1,i));print(i," ",po2)); <> point=[Mod(5, 19), Mod(2, 19)] on curve=0 ellap=3 1 [5, 2] 2 [3, 5] 3 [2, 4] 4 [4, 9] 5 [2, 1] 6 [3, 7] 7 [3, 7] 8 [2, 1] 9 [4, 9] 10 [2, 4] 11 [3, 5] 12 [5, 2] 13 [0] 14 [5, 2] 15 [3, 5] 16 [2, 4] 17 [4, 9] 18 [2, 1] 19 [3, 7] 20 [3, 7] 21 [2, 1] generated: Code:
gp > po=ellpow(e1,[x,y],3);x0=random(p);tt=polrootsmod(subst(numerator(po[2]),x,x0),p);while(length(tt)<2,x0=random(p);tt=polrootsmod(subst(numerator(po[2]),x,x0),p));po2=[Mod(1,p)*x0,tt[2] ] %244 = [Mod(8, 19), Mod(1, 19)] gp > ellpow(e1,po2,2*3) %245 = [0] ellisoncurve(e1,po2) %246 = 0 gp > 1. Looks like all [x,y] not on the curve give group structure for primes with good reduction. 2. There are points not on the curve with arbitrary even order. 3. Factoring not on the curve gives similar results with factoring on the curve (at least to 10^20). If this is right, what is known about the order of random [x,y] on a random curve? (The classic algorithm has some restrictions) Attached is modification to the elliptic curve factoring algorithm. <> Code:
\\ This program is distributed under the terms of the GPL v2. \\ The full text of the GPL is available at: \\ http://www.gnu.org/licenses/gpl.txt \\ Modification to the elliptic curve factoring algorithm working with points \\ *NOT* on the curve \\ Usage: \\ gp \\ \r FILENAME { facreal3(p,cu)= local(e1,x0,y0,a,b,tt,i,po1,po2,o,c1,cp,l1,po); a=random(p); b=random(p); po=x^3+a*x+b; while(gcd(poldisc(po),p)!=1,a=random(p); b=random(p); po=x^3+a*x+b;); e1=ellinit([0,0,0,a,b]); for(c1=1,cu, print(c1); x0=random(p); y0=random(p); while(ellisoncurve(e1,Mod(1,p)*[x0,y0]), x0=random(p); y0=random(p); ); po1=Mod(1,p)*[x0,y0]; po2=po1; print(" on curve=",ellisoncurve(e1,po1)); cp=0; while(cp<B1, cp=nextprime(cp+1); p1=cp; l1=round(log(B1)/log(p1)) ; for(j=1,l1, po2=(ellpow(e1,po2,p1)); if(centerlift(po2)==[0],o=i;print(" zero=",po2," cu=",c1)); ); ); ); return; } B1=11000; p=1000000000000241*99999999999999990167; facreal3(p,200); 
20061215, 12:17  #2 
"Nancy"
Aug 2002
Alexandria
2467_{10} Posts 
This is pushing my understanding of elliptic curves... but would a point not on E(p) be on the twist curve? Then it would be clear why you're getting group structure again.
Alex 
20061215, 13:38  #3  
6507_{8} Posts 
Quote:
In the example with: p=19; a=14;b=10; There is a point of order 13. The twisted curve has order 23 and the original curve has order 17. 

20061215, 14:00  #4 
23D1_{16} Posts 

20061221, 17:50  #5 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
I asked Pierrick Gaudry, who has worked on elliptic curve arithmetic before, about this and he replied simply that he didn't know about this idea, either. Someone may well have investigated this before, but if so, it's not very commonly known, apparantly. Sounds like an interesting topic to delve into some more.
Alex 
20061221, 18:19  #6  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}×1,877 Posts 
Quote:
For a curve in the form y^2 = x^3 + ax + b, the parameter b does not occur in the arithmetic when adding two points. So given y^2 = x^3 + Ax + B for given A,B, a point (x1, y1) not on this curve is instead on the curve y^2 = x^3 + Ax + B', where B' != B. You are still adding points, but it is on a DIFFERENT curve from the one you expect. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Elliptic curve arithmetic  burrobert  GMPECM  6  20121108 13:05 
Elliptic Curve Arithmetic  Raman  Math  8  20090413 19:20 
Elliptic curve method  Dirac  Factoring  11  20071101 14:01 
Linear recurrence on elliptic curve  Unregistered  Information & Answers  2  20070118 17:13 
Elliptic Curve Method factoring  Fermat numbers  philmoore  Math  131  20061218 06:27 