.
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 - 1
Nun 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) ;).