login  home  contents  what's new  discussion  bug reports help  links  subscribe  changes  refresh  edit

## Elliptic curve computations mod N in projective coordinates

On Jul 10, 2007 9:08 AM Alasdair McAndrew? wrote:

I have written some highly unoptimized code for factoring integers using Lenstra's elliptic curve method, with the "birthday paradox" phase two developed by Richard Brent. Even at this stage, it can factor the seventh Fermat number 2^2^7+1 in 352 seconds, as opposed to 1877 seconds by the in-built factoring method. If anybody is interesting in developing this code further, do let me know.

All I really want to do is to extend the methods in intfact.spad to include ecm - which the file itself recommends.

-Alasdair

reference

fricas
mod(a:Integer,b:PositiveInteger):Integer == (a>0 => a rem b::Integer; b + (a rem b))
Function declaration mod : (Integer,PositiveInteger) -> Integer has
been added to workspace.
Type: Void

a is a parameter which describes the elliptic curve, and which is the one used for addition and point doubling.

fricas
ecAdd(a:Integer,X:List Integer,Y:List Integer,N:Integer):List Integer ==
local u,v,A,x3,y3,z3
if (X=Y)::Boolean then return ecDouble(a,X,N)
else
u := Y.2*X.3-X.2*Y.3
v := Y.1*X.3-X.1*Y.3
A := u^2*X.3*Y.3-v^3-2*v^2*X.1*Y.3
x3 := (v*A) rem N
y3 := (u*(v^2*X.1*Y.3-A)-v^3*X.2*Y.3) rem N
z3 := (v^3*X.3*Y.3) rem N
return [x3,y3,z3]
Integer) -> List(Integer) has been added to workspace.
Type: Void
fricas
ecDouble(a:Integer,X:List Integer,N:Integer):List Integer ==
local w,s,B,h,x3,y3,z3
w := a*X.3^2+3*X.1^2
s := X.2*X.3
B := X.1*X.2*s
h := w^2 - 8*B
x3 := (2*h*s) rem N
y3 := (w*(4*B-h)-8*X.2^2*s^2) rem N
z3 := (8*s^3) rem N
return [x3,y3,z3]
Function declaration ecDouble : (Integer,List(Integer),Integer) ->
List(Integer) has been added to workspace.
Type: Void
fricas
ecMultiply(a:Integer,X:List Integer,n:Integer,N:Integer):List Integer ==
local lst,P
P:=X
for i in rest lst repeat
P:=ecDouble(a,P,N)
if i = 1 then P:=ecAdd(a,P,X,N)
return P
Function declaration ecMultiply : (Integer,List(Integer),Integer,
Integer) -> List(Integer) has been added to workspace.
Type: Void

Here is the main routine; you have to enter both the bounds B and r; for example:

   ecFactor(2^101-1,10000,700)


fricas
ecFactor(N:Integer,B:Integer,r:Integer):List Integer ==
local a:Integer, x:Integer,y:Integer,b,g,curve,found,Q,f,i,tmp
found:=false
i:=0
while not(found) repeat
curve:=false
while not(curve) repeat
a:=random(N)
x:=random(N)
y:=random(N)
b:=y^2-x^3-a*x
g:=gcd(4*a^3+27*b^2,N)
if g = 1 then
curve:=true
i:=i+1
if (i rem 20)=0 then output i
Q:=ecPhaseOne(a,[x,y,1],B,N)
f := gcd(Q.3,N)
if f>1 and f<N then
found:=true
else
tmp:=ecPhaseTwo(a,Q,N,r)
if tmp>1 and tmp<N then
found:=true
return [f,N/f]
Function declaration ecFactor : (Integer,Integer,Integer) -> List(
Integer) has been added to workspace.
Type: Void
fricas
ecPhaseOne(a:Integer,X:List Integer,B:PositiveInteger,N:PositiveInteger):List Integer ==
local P,i,e
P := X
for i in primes(2,B) repeat
e := wholePart(log2(B::DoubleFloat)/log2(i::DoubleFloat))::PositiveInteger
P := ecMultiply(a,P,i^e,N)
return P
Function declaration ecPhaseOne : (Integer,List(Integer),
PositiveInteger,PositiveInteger) -> List(Integer) has been added
to workspace.
Type: Void
fricas
ecPhaseTwo(a:Integer,Q:List Integer,N:PositiveInteger,r:PositiveInteger):Integer ==
local randr,Qs,tmp,i,j,k,d,result
result := 1
Qs := [Q]
for i in 2..r repeat
tmp := ecDouble(a,Qs.(i-1),N)
if randr.i = 1 then tmp := ecAdd(a,tmp,Q,N)
Qs := append(Qs,[tmp])
for i in 2..r repeat
if member?(Qs.i,[Qs.k for k in 1..i-1]) then
--j := position(Qs.i,[Qs.k for k in 1..i-1])
d := reduce(*,[reduce(*,[Qs.i.3-Qs.j.3 for j in i+1..r]) for i in _
1..r-1])
if gcd(N,d)>1 then result:=gcd(N,d)
return result
Function declaration ecPhaseTwo : (Integer,List(Integer),
PositiveInteger,PositiveInteger) -> Integer has been added to
workspace.
Type: Void

