Hoe ontbind je een groot getal in priemfactoren?

Question

Ik weet niet echt hoe ik het aan moet pakken. Als je bijvoorbeeld het getal 640 hebt, dan kan je toch niet eindeloos blijven proberen tot er eentje goed is? Is er niet een snelle manier om grote getallen te ontbinden in priemfactoren?

 · Accepted Answer

Begin altijd met het kleinste priemgetal (2 dus) en ga door tot die niet meer kan. Neem dan de volgende (3) en dan ook weer net zo vaak tot het niet meer kan.
Zo steeds verder.

Voorbeeld:
640 : 2 = 320
320 : 2 = 160
160 : 2 = 80
80 : 2 = 40
40 : 2 = 20
20 : 2 = 10
10 : 2 = 5
5 is een priemgetal, dus die kun je niet meer delen.
Dus:
640 = 2x2x2x2x2x2x2x5

 · Answer

Dit is een interessante vraag waarover menig wiskundige zich het hoofd heeft gebroken. De algoritmes om priemontbinden te vinden zijn momenteel niet veel beter dan brute force en evenzo is het bepalen van priemfactoren.
Voor relatief kleine getallen zoals 640 bestaan er natuurlijk trucs, zie bijvoorbeeld http://math.about.com/library/bldivide.htm
Hierbij kun je opmerken dat als 640 = a*b, dan zal een van beide factoren kleiner zijn dan sqrt(640)=25,2... en de ander groter. Dus bij het zoeken naar factoren hoef je alleen naar alle mogelijk priemfactoren onder de 25 te kijken.
Wanneer de getallen zo groot worden dat handmatige berekeningen ondoenlijk zijn, dan zijn er altijd nog computers waar je je toe kunt richten.
Probeer maar eens een groot geheel getal in Wolfram Alpha in te voeren ( http://www.wolframalpha.com ). Onder het kopje "Prime factorization" komt je ontbinding te staan.
Het feit dat ontbinding in priemfactoren zo'n lastig probleem is wordt uitvoerig gebruikt in de cryptografie. Kijk hiervoor maar eens op http://en.wikipedia.org/wiki/RSA_%28algorithm%29

Hoe ontbind je een groot getal in priemfactoren?

Het beste antwoord

Andere antwoorden (1)

Weet jij het beter..?