Natürliche Zahl in zwei Quadratzahlen zerlegen
-
Ich suche was in der Form n = a^2 + b^2. Aber kein Programm, das alles durchprobiert, sondern eine Formel zum ausrechnen.
-
Manuelito schrieb:
Ich suche was in der Form n = a^2 + b^2. Aber kein Programm, das alles durchprobiert, sondern eine Formel zum ausrechnen.
Ohne Einschränkung n prim. Zerlege n in \mathbb{Z}[i] ein Produkt von zwei Primidealen (Diese sind Hauptideale). Dazu musst du X^2 + 1 modulo p faktorisieren <=> suche Quadratwurzel von -1 mod p. Dazu gibt es z.B. den Shanks-Tonelli-Algorithmus. Wenn X^2 - 1 = (X - a)(X + a) deine Faktorisierung ist, dann sind (i - a, p) und (i + a, p) deine gesuchten Ideale. Mit dem euklidischen Algorithmus kannst du den ggT von i +- a und p in \mathbb{Z}[i] berechnen und somit eine Darstellung als Hauptideal (x + iy) mit x,y ganzzahlig bestimmen. Dann ist p = x^2 + y^2.
EDIT: Nur aus Neugierde, wozu brauchst du das?
-
Ribosom schrieb:
Ohne Einschränkung n prim.
Da steh ich grad auf der Leitung, wieso?
-
Jester schrieb:
Ribosom schrieb:
Ohne Einschränkung n prim.
Da steh ich grad auf der Leitung, wieso?
Wenn n = x^2 + y^2, m = u^2 + v^2 Summe zweier Quadrate sind, dann hat man auch die Darstellung von nm, indem man (x + iy)(u + iv) = (xu - yv) + (xv + yu)i rechnet und dann (xu - yv)^2 + (xv + yu)^2 = nm erhält.
-
was sind ideale?
-
-
Ja schon, nur da scheiterts schon an dem Begriff "Zahlenring" ^^
-
Dann wär vielleicht der Thread was für dich: http://www.c-plusplus.net/forum/viewtopic-var-t-is-203454.html
-
@ Ribosom: Danke für deine Antwort, aber um ehrlich zu sein, versteh ich überhaupt nichts. Da wird ausprobieren dann wohl der bessere Weg sein
-
http://en.wikipedia.org/wiki/Shanks-Tonelli_algorithm
Damit erhältst du (wenn ich die Zerlegung richtig verstanden habe (ich kenne zumindest die verwendeten Begriffe ;)) und p := n ist, man korrigiere dich gegebenenfalls) eine Zahl R für die in C++-Notation gilt: (R * R) % p == p - 1Nun ist die Behauptung, dass ggT(R + i, p) und ggT(R - i, p) die gesuchten Zahlen a, b sind. Das i ist dabei die imaginäre Einheit, den ggT berechnest du mit dem euklidischem Algorithmus (der praktischerweise auch in |Z[i] funktioniert, implementier ihn vielleicht einfach erstmal allgemein).
Du musst also zwei Algorithmen bauen, den Bereich dazwischen füllen geht auch. Und schneller als ausprobieren sollte das schon sein (zumindest wenn n ausreichend groß ist) ;).