WisFaq!

De digitale vraagbaak voor het wiskundeonderwijs

HOME

samengevat

\require{AMSmath}

Kwadratische zeef Pomerance

Het getal 8051 is mbv Fermat's methode te ontbinden in de priemfactoren 83 en 97. Ik las ergens dat hier een variant op is: de zg kwadratische zeef van Pomerance.

Ik snap niet hoe dit werkt. Deze methode blijkt ook te werken bij grote verschillen van de 2 factoren.
herman
Leerling bovenbouw havo-vwo - dinsdag 18 december 2012

Antwoord

De zeef van Pomerance ('uitgevonden' in 1984) werkt min of meer op gelijke manier als de methode van Fermat. Het te splitsen getal noemen we N.

Je probeert nu twee getallen x en y te vinden waarvoor x²·y²(modN) wat betekent dat N deelbaar is op x² - y² maar ook dat x² en y² bij deling door N dezelfde rest hebben.

Uit ggd(N,x² - y²) = N = ggd(N,x-y)·ggd(N,x+y) volgt dan een ontbinding van N.

Als voorbeeld nemen we N = 3737, een getal waarvan de wortel iets meer dan 61 is. We gaan nu starten met het rekenwerk vanaf r = 62.

Net als bij de methode van Fermat kijken we nu naar de rij getallen van de vorm (r + k)² - N = (62 + k)² - 3737 = k² + 124k + 107 waarbij we k een rij gehele getallen laten doorlopen, ook negatieve.

Als |k| niet al te groot wordt, dan zal (r + k)² - N klein zijn vergeleken met N. En kleinere getallen laten zich ontbinden in kleinere priemfactoren. De clou van de methode is nu dat we niet alle getallen in priemfactoren gaan ontbinden, maar alléén die getallen waarvan de priemfactoren niet boven een bepaalde grens G liggen.

Terug naar het gekozen getal 3737.
Het getal k laat ik lopen van -30 t/m 30 en als grens G neem ik 30.

Als bijv. k = -7, dan is k² + 124k + 107 gelijk aan -712 en dit laatste getal laat zich ontbinden als -2·2·2·89. Omdat 89 boven de grens G = 30 ligt, laat ik k = -7 verder buiten beschouwing.

Bij k = 1 is k² + 124k + 107 gelijk aan 232 wat ontbindt in 2·2·2·29, priemgetallen die alle onder de 30 liggen. Dus k = 1 doet daarom mee.

Voor alle k vanaf -30 t/m 30 doe je dit werk (d.w.z. dat laat je de computer doen).
Hieronder zie je drie 'goede' k-waarden met bijbehorende splitsing.

k = - 9 gaf -(2⁵)·29
k = - 3 gaf -2⁸
k = -1 gaf -2⁴

Let nu alleen op de laatste twee.
Daar staat dat (r - 3)²·(-2⁸) en (r - 1)²·(-2⁴) (beide modulo 3737)
Dit tweetal moduli vermenigvuldig je wat oplevert (r-3)²(r-1)²·2¹²

Merk op dat aan beide kanten van het modulusteken een kwadraat staat en denk dan nog even aan het begin van dit lange verhaal waar het over twee getallen x en y gaat.
Nu maar hopen dat er een echte factor uitrolt.
ggd(N,(r-3)(r-1) - 2⁶) = ggd(3737,59·61-64) = ggd(3737,3535) = 101

En inderdaad: 3737 = 101·37

Ten slotte:
er waren meer goede waarden voor k, maar toevallig liep het met de waarden k = -3 en k = -1 direct goed af. Puur geluk! Als die laatste ggd-berekening bijv. 1 zou hebben opgeleverd, was alle moeite vergeefs.
Berekeningen als deze lenen zich bij uitstek voor inzet van computers. Met de hand is het vrijwel onbegonnen werk.
De grenzen voor k en G zijn toevallig 30 maar ze hoeven niet gelijk te zijn.
Je zag dat bijv. k = -7 verder niet meedeed. Daarom heet de methode 'zeef'methode.
Veel plezier ermee!

MBL

Vragen naar aanleiding van dit antwoord? Klik rechts..!
maandag 24 december 2012

Re: Kwadratische zeef Pomerance