numbers Priemfactor Rekenmachine star

Hoe Het Werkt

Priemfactorontbinding betekent een getal schrijven als een product van zijn priembouwstenen — bijvoorbeeld 60 = 2² × 3 × 5. De hoofdstelling van de rekenkunde garandeert dat elk geheel getal groter dan 1 precies één zo'n ontbinding heeft (afgezien van het herschikken van de factoren): er is maar één manier om 60 te ontbinden in priemgetallen, ongeacht in welke volgorde u probeert te delen. Deze uniciteit maakt priemfactorontbinding een zinvolle, goed gedefinieerde bewerking in plaats van een kwestie van keuze.

De tool vindt dit via proefdeling: eerst worden zoveel mogelijk factoren van 2 eruit gedeeld (waarbij wordt geteld hoe vaak 2 er precies in past), daarna gaat men naar oneven kandidaten — 3, 5, 7, 9, 11… — en deelt elk zo vaak als past, tot aan de vierkantswortel van wat overblijft. Uitgewerkt voorbeeld voor 360: deel drie keer door 2 (360→180→90→45, dus 2³), dan is 45 oneven — deel twee keer door 3 (45→15→5, dus 3²), dan blijft 5 over, wat zelf een priemgetal is (5¹). Resultaat: 360 = 2³ × 3² × 5, en dit terugvermenigvuldigen — 8 × 9 × 5 — bevestigt 360. Als geen enkele kandidaat tot √n het overblijvende getal gelijk deelt, is dat overblijvende getal zelf een priemgetal en sluit dit de ontbinding af.

Wat U Moet Weten

Kleine en middelgrote getallen worden op deze manier bijna direct ontbonden. Maar dezelfde proefdelingsaanpak wordt rekenkundig zeer zwaar voor zeer grote getallen — honderden cijfers — omdat het aantal te controleren kandidaten enorm toeneemt, en er geen bekend efficiënt (polynomiaal) algoritme bestaat voor algemene gehele getallen op klassieke computers. Deze asymmetrie — twee grote priemgetallen met elkaar vermenigvuldigen is snel, maar hun product terug ontbinden is traag — is niet zomaar een curiositeit, het is exact de veiligheidsbasis van RSA-cryptografie met openbare sleutel: een publieke sleutel wordt opgebouwd uit het product van twee enorme geheime priemgetallen, en het breken van de versleuteling zou vereisen dat dat product wordt ontbonden, wat momenteel onhaalbaar is bij de gebruikte sleutelgroottes.

• 1 heeft helemaal geen priemfactorontbinding — het is noch priem, noch samengesteld, en de conventie van het "lege product" behandelt het als een speciaal geval.
• Een getal dat proefdeling tot aan zijn eigen vierkantswortel doorstaat zonder dat er iets op deelt, is per definitie een priemgetal.
• Naast cryptografie ligt factorisatie ten grondslag aan het vereenvoudigen van breuken, het vinden van de grootste gemene deler (ggd) en het kleinste gemene veelvoud (kgv), en het bepalen van hoeveel delers een getal heeft.