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

Ontbinden in priemfactoren.
       
De meest kinderlijke manier om een getal  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  x2 1  mod n  vier verschillende oplossingen {1, n - 1, a, b}  mod n
waarbij  ggd(n, a - 1) = en ggd(n , b - 1) = q 

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

Er zijn nu vier oplossingen  mod n:
x ☰ 1  mod 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  x2 y2  (mod n) met y inverteerbaar mod n
Dan geldt  (x/y)2  ☰ 1  (mod n) 

Oké, maar hoe vinden we zulke x en y waarvoor x2 y2  (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 2332 - n een vrij klein getal zal zijn.
2332 - 53953 = 336
We ontbinden nu 336:   336 = 24 • 3 • 7
dus   2332 - 53953 = 24 • 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:
2232 - 53953 = -4224 =   -27 • 3 • 11
2242 - 53953 = -3777 =   lukt niet kleiner dan 50
2252 - 53953 = -3328 = -28 • 13 
2262 - 53953 = -2877  =  lukt niet
2272 - 53952 = -2424 =   lukt niet
2282 - 53953 = -1969 =  lukt niet
2292 - 53953 = -1512 = -23 • 33 • 7
2302 - 53953 = -1053 = -34 • 13
2312 - 53953 = -592 = -24 • 37
2322 - 53953 = -129 = -3 • 43
2332 - 53953 =  336 = 24 • 3 • 7
2342 - 53953 =  803 = lukt niet
2352 - 53953 = 1272 = lukt niet
2362 - 53953 = 1743 = lukt niet
2372 - 53953 =  2216 = lukt niet
2382 - 53952 =  2691 = 32 • 13 • 23
2392 - 53953 = 3168 = 25 • 32 • 11
2402 - 53953 = 3647 = lukt niet
2412 - 53953 =  4128 = 25 • 3 • 43
2422 - 53953 = 4611 = lukt niet
2432 - 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   2252 • 2302 = (-28 • 13) • (-34 • 13) = (28 • 34 • 132) = (24 • 32 • 13)= 18722 
(je kunt dus met deze lijst stoppen zodra zoiets lukt, dus we hadden bij 230 al kunnen stoppen)

Daarmee hebben we zo'n  x2 y2  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
       

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