I spent most of the weekend failing to adapt Will Jagy's algorithm, encouraged by a delusion that I understood better why that should work. Once that notion had been dispelled, Victor's method succeeded at once, and generalises to an arbitrary quadratic form as follows. (A) To represent a prime number p by a quadratic form f(x, y) : (1) Solve quadratic equation f(w, 1) = 0 over |F_p ; (2) Reduce the lattice basis { [w, 1], [p, 0] } to a minimal basis; (3) Now either reduced vector yields [s, t] such that f(s, t) = p . The second quadratic root actually applies to the conjugate form, so that signs in step (3) may be incorrect. Efficient polynomial-time algorithms are eg. Tonelli-Shanks for step (1), and enhanced Euclidean for step (2). However, one's favourite CAS these days conceals such drudgery behind clean facades, such as Magma's Sqrt() and LLL() . Useful test info is available at http://oeis.org/wiki/User:Peter_Luschny/BinaryQuadraticForms There remain two supplementary questions. (B) Exactly why does method (A) work? (C) How do representations of prime factors combine into representations of a composite target? All these seem bread-and-butter questions to my innocent mind, and it is mystifying that they are not part-and-parcel of standard treatments. Or are they? Fred Lunnon On 4/14/18, Victor Miller <victorsmiller@gmail.com> wrote:
Yes, See my answer to the question about the sum of two squares:
https://mathoverflow.net/questions/70208/system-of-diophantine-equations?rq=...
For your problem you need to find a primitive 6th root of unity (really just finding sqrt(-3)), then set up the lattice and apply LLL.
Fred Lunnon <fred.lunnon@gmail.com> wrote:
There exists an algorithm for finding integers m,n such that x = m^2 + n^2 , in amortised time proportional to (log x)^3 , where x is prime with x mod 4 = 1 . See Richard E. Crandall, Carl Pomerance "Prime Numbers: A Computational Perspective" Springer (2001), sect 2.3.2 pp 93--96 .
Is there an analogous efficient algorithm for x = m^2 + m n + n^2 ? See https://en.wikipedia.org/wiki/Eisenstein_integer https://oeis.org/A034017 , https://oeis.org/A000086
What about more general binary quadratic forms?
Fred Lunnon
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun