WisFaq!

De digitale vraagbaak voor het wiskundeonderwijs

HOME

samengevat

\require{AMSmath}

Getal ontbinden met de ECM

Lieve Wisfaq,
Om grotere getallen te ontbinden in priemgetallen wordt soms de "elliptic curve method" (ECM) gebruikt. Hiermee kraakt bij voorbeeld de applet op www.alpertron.com.ar/ECM.HTM een getal als 1+7*10^48 snel. Kunt u mij uitleggen volgens welk principe de ECM werkt?
Groeten, Jaap
Jaap
Docent - zondag 4 januari 2004

Antwoord

Hallo Jaap,

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 y²=x³+ax²+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(x₁,y₁) en een elliptische kromme y²=x³+bx+c die door dit punt gaat, waarbij x₁,y₁ natuurlijke getallen zijn, b en c geheel. Dat is niet lastig: kies willekeurig x₁,y₁ 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:
(^a_k/_{d²_k},^b_k/_{d³_k})

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(d_k,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 1Dn 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 4b³+27c² 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

Vragen naar aanleiding van dit antwoord? Klik rechts..!
zondag 4 januari 2004