Frage von Aliaxos, 55

wie kann ich ein Algorithmus schreiben der eine Anzahl n bestimmt und drückt sie als Produkt von Primzahlen?

Expertenantwort
von hypergerd, Community-Experte für Mathematik, 13

Eine der schnellsten Computerfunktionen nennt sich Modulo

(x mod y = x % x)

Sie ergibt den Rest der Division x/y.

Mann kann also erst die 2 und ab der 3 alle ungeraden Zahlen testen und bei jedem Ergebnis 0 -> ist ein Teiler gefunden. Also teilen und nächste ungerade Zahl testen...

http://www.lamprechts.de/gerd/php/RechnerMitUmkehrfunktion.php

(siehe Bild )

macht das online bis 16 stellige Faktoren recht schnell...

Aber danach wird es exponentiell langsam!

Nun kommt es auf den Typ der zu untersuchenden Zahl an. Die groben kleinen Faktoren sind ja raus -> also Untersuchung auf:

Typ: Carmichael, Fermat, Mersenne

http://www.lamprechts.de/gerd/php/Carmichael-Zahl-Faktorisierer.php

sobald es einer dieser Typen ist, findet man auch 500 stellige Faktoren recht schnell.

Wenn nicht (z.B. bei RSA-Zahlen), dann wird es richtig kompliziert.

https://de.m.wikipedia.org/wiki/Elliptische_Kurve

ist zwar schneller als Modulo (100 stellige Zahlen unter 15 min)

aber es gibt bis heute 309stellige Zahlen (Typ RSA), die damit bis heute nicht aufgelöst sind (also ob Prime, oder weitere Faktoren).

Kommentar von TeeTier ,

Kleiner Fehler:

(x mod y = x % x)

... sollte so aussehen:

(x mod y = x % y)
Kommentar von hypergerd ,

Ja natürlich! Habe mal wieder zu schnell geschrieben. Danke.

Antwort
von valvaris, 48

Kannst du. Das ganze nennt sich Primfaktorenzerlegung und wird für die RSA-Verschlüsselung verwendet.

http://users.informatik.uni-halle.de/~ahyjb/krypto/Factor/RSAFac.html

Expertenantwort
von Willibergi, Community-Experte für Mathematik, 26

Dazu gibt es einige Verfahren.

Mehr dazu hier: https://de.m.wikipedia.org/wiki/Faktorisierungsverfahren

Ich hoffe, ich konnte dir helfen; wenn du noch Fragen hast, kommentiere einfach. 

LG Willibergi

Keine passende Antwort gefunden?

Fragen Sie die Community

Weitere Fragen mit Antworten