See http://www.alpertron.com.ar/ECM.HTM for values of B.

For example:

fricas
)set message time on
factor 2^101-1
 (1)
Type: Factored(Integer)
fricas
Time: 0.03 (IN) + 2.82 (EV) + 0.04 (OT) = 2.89 sec

fricas
ecFactor(2^101-1,10000,700)
fricas
Compiling function ecDouble with type (Integer,List(Integer),Integer
) -> List(Integer)
fricas
Compiling function ecAdd with type (Integer,List(Integer),List(
Integer),Integer) -> List(Integer)
fricas
Compiling function ecMultiply with type (Integer,List(Integer),
Integer,Integer) -> List(Integer)
fricas
Compiling function ecPhaseOne with type (Integer,List(Integer),
PositiveInteger,PositiveInteger) -> List(Integer)
fricas
Compiling function ecPhaseTwo with type (Integer,List(Integer),
PositiveInteger,PositiveInteger) -> Integer
fricas
Compiling function ecFactor with type (Integer,Integer,Integer) ->
List(Integer)
fricas
Compiling function G727 with type Integer -> Boolean
fricas
Compiling function G729 with type NonNegativeInteger -> Boolean
 (2)
Type: List(Integer)
fricas
Time: 0.18 (IN) + 4.78 (EV) + 0.09 (OT) = 5.05 sec

fricas
test( reduce(*,%)=2^101-1 )
 (3)
Type: Boolean
fricas
Time: 0 sec

)abbrev package EC EllipticCurve
--#pile
--#include "axiom"
--import from Integer
EllipticCurve(): with
ecDouble:(Integer,List Integer,Integer) -> List Integer
ecMultiply:(Integer,List Integer,Integer,Integer) -> List Integer
if X=Y then
ecDouble(a,X,N)
else
u := Y.2*X.3-X.2*Y.3
v := Y.1*X.3-X.1*Y.3
A := u^2*X.3*Y.3-v^3-2*v^2*X.1*Y.3
x3 := (v*A) rem N
y3 := (u*(v^2*X.1*Y.3-A)-v^3*X.2*Y.3) rem N
z3 := (v^3*X.3*Y.3) rem N
[x3,y3,z3]
ecDouble(a:Integer,X:List Integer,N:Integer):List Integer ==
w := a*X.3^2+3*X.1^2
s := X.2*X.3
B := X.1*X.2*s
h := w^2 - 8*B
x3 := (2*h*s) rem N
y3 := (w*(4*B-h)-8*X.2^2*s^2) rem N
z3 := (8*s^3) rem N
[x3,y3,z3]
ecMultiply(a:Integer,X:List Integer,n:Integer,N:Integer):List Integer ==
-- import from RadixExpansion 2, List Integer
P:=X
for i in rest lst repeat
P:=ecDouble(a,P,N)
if i = 1 then P:=ecAdd(a,P,X,N)
P
   Compiling FriCAS source code from file
