Aritmetikkens fundamentalteorem fortæller os, at de hele tal har entydig faktorisering, men den siger ikke noget om, hvordan vi skal udføre denne faktorisering. Formålet med dette foredrag er at belyse Lenstra’s algoritme til faktorisering af hele tal, herunder specielt dens anvendelse af gruppestrukturen på en elliptisk kurve.

De naturlige spørgsmål for mig har været:

• Hvordan og hvorfor virker algoritmen?
• Hvor hurtig er den.
• Hvorfor bruger man lige elliptiske kurver?

• Hvilke forbedringer af Lenstra kan man lave.

Antag nu at n>1 et helt tal. Et naturligt spørgsmål, inden det store arbejde med at faktorisere, må være: Er n et primtal?

Fermat’ lille sætning: Hvis p et primtal og (x,p)=1, så er x^(p-1)=1 mod p

Eksempel 1. n=246082373 => 2^(n-1)=180137693 mod n => n ej et primtal.

Eksempel 2. n=2699900771 => 2^(n-1)=1087755572 mod n => n ej et primtal.

Til de eksempler, som jeg vil komme med, er ovenstående metode tilstrækkelig.

Antag nu, at n ikke er et primtal. Jeg vil da skitsere en metode til at finde en faktor i n.

Da n ej et primtal har n en primfaktor p.

• Antag a valgt så [a] ligger i U(Z/pZ)

• Antagelse: k valgt så #U(Z/pZ)=p-1|k.

Da er a^k=1 mod p. Dette kan give os en faktor.

p|a^k-1 => (a^k -1,n)>=p. Hvis (a^k-1,n)<n så har vi en faktor.

1. Vælg K>1. Beregn k=LCM(1,2,…..,K)=2^a1*3^a2*5^a3*…*q^as
2. Vælg 1<a<n. Beregn D=(a,n).
1. Hvis 1<D<n så har vi en faktor og er færdige.
2. Hvis D=n så er vi uheldige og går til 2 og vælger et andet a.
3. Hvis D=1 fortsættes.
3. Beregn D=(a^k-1,n)
1. Hvis 1<D<n så har vi en faktor og er færdige.
2. Hvis D=n så er vi uheldige og går til 2 og vælger et andet a.
3. Hvis D=1 så går vi til 1 og vælger et større K.

• 1) Vi skal vælge et k i det håb at n har en primfaktor p så p-1|k. Derfor vælger vi et k med en masse divisorer: k=LCM(1,2,..,K).
• 3) Ifølge lemma 1 det blot nødvendigt at beregne 2^k-1 mod n. (sparer computerkraft)
• Algoritmen stopper på et tidspunkt, idet p-1|k for k=LCM(1,2..,K) når K>=(p-1)/2. Den tid som algoritmen tager afhænger af størrelsen på k, da vi skal beregne 2^k-1 mod n. Dette fører til følgende praktiske konklusion: Pollards algoritme virker såfremt n har en primfaktor p så p-1 er et produkt af små primtal.

n=246082373 (ej et primtal)

1. Vælg K=9, k=LCM(1,2,..,K)=2520.
2. Vælg a=2. (a,n)=1.
3. 2^k-1=130940740 mod n

• Pollards algoritme bygger på gruppestrukturen for Z/pZ.
• Vi kan opstille følgende svagt formulerede krav for om Pollards algoritme virker i praksis: n skal have en primfaktor p så p-1 er et produkt af små primtal.

Lenstra’s algoritme bygger på samme grundide som Pollard’s.

Da n ej et primtal har n en primfaktor p.

• Antag E en elliptisk kurve over Q, at P ligger på E og E_p en elliptisk kurve.
• Antag k valgt så #E_p(Z/pZ)|k

Da er k·P_p=0. Dette kan give os en faktor.

Det vi gør er at beregne k·P=(a_k/d_k²,b_k/d_k³) (Lemma 2)

