Ik ben mijn thesis aan het maken over elliptische krommen, dus dit zou wel moeten lukken... Het algoritme in kwestie wordt ook wel Lenstra's algoritme genoemd.
Allereerst moet je weten dat elliptische krommen krommen zijn van de vorm y2=x3+ax2+bx+c.
Bovendien is er op die krommen een optelling van punten gedefinieerd: gegeven twee punten, P en Q, gelegen op de kromme E. Om (P+Q) te berekenen: verbind P met Q, zoek het derde snijpunt van deze rechte met E (dat is er altijd), en spiegel dit punt dan tov de x-as. Dit geeft je het punt P+Q.
Om P+P te bepalen moet je de "rechte door P en P " bepalen, in dat geval kies je de raaklijn in P aan de kromme E, zoek weer het derde punt en spiegel tov x-as. Op deze manier kan je dus, vertrekkende van P, de punten 2P,3P,... bepalen.
En dan nu het algoritme zelf. Input: een getal n waarvan je weet dat het niet priem is. Output: niet-triviale delers van n.
1. Kies een punt P(x1,y1) en een elliptische kromme y2=x3+bx+c die door dit punt gaat, waarbij x1,y1 natuurlijke getallen zijn, b en c geheel. Dat is niet lastig: kies willekeurig x1,y1 en b, en bepaal dan c.
2. Kies een k, zijnde een natuurlijk getal dat een product is van veel relatief kleine priemgetallen, typisch kiest men hiervoor het kleinste gemeen veelvoud van de eerste M natuurlijke getallen.
3. Bereken k*P (dus P+P+P+...+P, k termen 'P'). Dit zal altijd een punt zijn met volgende coördinaten:
(ak/d2k,bk/d3k)
Het bewijs dat die noemer tot de tweede macht voorkomt in de x-coördinaat, en tot de derde macht in de y-coördinaat, is vrij lastig.
4. Bereken D=ggd(dk,n). n is het te ontbinden getal.
Als D=1 moet je teruggaan naar stap 2 en een hogere k kiezen, ofwel naar stap 1 en opnieuw beginnen met een andere elliptische kromme.
Als D=n moet je teruggaan naar stap 2 en een lagere k kiezen.
Als 1
Dn dan is D een deler van n en is het algoritme geslaagd. Nu zijn er twee elementen belangrijk aan zulke algoritmes: werkt het in een ietwat doenbare tijd, en waarom is het beter dan andere algoritmes.
- Doenbare tijd: het berekenen van de ggd kan via Euclides' delingsalgoritme in een logaritmische tijd, dus snel. Ook het berekenen van kP gebeurt snel, vooral omdat je elke berekening modulo n mag doen.
- Het is efficiënter dan andere, gelijkaardige algoritmes, zoals het algoritme van Pollard, waarop het ongeveer gebaseerd is. Dat komt omwille van volgende redenering: bij Pollards algoritme moet je ook zo een k kiezen, en die steeds groter laten worden wanneer blijkt dat het algoritme geen oplossing geeft. Het kan echter zijn dat je nooit een oplossing krijgt!
Terwijl in dit algoritme, als je merkt dat je niet snel genoeg een oplossing krijgt, kies je gewoon een andere kromme, en je start met een propere lei. Bovendien bestaat er een stelling dat 'de krommen vrij gelijkmatig verdeeld zijn', dwz dat je meestal niet te veel krommen moet uitproberen vooraleer het algoritme een oplossing biedt.
NB: er zijn nog twee andere stappen die je moet controleren: je n mag geen 2- of 3-voud zijn, en geen macht van een natuurlijk getal, en de discriminant 4b3+27c2 mag geen n-voud zijn, maar dat zijn allemaal details die weinig met de werking van het algoritme te maken hebben, en stappen die zeer snel na te gaan zijn.
Ik hoop dat dit al min of meer het principe duidelijk maakt, als je nog meer uitleg wilt of er is iets niet duidelijk, dan reageer je maar.
Groeten,
Christophe
4-1-2004