kwadratische zeef, ontbinden in priemfactoren

© h.hofstede (h.hofstede@hogeland.nl)

Ontbinden in priemfactoren.

De meest kinderlijke manier om een getal n te ontbinden in zijn priemfactoren is gewoon door te proberen door welke priemgetallen je het allemaal kunt delen.
Oké, wie een beetje slim is ziet natuurlijk dat je het maar hoeft te proberen tot en met √n, want als het door een groter getal deelbaar was, dan was het ook door een kleiner getal deelbaar, en dat hadden we dan al gevonden.

Voor echt grote getallen (van bijvoorbeeld meer dan 20 cijfers) zijn betere manieren nodig.......
Je raadt het al: hier komt er eentje.

Kwadratische zeef.

De kwadratische zeef is gebaseerd op de volgende stelling:

Stel dat n = p • q met p en q twee verschillende priemgetallen,
dan heeft de vergelijking x² ☰ 1 mod n vier verschillende oplossingen {1, n - 1, a, b} mod n
waarbij ggd(n, a - 1) = p en ggd(n , b - 1) = q

Bewijs.

x² ☰ 1 mod pq is gelijk aan het stelsel x² ☰ 1 mod p en x² ☰ 1 mod q (mits ggd(p, q) = 1 maar dat is natuurlijk zo)
immers: (p is een deler van x² - 1 en q is een deler van x²- 1) ⇔ (pq een deler van x²- 1)

Er zijn nu vier oplossingen mod n:
x ☰ 1 mod p en x ☰ 1 mod q
x ☰ -1 mod p en x ☰ -1 mod q
x ☰ 1 mod p en x ☰ -1 mod q
x ☰ -1 mod p en x ☰ 1 mod q

De eerste geeft x ☰ 1 (mod n)
De tweede geeft x ☰ -1 (mod n)
Noem de derde oplossing a, dan is ggd(n, a - 1) = p
Noem de vierde oplossing b, dan is ggd(n, b - 1) = q

q.e.d.

Hoe gaan we dit toepassen?

Stel dat we een groot getal n willen ontbinden in priemgetallen.
Stel dat we twee getallen x en y kunnen vinden waarvoor x² ☰ y² (mod n) met y inverteerbaar mod n
Dan geldt (^x/_y)² ☰ 1 (mod n)

Oké, maar hoe vinden we zulke x en y waarvoor x² ☰ y² (mod n) ?????????
Dat is het makkelijkst met een voorbeeld uit te leggen.

Stel dat we n = 53953 willen ontbinden
√53953 = 232,27..... en dat betekent dat 233² - n een vrij klein getal zal zijn.
233² - 53953 = 336
We ontbinden nu 336:   336 = 2⁴ • 3 • 7
dus   233² - 53953 = 2⁴ • 3 • 7 (mod n)

Dit gaan we voor een aantal getallen rondom 233 op dezelfde manier doen (daarbij telt -1 ook als "priemfactor"). We nemen alleen degenen met priemfactoren allemaal kleiner dan 50.
Dat geeft:
223² - 53953 =-4224 =-2⁷• 3 • 11
224² - 53953 = -3777 =   lukt niet kleiner dan 50
225² - 53953 = -3328 = -2⁸ • 13
226² - 53953 = -2877 = lukt niet
227² - 53952 = -2424 =   lukt niet
228² - 53953 = -1969 = lukt niet
229² - 53953 = -1512 = -2³ • 3³ • 7
230² - 53953 = -1053 = -3⁴ • 13
231² - 53953 = -592 = -2⁴ • 37
232² - 53953 = -129 = -3 • 43
233² - 53953 = 336 = 2⁴ • 3 • 7
234² - 53953 = 803 = lukt niet
235² - 53953 = 1272 = lukt niet
236² - 53953 = 1743 = lukt niet
237² - 53953 = 2216 = lukt niet
238² - 53952 = 2691 = 3² • 13 • 23
239² - 53953 = 3168 = 2⁵ • 3² • 11
240² - 53953 = 3647 = lukt niet
241² - 53953 = 4128 = 2⁵ • 3 • 43
242² - 53953 = 4611 = lukt niet
243² - 53953 = 5096 = lukt niet

Nu proberen we er twee uit deze lijst te kiezen zodat samengenomen alle priemfactoren op een even aantal uitkomen.
Je ziet dat   225² • 230² = (-2⁸ • 13) • (-3⁴ • 13) = (2⁸ • 3⁴ • 13²) = (2⁴ • 3² • 13)²= 1872² (je kunt dus met deze lijst stoppen zodra zoiets lukt, dus we hadden bij 230 al kunnen stoppen)Daarmee hebben we zo'n x² ☰ y² gevonden.
Bereken de ggd van beide getallen: ggd(53953, 225 • 230 - 1872) = ggd(53953, 49878) = 163
(dat laatste natuurlijk met het Euclidisch algoritme)

Eindresultaat   59353 = 163 • 331