Dvs k·P=(a_k·d_k,b_k,d_k³) kan p-reduceres til k·P_p=0 så må d_k=0 mod p. Dvs (d_k,n)>=p. Hvis (d_k,n)<n så har vi en faktor.

Antag n>2 ej et primtal. Vi ønsker at finde en faktor.

1) Beregn D=(6,n)

1. Hvis D>1 har vi en faktor. færdig
2. Hvis D=1 fortsættes.

1. Vi vælger en elliptisk kurve ved:

Vælg tal x, y, b mellem 1 og n.

Lad c=y²-x³-b*x

Bem: E: y²=x³+bx+c, P=(x,y) ligger på E(Q)

2. Beregn D=(4b³+27c²,n)
1. Hvis D=n så hop til 2a og vælg nyt b.
2. Hvis 1<D<n så har vi en faktor. Færdig
3. Hvis D=1 fortsæt
3. Vælg et K>1. Lad k=LCM(1,2,..,K)
4. Beregn k·P=(a_k/d_k²,b_k/d_k³). Beregn D=(d_k,n)
1. Hvis D=n hopper vi til 3) og vælger et mindre k.
2. Hvis 1<D<n så har vi en faktor. Færdig.
3. Hvis D=1 kan vi hoppe til 2) og vælge nyt b eller til 3) og vælge et nyt k.

• 1) hvis (6,n)=1 så er 2 og 3 ikke divisorer i n. Dette betyder at ligninger af typen y²=x³+bx+c dækker alle isomorfiklasser af elliptiske kurver over Z/pZ for primdivisorer p|n. (Knapp s. 57)
• 3) Vi tjekker at E og E_p er elliptiske kurver for alle p|n.
• 4) Vi vælger et k i håb om at #E_p(Z/pZ)|k for et p|n.
• 5) I stedet for at beregne k·P beregnes k·P mod n. Lemma 1 og Lemma 3 retfærdiggør at vi kan gøre dette. Additionsformlerne mod n er beskrevet i appendix. Hvis vi studerer additionsformlerne for den elliptiske kurve, ser vi, at formlerne bryder sammen (mod n) hvis og kun hvis vi står med et tal d så at D=(d,n)>1. Hvis D<n har vi en faktor ellers er vi uheldige og må starte forfra.

n=2699900771 ej et primtal

Vi udfører algoritmen

(n,6)=1

Vi vælger en elliptisk kurve og et punkt på den:

P = (2,1)

b = 1, c = 1² — 2³ —1·2 = -9

dvs. vores elliptiske kurve er E: y² = x³ + x - 9

(4b³+27c²,n) = 1

Vælger K=15, k = LCM(1,2,..,15) = 360360

k = 360360

= 2³ + 2⁵ + 2⁷ + 2⁸ + 2⁹ + 2¹⁰ + 2¹¹ + 2¹² +2¹³ + 2¹⁴ + 2¹⁶ + 2¹⁸

Ved hjælp af sædvanlige additionsformler har jeg beregnet 2ⁱ·P mod n for i mellem 1 og 18(se bilag) og derefter har jeg beregnet følgende punkter mod n vha. sædvanlige additionsformler: (2³+2⁵)·P, (2³+2⁵+2⁷)·P,…,k·P.

K·P=(860532099,1417592321) mod n

Men hov dette har jo ikke givet nogen faktor. Nej det skyldes, at n ikke har en primdivisor p, sådan at #E_p(Z/pZ)|k for den valgte elliptiske kurve E og det valgte tal k. Hvad gør vi så nu? Der er to muligheder: enten kan vi vælge et større k, eller også kan vi vælge en anden elliptisk kurve.

Vi prøver at vælge en anden elliptisk kurve. Vi går til step 2) og vælger et nyt b. For b=2,3,..42 kan vi beregne k·P mod n. Så der får vi heller ingen faktor

Sæt nu b = 43.

Vi kan beregne 2ⁱ·P mod n for alle i mellem 1 og 18. Jeg kan regne frem til

