Faktorisierung, die 123.

28/03/2008 - 00:27 von mock | Report spam
Ich habe eine Möglichkeit gefunden, die Trefferquote bei der
Faktorisierung von Zahlen zu erhöhen.

Seien z aus N die zu faktorisierende Zahl und i < sqrt(z) aus N der
Teiler:

Im Vergleichsfall *) überprüft man fortlaufend, ob mod ( z , i ) == 0,
und erhàlt x Teiler. Wenn man nun **) statt der einfachen Zahlen i ein
q(i) berechnet, erhàlt man x + y Teiler mit oft y > 0.

Das q sei die Quersumme von z zur Basis i, d. h. im Binàrsytem,
Ternàrsystem usw. Dadurch erhàlt man beispielsweise im Fall z 31415926535089 die folgenden Ergebnisse mit dem Teiler 605323 (im
Dezimalsystem angegeben):

*) **)
i = 5447907 q(i) = 5447908
q(i) = 5189945
i = 4842584 q(i) = 4842585
q(i) = 4324954
i = 4237261 q(i) = 4237262
q(i) = 3992265
i = 3631938 q(i) = 3631939
i = 3026615 q(i) = 3026616
q(i) = 2883303
q(i) = 2594973
q(i) = 2471403
i = 2421292 q(i) = 2421293
i = 1815969 q(i) = 1815970
q(i) = 1297487
q(i) = 1265841
i = 1210646 q(i) = 1210647
i = 605323 q(i) = 605324

Voilà. x = 9 und y = 8.
 

Lesen sie die antworten

#1 mock
28/03/2008 - 19:45 | Warnen spam
Pardon!

Selbstverstàndlich meinte ich nicht, man erhielte mehrere Teiler,
sondern mehrere Ergebnisse, die einen Teiler != 1 ergeben. Ebenso
selbstverstàndlich prüfe ich die Ergebnisse auf einen ggT != 1.

Ich finde es erstaunlich, dass eine andere Funktion als f(i) ggT(z,i), nàmlich q(i) = ggT(z,Quersumme von z im Zahlensystem i),
immer mehr oder gleich viele Ergebnisse liefert.

Gibt es weitere Funktionen dieser Art? Kann man die Zahlen q(i), die
ungleich i + 1 sind, auf andere Weise ermitteln? Ist das vielleicht
sogar ein Weg, das Faktorisierungsproblem zu lösen?

Ähnliche fragen