24366Re: Impossible to Prove ??
- Aug 4, 2012--- In email@example.com, "djbroadhurst" <d.broadhurst@...> wrote:
>From the archives:
> --- In firstname.lastname@example.org,
> "Aldrich" <aldrich617@> asked:
> > if p was not known already known to be prime
> > or even if it was a possible value of F(x,y), would the
> > qfbsolve procedure prove it to be so straightaway?
> > If it had factors that were exclusively +/- 1 mod 10, would
> > all of the locations of p be immediately evident and its
> > factors automatically identified
> > how does the qfbsolve procedure actually work?
> It depends crucially on the sign of the discriminant.
> In the case of
> G(x,y) = 2*x^2 + 2*x*y + y^2 = (x + y)^2 + x^2
> with negative discriminant 2^2 - 4*2 = -4,
> we may solve G(x,p) = p, for prime p = 1 mod 4,
> by finding the Gaussian prime x + y + sqrt(-1)*x
> whose norm is p. This is unique, up to multiplication
> by powers of sqrt(-1), or conjugation, and may be found
> using Algorithm 1.5.3 of CCANT by Henri Cohen.
> In the case of
> F(x,y) = 5*x^2 + 5*x*y + y^2 = (5*x/2 + y)^2 - 5*(x/2)^2
> with positive discriminant 5^2 - 4*5 = 5, there is an infinity
> of solutions to F(x,y) = p, for prime p = +/- 1 mod 10.
> In this latter case qfbsolve gives a solution
> to F(x,y) = p, for prime p = +/- 1 mod 10,
> that is unique up to multiplication by unities,
> or conjugation. However there is an infinity of unities:
> see Hardy and Wright, Section 15.4.
> Suppose that we have found [x,y] such that p is the norm of
> z = 2*x + y + w*x, where w = (1+sqrt(5))/2 is the fundamental
> unit, satisfying w^2 = 1+w, conj(w) = 1-w, norm(w) = -1.
> Then we may obtain an infinity of solutions
> Z = 2*X + Y + w*X, by multiplying z by any positive integral
> power of w^2 = 1+w, or any such power of conj(w^2) = 2-w,
> both of whose norms are unity.
> For example, you saw that qfbsolve gave
> F(x,y) = 5*x^2 + 5*x*y + y^2;
> x = 5355540695;
> y = -1733283533;
> from which you may easily obtain
> X = 4950185869189924612835721591430071882362137191396995;
> Y = -6840988620591034906820556921677926059550551300711158;
> by setting Z = z*(1+w)^100.
> I recommend
> for blow-by-blow solutions of such problems,
> using continued fractions.
Solve the equation Q(x,y) = p over the integers,
where Q is a binary quadratic form and p a prime number.
Return [x,y] as a two-components vector, or zero if there
is no solution. Note that this function returns only
one solution and not all the solutions. Let D = \disc Q.
The algorithm used runs in probabilistic polynomial
time in p (through the computation of a square root of D
modulo p); it is polynomial time in D if Q is imaginary,
but exponential time if Q is real (through the computation
of a full cycle of reduced forms). In the latter case,
note that bnfisprincipal provides a solution in heuristic
subexponential time in D assuming the GRH.
The library syntax is GEN qfbsolve(GEN Q, GEN p).
As to the status of proofs of conjectures relating
to qfbsolve, my guess is that many of them are still
- << Previous post in topic Next post in topic >>