mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2006-12-15, 10:07   #1
bongomongo
 

22×373 Posts
Default 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]
Points not on the curve with arbitrary even order seem to be
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 >
Some tests results that may be screwed by testing with small number:

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);
<-->
  Reply With Quote
Old 2006-12-15, 12:17   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

9A016 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2006-12-15, 13:38   #3
Unregistered
 

2·3·192 Posts
Default

Quote:
Originally Posted by akruppa View Post
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
Are you sure about this?

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.
  Reply With Quote
Old 2006-12-15, 14:00   #4
Unregistered
 

696710 Posts
Default

Quote:
Originally Posted by akruppa View Post
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
If the coding is right: The pseudo point with constructed order of 6 [8,1] is not on any twist in F19
  Reply With Quote
Old 2006-12-21, 17:50   #5
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

25×7×11 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2006-12-21, 18:19   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by akruppa View Post
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
It is simple.

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.
R.D. Silverman 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 Arithmetic Raman Math 8 2009-04-13 19:20
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 Curve Method factoring - Fermat numbers philmoore Math 131 2006-12-18 06:27

All times are UTC. The time now is 06:31.

Fri Nov 27 06:31:40 UTC 2020 up 78 days, 3:42, 4 users, load averages: 1.22, 1.19, 1.16

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.