(2³ + 2⁵ + .. + 2¹⁶)·P = (2357880258,1300821445) mod n

Nu vil jeg forsøge at beregne k·P mod n

k·P = (2³ + 2⁵ + .. + 2¹⁶)·P + 2¹⁸·P

Additionsformlerne giver, at jeg skal finde en invers til 336343265-2357880258 i Z/nZ. Dette er ikke muligt, hvorfor ikke? Jo fordi (336343265-2357880258,n) = 26947. Dvs vi har fundet en faktor i n.

Vi bemærker at pointen i forhold til Pollards algoritme er, at Lenstras algoritme giver flere valgmuligheder: Hvis vi ikke får en faktor i første omgang behøver vi ikke øge k (hvilket ville betyde større forbrug af computerkraft). Derimod kan vi vælge en ny elliptisk kurve.

Opsummering af Lenstra’s algoritme.

• Den bygger på gruppestrukturen for elliptiske kurver.
• Vi kan opstille følgende svagt formulerede krav for om den virker i praksis: n skal have en primdivisor p sådan, at vi kan finde en elliptisk kurve E over Q så #E_p(Z/pZ) er et produkt af små primtal.

• Ovenfor har jeg skitseret hvordan og hvorfor Lenstra’s algoritme virker.
• Jeg har ikke fået sat mig ind i hvor hurtig algoritmen er.
• Jeg håber, at jeg har fået givet et indtryk af "hvorfor elliptiske kurver". For mig at se må det være fordi, at man har en masse forskellige elliptiske kurver og dermed forskellige #E_p(Z/pZ) til rådighed(?). Endvidere er der også formlen for addition af to punkter på den elliptiske kurve, som specifikt giver mig en faktor.
• Lenstra’s algoritme fører også frem til følgende to spørgsmål:

• Hvordan er fordelingen af #E_p(Z/pZ) for forskellige elliptiske kurver E? Vi har jo at tallene ligger i et interval bestemt af Hasse’s sætning.

• Er der hele tal i intervallet givet ved Hasse’s sætning, som kan siges at være et produkt af "små" primtal?

• Algoritmens hastighed afhænger af størrelsen af faktorerne i n.

Den bog jeg hovedsageligt har brugt er

Selvfølgelig har jeg også kigget i

Lenstra’s originale artikel findes i

Derudover har jeg skimmet følgende to tekster

Math. Of Computation, 1993 nr. 61, s. 445ff (R. D. Silverman And S. S. Wagstaff, Jr.: A practical analysis of the elliptic curve factoring algorithm.)

Lemma 1: Antag a,b,n hele tal. Antag b=a mod n.

Da gælder (b,n)=(a,n)

Bevis: Jeg bruger def. 3.1.2 i Alg 1 bog. Lad c=(a,n) og d=(b,n)

Lemma 2: Antag E: y²=x³+bx+c en elliptisk kurve over Q. P ligger på E(Q)\{0}.

Da er P på formen P=(a_k/d_k²,b_k/d_k³) hvor (a_k,d_k)=1=(b_k,d_k)

Bevis: Antag P=(m/M,n/N) (uforkortelige brøker, M,N>0).

• n²*M³=m³*N²+b*m*M²*N²+c*M³*N² (vha. kurvens ligning)
• N²|M³ og M²|N²
• N²|M³ og M³|N² (vha. kurvens ligning)
• N²=M³
• M=d_k² og N=d_k³ for et passende d_k (entydig faktorisering).

Lemma 3: Antag p et primtal så p|n

Lad S={s i Z| (s,n)=1}

Da gælder

1) S er multiplikativ. Dvs vi har lokalisering S^-1Z en delring af Q.

2) Følgende diagram af ringhomomorfier kommuterer:

Bevis:

1) s,t i S => (s,n)=1=(t,n) => (s·t,n) = 1 => s·t i S

Endvidere er 1 i S.

qed.

Setup: E: y²=x³+b·x+c en elliptisk kurve over Q.

