Springen naar inhoud

Handige Methode Ontbinden in Priemfactoren


  • Log in om te kunnen reageren

#1

Odyssius

    Odyssius


  • >100 berichten
  • 128 berichten
  • Ervaren gebruiker

Geplaatst op 31 januari 2006 - 21:20

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?

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

TD

    TD


  • >5k berichten
  • 24049 berichten
  • VIP

Geplaatst op 31 januari 2006 - 21:22

Met een computerprogramma? Geef het cijfer gerust...

#3

Odyssius

    Odyssius


  • >100 berichten
  • 128 berichten
  • Ervaren gebruiker

Geplaatst op 31 januari 2006 - 21:26

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?

#4

TD

    TD


  • >5k berichten
  • 24049 berichten
  • VIP

Geplaatst op 31 januari 2006 - 21:37

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.

#5

Odyssius

    Odyssius


  • >100 berichten
  • 128 berichten
  • Ervaren gebruiker

Geplaatst op 31 januari 2006 - 21:41

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

#6

TD

    TD


  • >5k berichten
  • 24049 berichten
  • VIP

Geplaatst op 31 januari 2006 - 21:44

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.

#7

dr. E. Noether

    dr. E. Noether


  • >25 berichten
  • 96 berichten
  • Ervaren gebruiker

Geplaatst op 31 januari 2006 - 22:56

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!

#8

eXorikos

    eXorikos


  • >100 berichten
  • 134 berichten
  • Ervaren gebruiker

Geplaatst op 31 januari 2006 - 23:45

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...

#9

Elmo

    Elmo


  • >1k berichten
  • 3437 berichten
  • VIP

Geplaatst op 01 februari 2006 - 07:23

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...

#10

Odyssius

    Odyssius


  • >100 berichten
  • 128 berichten
  • Ervaren gebruiker

Geplaatst op 08 februari 2006 - 18:10

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





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures