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);

<-->