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

... komplette Frage anzeigen

3 Antworten

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

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von TeeTier
02.09.2016, 13:14

Kleiner Fehler:

(x mod y = x % x)

... sollte so aussehen:

(x mod y = x % y)
1

Was möchtest Du wissen?