using old system compiler.
EC abbreviates package EllipticCurve
------------------------------------------------------------------------
initializing NRLIB EC for EllipticCurve
compiling into NRLIB EC
compiling exported ecAdd : (Integer,List Integer,List Integer,Integer) -> List Integer
Time: 0.07 SEC.
compiling exported ecDouble : (Integer,List Integer,Integer) -> List Integer
Time: 0.08 SEC.
compiling exported ecMultiply : (Integer,List Integer,Integer,Integer) -> List Integer
Time: 0.01 SEC.
(time taken in buildFunctor:  0)
;;;     ***       |EllipticCurve| REDEFINED
;;;     ***       |EllipticCurve| REDEFINED
Time: 0 SEC.
Cumulative Statistics for Constructor EllipticCurve
Time: 0.16 seconds
finalizing NRLIB EC
Processing EllipticCurve for Browser database:
--->-->EllipticCurve(constructor): Not documented!!!!
--->-->EllipticCurve((ecAdd ((List (Integer)) (Integer) (List (Integer)) (List (Integer)) (Integer)))): Not documented!!!!
--->-->EllipticCurve((ecDouble ((List (Integer)) (Integer) (List (Integer)) (Integer)))): Not documented!!!!
--->-->EllipticCurve((ecMultiply ((List (Integer)) (Integer) (List (Integer)) (Integer) (Integer)))): Not documented!!!!
--->-->EllipticCurve(): Missing Description
; compiling file "/var/aw/var/LatexWiki/EC.NRLIB/EC.lsp" (written 31 JUL 2013 05:37:59 PM):
; /var/aw/var/LatexWiki/EC.NRLIB/EC.fasl written
; compilation finished in 0:00:00.047
------------------------------------------------------------------------
EllipticCurve is now explicitly exposed in frame initial
EllipticCurve will be automatically loaded when needed from
/var/aw/var/LatexWiki/EC.NRLIB/EC

fricas
factor(N:Integer,B:Integer,r:Integer):List Integer ==
local a:Integer, x:Integer,y:Integer,b,g,curve,found,Q,f,i,tmp
found:=false
i:=0
while not(found) repeat
curve:=false
while not(curve) repeat
a:=random(N)
x:=random(N)
y:=random(N)
b:=y^2-x^3-a*x
g:=gcd(4*a^3+27*b^2,N)
if g = 1 then
curve:=true
i:=i+1
if (i rem 20)=0 then output i
Q:=ecPhase1(a,[x,y,1],B,N)
f := gcd(Q.3,N)
if f>1 and f<N then
found:=true
else
tmp:=ecPhase2(a,Q,N,r)
if tmp>1 and tmp<N then
found:=true
return [f,N/f]
Function declaration factor : (Integer,Integer,Integer) -> List(
Integer) has been added to workspace.
Type: Void
fricas
Time: 0 sec
ecPhase1(a:Integer,X:List Integer,B:PositiveInteger,N:PositiveInteger):List Integer ==
local P,i,e
P := X
for i in primes(2,B) repeat
e := wholePart(log2(B::DoubleFloat)/log2(i::DoubleFloat))::PositiveInteger
P := ecMultiply(a,P,i^e,N)$EC return P Function declaration ecPhase1 : (Integer,List(Integer), PositiveInteger,PositiveInteger) -> List(Integer) has been added to workspace. Type: Void fricas Time: 0 sec ecPhase2(a:Integer,Q:List Integer,N:PositiveInteger,r:PositiveInteger):Integer == local randr,Qs,tmp,i,j,k,d,result result := 1 randr := rest wholeRagits(2^r+random(2^r)::RadixExpansion 2) Qs := [Q] for i in 2..r repeat tmp := ecDouble(a,Qs.(i-1),N)$EC
if randr.i = 1 then tmp := ecAdd(a,tmp,Q,N)\$EC
Qs := append(Qs,[tmp])
for i in 2..r repeat
if member?(Qs.i,[Qs.k for k in 1..i-1]) then
--j := position(Qs.i,[Qs.k for k in 1..i-1])
d := reduce(*,[reduce(*,[Qs.i.3-Qs.j.3 for j in i+1..r]) for i in _
1..r-1])
if gcd(N,d)>1 then result:=gcd(N,d)
return result
Function declaration ecPhase2 : (Integer,List(Integer),
PositiveInteger,PositiveInteger) -> Integer has been added to
workspace.
Type: Void
fricas
Time: 0.01 (IN) = 0.01 sec

See http://www.alpertron.com.ar/ECM.HTM for values of B.

For example:

fricas
)set message time on
factor 2^101-1
 (4)
Type: Factored(Integer)
fricas
Time: 1.50 (EV) = 1.50 sec

fricas
factor(2^101-1,10000,700)
fricas
Compiling function ecPhase1 with type (Integer,List(Integer),
PositiveInteger,PositiveInteger) -> List(Integer)
fricas
Compiling function ecPhase2 with type (Integer,List(Integer),
PositiveInteger,PositiveInteger) -> Integer
fricas
Compiling function factor with type (Integer,Integer,Integer) ->
List(Integer)
 (5)
Type: List(Integer)
fricas
Time: 0.15 (EV) + 0.06 (OT) = 0.21 sec

fricas
test( reduce(*,%)=2^101-1 )
 (6)
Type: Boolean
fricas
Time: 0 sec

 Subject:   Be Bold !! ( 15 subscribers )