Q₁=(x₁,y₁) og Q₂=(x₂,y₂) ligger på den elliptiske kurve.

Hvis x₁=x₂ mod n og y₁=-y₂ mod n er Q₁=-Q₂ mod n og Q₁+Q₂=0 mod n.

Ellers:

Bem: Dette giver mening ó D:=(y₁,n)=1

Hvis 1<D<n har vi en faktor.

Hvis D=n er vi uheldige og beregningen kan ikke lade sig gøre mod n.

Bem: Dette giver mening ó D:=(x₂-x₁,n)=1

Hvis 1<D<n har vi en faktor.

Hvis D=n er vi uheldige og beregningen kan ikke lade sig gøre mod n.

Så er

Q₃=(x₃,y₃) mod n , færdig.

n=2699900771

k = 360360

= 2³ + 2⁵ + 2⁷ + 2⁸ + 2⁹ + 2¹⁰ + 2¹¹ + 2¹² +2¹³ + 2¹⁴ + 2¹⁶ + 2¹⁸

P=(2,1)

E : y² = x³ + x — 9

Herefter følger punkterne mod n

2¹P 674975231 2362412938

2²P 1829156875 756880883

2³P 1405826909 752079457

2⁴P 1623498895 1986788186

2⁵P 1382333483 2211764966

2⁶P 1726878857 1907246394

2⁷P 1541203440 1149809620

2⁸P 2069987796 1299697929

2⁹P 740551282 1815456786

2¹⁰P 165063480 1392593857

2¹¹P 25276715 129880250

2¹²P 2049982611 1374446675

2¹³P 882417997 2618721850

2¹⁴P 885122155 400915515

2¹⁵P 2334561671 2622265852

2¹⁶P 1904471183 856043424

2¹⁷P 2139640562 2042013567

2¹⁸P 1411328980 2224186645

2³P 1405826909 752079457

(2³ + 2⁵)P 1922782989 859541328

(.. + 2⁷)P 2204849298 695329116

(.. + 2⁸)P 1730116303 1462619697

(.. + 2⁹)P 1149443832 885908106

