Ultraschnelle Faktorisierung < Numerik < Hochschule < Mathe < Vorhilfe
|
Ich stelle mal die Vermutung auf, daß alle Pseudoprimzahlen mit Basis 2
faktorisiert werden können, wenn man sie auf Basis 7 prüft.
Natürlich mit Außnahme der wenigen Pseudoprimzahlen die auch
gegenüber Basis 7 pseudoprim sind.
Ich habe die ersten 43 Zahlen von 341 bis 31417 getestet und alle
haben funktioniert.
Zitat Wiki:
Michele Cipolla konstruierte im Jahr 1904 auf folgende Weise unendlich viele Fermatsche Pseudoprimzahlen zu jeder Basis:
Für jedes a > 1 und jede ungerade Primzahl p, die [mm] a(a^2-1) [/mm] nicht teilt, ist
[mm] n=\frac{a^p-1}{a-1}\cdot\frac{a^p+1}{a+1}
[/mm]
eine Fermatsche Pseudoprimzahl zur Basis a.[1] Da es unendlich viele Primzahlen gibt, muss es demnach auch zu jeder Basis unendlich viele Fermatsche Pseudoprimzahlen geben. Beispiele:
Zitat Ende:
Kann man nicht eine Zahl Pseudoprim zur Basis 2 machen und die Faktoren erhalten. Dann müßte man nur noch die Basis 7 annehmen und die Faktoren wären da.
Das gilt besonders für große Zahlen - Public Key.
MfG
Krzyzape
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 07:20 Di 22.04.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
