Sorry, an error occurred while loading the content.

## 24366Re: Impossible to Prove ??

Expand Messages
• Aug 4, 2012
• 0 Attachment
>
>
>
> --- In primenumbers@yahoogroups.com,
> "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?
>
> No.
>
> > 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
>
> No.
>
> > 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;
> print(F(x,y));
>
> 100000000000000000039
>
> from which you may easily obtain
>
> X = 4950185869189924612835721591430071882362137191396995;
> Y = -6840988620591034906820556921677926059550551300711158;
> print(F(X,Y));
>
> 100000000000000000039
>
> by setting Z = z*(1+w)^100.
>
> I recommend
> for blow-by-blow solutions of such problems,
> using continued fractions.
>
> David
>

From the archives:

qfbsolve(Q,p)

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
empirical.

Aldrich
• Show all 18 messages in this topic