(.. + 2¹⁰⁾P 705410552 1148138018

(.. + 2¹¹)P 292592555 139248920

(.. + 2¹²)P 1705603363 1219926924

(.. + 2¹³)P 1570683207 1073552762

(.. + 2¹⁴)P 1255139834 1391785173

(.. + 2¹⁶)P 626026554 1529987586

(.. + 2¹⁸)P 860532099 1417592321

E : y² = x³ + 43·x — 93

Herefter følger punkterne mod n

2¹P 674975945 1687417349

2²P 1935568486 998190584

2³P 1820219002 876621191

2⁴P 1626068413 2264448679

2⁵P 1021309937 1467280374

2⁶P 2380080395 312022427

2⁷P 2542557635 670914208

2⁸P 860756604 1019978361

2⁹P 655704292 1402722699

2¹⁰P 2343241826 1661311876

2¹¹P 2138750499 1430859278

2¹²P 26081599 499166945

2¹³P 1804741417 1973953680

2¹⁴P 2168969222 313575519

2¹⁵P 2130707230 217043797

2¹⁶P 904172551 1584759503

2¹⁷P 1874326830 1800802643

2¹⁸P 336343265 223462557

2³ 1820219002 876621191

(2³+2⁵)P 1241063773 21569020

(.. +2⁷)P 2376668195 1670412598

(.. +2⁸)P 914946137 582212382

(.. +2⁹)P 797475569 1756571365

(.. +2¹⁰)P 2208132890 2591113840

(.. +2¹¹)P 2364660358 2143324835

(.. +2¹²⁾P 2192180482 1638041108

(.. +2¹³)P 1065288789 1806230821

(.. +2¹⁴)P 684801980 490190805

(.. +2¹⁶)P 2357880258 1300821445

gcd(336343265-2357880258,n)=26947

> # Lenstras algoritme;

> # n:=48112959837082048697*54673257461630679457;

> # n:=1715761513;

> n := 26947*100193;

>

>

> # Initialisering;

> slut:=false:faktor:=false:d:=0:uheldig:=false:primtal:=false:forfra:=false:

> ny_b:=false:ny_k:=false:ny_pkt:=false:

> #Slut på initialisering;

>

> # Vi tjekker at n er et primtal;

> temp:=2&^(n-1) mod n:

> if (temp<>1) then primtal:=true:

> else slut:=true;fejltype:=1;fi:

> # Slut på tjek

>

> # Her starter algoritmen;

> # Algoritmen indeholder visse valg, som kan indtastes her;

> K_min:=15;K_max:=1000; step:=10;

> b_min:=1;b_max:=1000;

> x:=2;

> y:=1;

> # Initialisering

> K:=K_min:b:=b_min:

> # Step 1a;

> temp:=gcd(6,n):

> if (temp>1 and temp <n) then faktor:=true:d:=temp:

> elif temp=n then slut:=true;fi:

> # Slut på step 1a;

> #Step 1b;

> #Skulle her tjekke at n ikke et perfekt tal;

> #Slut på step 1b;

> #Her starter den store løkke;

> while (slut=false and faktor=false and primtal=true) do

> slut:=false:forfra:=false:faktor:=false:d:=0:

> #Step 2+3;

> # Vi kører for b mellem b_min og b_max og øger derefter K indtil K>=K_max;

> if (slut=false and forfra=false) then

> if ny_b=true then b:=b+1;ny_b:=false:fi:

> if b=b_max then b:=b_min;K:=K+step;lprint(K);fi:

> if K>=K_max then slut:=true;fi:

> c:=y^2-x^3-b*x mod n;

> P:=(x,y);

> fi:

> #Slut på step 2+3;

>

> #Start på step 4;

> if (slut=false and forfra=false) then

> temp:=gcd(4*b^3+27*c^2 mod n,n);

> if temp=n then ny_b:=true;forfra:=true;

> elif temp>1 then faktor:=true;d:=temp;fi;

> fi;

> #Slut på step 4;

>

> #Step 5

> if (slut=false and forfra=false) then

> k:=1:

> for i from 2 to K do

> k:=lcm(i,k);

> od;

> fi:

> #Slut på step 5;

>

> #Step 6

> if (slut=false and forfra=false) then

>

> # vi finder binær opskrivning af k;

> temp:=k:i:=0:

> while (temp<>0) do

> t1:=temp mod 2^(i+1);

> if t1=0 then a[i]:=0;

> else a[i]:=1;

> # lprint(i);

> fi;

> temp:=temp - a[i]*2^i;

> i:=i+1;

> od:

> s:=i-1:

> #slut på binær opskrivning af k;

>

> # nu beregner vi 2^iP;

> Q:=P:a[0]:=P;

> for i from 1 to s while (slut=false and forfra=false and faktor=false) do

>

> # Start på additionsalgoritme mod n;

> # Man kan være uheldig, få en faktor eller få P+Q (=P_Q); # Bem. følgende variable skal være definer

> # et: n, b, c, P, Q; # Derudover benyttes følgende variable: uheldig, faktor, d, x1, y1, x2, y2, P_Q, x3, y3

> # , g, lambda;

>

> uheldig:= false:d:=0:

> if P=nul then

> if Q=nul then P_Q:=nul;

> else P_Q:=Q;fi;

> elif Q=nul then P_Q:=P;

>

> else

>

> x1:=P[1]:

> y1:=P[2]:

> x2:=Q[1]:

> y2:=Q[2]:

>

> # Vi beregner lambda i tilf. P=Q;

> if (P=Q) then

> g:=gcd(y1,n):

> if (g=n) then uheldig:=true;fi:

> if (g>1 and g<n) then d:=g;faktor:=true;fi:

> if g=1 then lambda:=(3*x1^2+b)/(2*y1) mod n:fi:

> fi:

> # Slut på beregning af lambda i tilf. P=Q;

>

> # Vi beregner lambda i talfælde P<>Q og P<>-Q;

> if (x1<>x2 ) then

> g := gcd(x2-x1,n):

> if (g=n) then uheldig:=true;fi;

> if (g>1 and g<n) then d:=g;faktor:=true;fi;

> if (g=1) then lambda:=(y2-y1)/(x2-x1) mod n;fi;

> fi:

> # Slut på beregning i tilf. P<>Q og P<>-Q;

>

>

> # Vi bruger add. formler;

> if (y1=-y2) then P_Q:=nul;

> elif (uheldig=false) then

> x3:=lambda^2-x1-x2 mod n:

> y3:=-lambda*x3-(y1-lambda*x1) mod n:

> P_Q:=(x3,y3):

> fi:

> # Slut på brug af add. formler;

>

> fi:

> # Slut på additionsalgoritme mod n;

>

> if uheldig=true then forfra=true;ny_b:=true;

> else

> pkt[i]:=P_Q;

> # lprint(i, pkt[i]);

> P:=P_Q;Q:=P;

> fi;

>

> od;

> #Slut på beregning af 2^iP;

>

> #start på beregning af kP;

>

> kP:=nul;

> for i from 0 to s while (slut=false and forfra=false and faktor=false) do

> if a[i]=1 then

> P:=kP:Q:=pkt[i]:

> # Så adderer vi kP og pkt[i];

>

> # Start på additionsalgoritme mod n;

> # Man kan være uheldig, få en faktor eller få P+Q (=P_Q); Bem. følgende variable skal være defineret

> # et: n, b, c, P, Q; # Derudover benyttes følgende variable: uheldig, faktor, d, x1, y1, x2, y2, P_Q, x3, y3

> # g, lambda;

>

> uheldig:= false:d:=0:

> if P=nul then

> if Q=nul then P_Q:=nul;

> else P_Q:=Q;fi;

> elif Q=nul then P_Q:=P;

>

> else

>

> x1:=P[1]:

> y1:=P[2]:

> x2:=Q[1]:

> y2:=Q[2]:

>

> # Vi beregner lambda i tilf. P=Q;

> if (P=Q) then

> g:=gcd(y1,n):

> if (g=n) then uheldig:=true;fi:

> if (g>1 and g<n) then d:=g;faktor:=true;fi:

> if g=1 then lambda:=(3*x1^2+b)/(2*y1) mod n:fi:

> fi:

> # Slut på beregning af lambda i tilf. P=Q;

>

> # Vi beregner lambda i talfælde P<>Q og P<>-Q;

> if (x1<>x2 ) then

> g := gcd(x2-x1,n):

> if (g=n) then uheldig:=true;fi;

> if (g>1 and g<n) then d:=g;faktor:=true;fi;

> if (g=1) then lambda:=(y2-y1)/(x2-x1) mod n;fi;

> fi:

> # Slut på beregning i tilf. P<>Q og P<>-Q;

>

> # Vi bruger add. formler;

> if (y1=-y2) then P_Q:=nul;

> elif (uheldig=false) then

> x3:=lambda^2-x1-x2 mod n:

> y3:=-lambda*x3-(y1-lambda*x1) mod n:

> P_Q:=(x3,y3):

> fi:

> # Slut på brug af add. formler;

>

> fi:

> # Slut på additionsalgoritme mod n;

> if uheldig=true then forfra:=true;ny_b:=true:

> else

> kP:=P_Q;

> # lprint(i, kP);

> fi:

>

> fi;

> #Slut på add af kP og pkt[i];

>

> od;

> #slut på beregning af kP;

>

> fi:

> #Slut på Step 6;

>

> if (slut=false and faktor=false) then ny_b:=true;fi:

> od:

> # Slut på den store løkke;

>

> faktor;

> d;

> b_:=b;

> K_:=K;