Handige Methode Ontbinden in Priemfactoren

Moderators: dirkwb, Xilvo

Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
Reageer

Bericht 31-01-'06, 21:20

Odyssius

Gebruikersavatar
Berichten: 128

Handige Methode Ontbinden in Priemfactoren

Voor m'n les wiskunde moet ik RSA kunnen kraken. Om dit te doen moet je een getal m kunnen ontbinden in priemfactoren. Ik heb echter het ongeluk dat m een getal is van meer dan 30 cijfers. Weet er iemand een goede techniek om dit getal te ontbinden?
Omhoog

Bericht 31-01-'06, 21:22

TD

Gebruikersavatar
Berichten: 24.578

Re: Handige Methode Ontbinden in Priemfactoren

Met een computerprogramma? Geef het cijfer gerust...
Omhoog

Bericht 31-01-'06, 21:26

Odyssius

Gebruikersavatar
Berichten: 128

Re: Handige Methode Ontbinden in Priemfactoren

het cijfer is: 8 155 564 322 963 545 435 233 042 348 043

als je een computerprogramma gebruikt, zou je me ook kunnen zeggen welk of hoe het werkt?
Omhoog

Bericht 31-01-'06, 21:37

TD

Gebruikersavatar
Berichten: 24.578

Re: Handige Methode Ontbinden in Priemfactoren

Derive had er bij mij wat moeite mee maar dat kan ook omdat ik redelijk wat programma's tegelijk aan het draaien ben. Er kwam nog geen antwoord na een halve minuut, toen heb ik geannuleerd. Mathematica geeft het antwoord in een seconde, er zijn precies twee priemfactoren:

8155564322963545435233042348043 = 666666777777727*12233344445555509

De klassieke manier is "trial & error division" (kijken of het getal deelt door opeenvolgende priemgetallen) maar vanaf grotere getallen worden er ook algoritmes gebruikt, wat Mathematica betreft zijn dit "Pollard p-1", "Pollard rho" en kwadratische zeefalgoritmen.
Omhoog

Bericht 31-01-'06, 21:41

Odyssius

Gebruikersavatar
Berichten: 128

Re: Handige Methode Ontbinden in Priemfactoren

Kun je me zeggen hoe je het berekent via een engelstalige Derive versie nr 5?
Omhoog

Bericht 31-01-'06, 21:44

TD

Gebruikersavatar
Berichten: 24.578

Re: Handige Methode Ontbinden in Priemfactoren

Je geeft het getal in, selecteren en dan Simplify-Factor of ctrl-F.

Er is dan een optie "Prime Number Decomposition".

Dit is hoe het in Derive 6 is, vermoedelijk in 5 precies hetzelfde of zeer gelijkaardig. Of het Derive gaat lukken is een andere vraag, maar je kan proberen.
Omhoog

Bericht 31-01-'06, 22:56

dr. E. Noether

Berichten: 96

Re: Handige Methode Ontbinden in Priemfactoren

Je kunt hiervoor ook gebuik maken van een dienst op het internet, b.v.

http://www.alpertron.com.ar/ECM.HTM

Dat getal van jou van 30 cijfers doet ie in een fractie van een seconde!
Omhoog

Bericht 31-01-'06, 23:45

eXorikos

Berichten: 134

Re: Handige Methode Ontbinden in Priemfactoren

Hoe doet zo'n programma dat in godsnaam? :roll: Ik zie totaal niet hoe ik aan zo'n probleem zou moeten beginnen, behalve dan om elk priemgetal af te gaan tot je er bent...
Omhoog

Bericht 01-02-'06, 07:23

Elmo

Gebruikersavatar
Berichten: 3.437

Re: Handige Methode Ontbinden in Priemfactoren

Zo verschrikkelijk veel priemgetallen zijn er nu ook niet hoor. De wortel van 8155564322963545435233042348043 is ongeveer 2x1015, en dat betekent dat er ongeveer 2x1015/log[2x1015] priemgetallen zijn. Dat komt neer op ruwweg 1013, wel veel maar niet ondoenlijk.

Er zijn getal-theoretische methoden om nog veel sneller te factoriseren, kijk maar eens hier, of voor speciale gevallen hier .
Never underestimate the predictability of stupidity...
Omhoog

Bericht 08-02-'06, 18:10

Odyssius

Gebruikersavatar
Berichten: 128

Re: Handige Methode Ontbinden in Priemfactoren

In het programma dat dr. E. Noether ons aanraadde spreekt men over de Elliptic Curve Method, iemand die weet wat dit is?
Omhoog
Reageer

Terug naar “Wiskunde”