WisFaq!

Ggd, priemgetallen en meer...

Ik doe een po over de getaltheorie, nu zou ik graag willen weten waarom de ggd zo belangrijk is voor de getaltheorie. Ook heb ik ergens gelezen dat computers niet in staat zijn om priemgetallen groter dan 40 cijfers te vinden, is dat waar? En is men er al in geslaagd om getallen groter dan 140 te ontbinden? En zijn de mersenne priemgetallen ook van belang voor cryptografie?

Chantal
5-3-2002

Antwoord

De GGD is belangrijk omdat allerlei eigenschappen en bewerkingen tussen getallen juist wel of juist niet gelden afhankelijk van de GGD van die twee getallen. Aan de andere kant is het beetje 'vreemd' om er zo over te praten, want de GGD wil niets anders zeggen wat de grootste gemeenschappelijke deler van twee getallen is... en daar kan je toch niet om heen?

Dat computers best in staat zijn om priemgetallen groter dan 40 cijfers te vinden is onlangs maar eens bewezen door een 20-jarige student die in het GIMPS-project een nieuw Mersenne-priemgetal gevonden heeft. Dit getal, 2^13466917-1 bestaat uit maar liefst 4.053.946 cijfers (ongeveer de grootte van een paperback).

Het 'probleem' van het vinden van de ontbinding van getallen met 140 of meer cijfers is niet het probleem. Deze 'magische' grens heeft te maken met RSA. RSA is een cryptosysteem waarbij men het produkt van twee grote priemgetallen gebruikt om de berichten te versleutelen. Bij de introductie was het idee dat het minimaal 40 jaar zou duren voor men de ontbinden van dit grote getal zou kunnen vinden. Door inschakelen van heel veel verschillende computers over de hele wereld is men er in geslaagd de ontbinding veel eerder te vinden. Dat is niet erg, want dan neem je gewoon weer een ander groot produkt van twee priemgetallen (bijv. 130 of 140 cijfers). Uiteindelijk worden zo getal van 140 cijfers ook weer 'gekraakt', maar het heeft alles te maken met tijd!

Ik heb hier een programmatje dat getallen van wel 400 cijfers kan ontbinden... alleen mogen de delers niet grote zijn dan 40 cijfers....

Er zijn nog niet zoveel Mersenne priemgetallen bekend, dus als je die gaat gebruiken voor een cryptosysteem lijkt me dat niet zo slim. Je maakt het de potentiele 'kraker' wel erg makkelijk!

WvR
7-3-2002