| |
|
 Autor: |
|
Thema: Erweiterung Faktorisierung Fermat/Lehmann
|
|
|
Matheniete
(offline)
Newbie
Beiträge: 10
Mitglied seit: 26.07.2012
Deutschland
|
|
Re: Erweiterung Faktorisierung Fermat/Lehmann #2
|
Datum: 14.11.2013, 13:31 
|
Zu zerlegende Zahl N = X*Y
X/Y = T
N = X^2 / T
X = N^(0,5) * T^(0,5)
Y = N^(0,5) / T^(0,5)
X=A+B
Y=A-B
X-Y = 2*B
X+Y = 2*A
B = N^(0,5)*(T^(0,5)-1/T^(0,5))/ 2
A = N^(0,5)*((T^(0,5)+1/T^(0,5))/ 2
Bereichsbetrachtung
Schrittlänge
Z=A/B = (1+1/T) / (1-1/T)
Änderung Schrittlänge
(Z2-Z1)/(A2 – A1) =((1+1/T1) / (1-1/T1)-(1+1/T2) / (1-1/T2)) /(N^(0,5)/2)*((T2^(0,5)+1/T2^(0,5) -T1^(0,5)-1/T1^(0,5))
Durch die berechenbare Steigung lässt sich der Fermat Algorithmus im Umkreis der ganzzahligen Schrittlängen deutlich Steigern. Der Abstand zwischen den zu Überprüfenden A ergibt sich aus der Tatsache, dass die Summe der Nachkommastellen ca. 1 bzw. -1 ergeben soll. Vereinfacht mit der linearen Steigung gerechnet ergibt sich zum Bsp. für die Schrittlänge Z=3 der maximale Abstand zu
Restwert(Bi;(Z))=1= i*i/((N^(0,5)/2*2,6) --> i = 1,14*N^(0,25)
Dieser Wert ist nicht Genau und dient nur zur Eingrenzung des Suchbereichs. Nach der Startjustierung lassen sich die gefundenen Suchbereiche mit dem Restwert = 1 durch jeweiliges halbieren (die eine Hälfte mit Restwert = 0 die andere =1) mit log(i;2) Schritten überprüfen.
Dieses Verfahren ist nicht auf ganze Zahlen beschränkt. Auch mit Brüchen lässt es sich anwenden.
Binominator nicht Matheniete!
(Bisher wurde dieser Beitrag 12 mal editiert, als letztes von Matheniete am 17.11.2013 @ 15:23)
|
|
|
|
|
|
