Faktorisierung (XXIX)

10/06/2011 - 23:21 von mock | Report spam
Mir ist aufgefallen, dass man eine Zahl àhnlich der Faktorisierung
nach Fermat (3. Binomische Formel) auch mit den Summen von Zahlen
bewerkstelligen kann:

Sei z = 763

Beispiel Fermat:

Man erhöht ein x=√z um jeweils 1 bis x²-z ein Quadrat y² ist und hat
die Lösung z=(x+y)(x-y) = 109⋅7

Mein Beispiel:

Ich addiere alle Zahlen aᵢ (aufsteigend, beginnend bei 0) bis zum
kleinsten (aₓ²+aₓ)/2>=z. Das kann man leicht erreichen, indem man
√(2z)=aₓ setzt und aₓ mit 0 oder 1 addiert. Dieses aₓ erhöhe ich so
lange um jeweils 1, bis zum Auffinden eines yₒ, so dass gilt (√((aₓ+j)²
+aₓ+j))²-z = (yₒ²+yₒ)/2. Der GGT von z und aₓ+j-yₒ ist dann nicht
trivial. aₓ+ja, yₒG, GGT(763,61-47)=7

Leider ist das Verfahren nicht effektiver als das Fermatsche, aber
vielleicht làsst sich etwas daraus machen.
 

Lesen sie die antworten

#1 mock
11/06/2011 - 01:30 | Warnen spam
Ich versehe mich leicht. Hier ein gp-Programm:

zv3;
\\ zu faktorisierende Zahl
ergebnis(g)=print(z," = ",g," * ",z\g) \\
Ergebnisanzeige
gss(x)=(x^2+x)
\2 \\ kleiner
Gauss - Summe der Zahlen von 1 bis x
a=sqrtint(2*z);if(gss(a)>z,a--);
while(1,h=gss(a++);if(h-gss(sqrtint(2*(h-z)))==z,ergebnis(gcd(z,a-
sqrtint(2*(h-z))));break()))

Ähnliche fragen