- --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
>

From the archives:

>

>

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

> http://www.alpertron.com.ar/QUAD.HTM

> for blow-by-blow solutions of such problems,

> using continued fractions.

>

> David

>

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 - "Aldrich" <aldrich617@...> wrote:

> I don't see how

Let w = (1+sqrt(5))/2 be the fundamental unit.

> it immediately follows from Hardy/Wright Theorem 257 that

> A = 5x^2 + 5xy + y^2 has as values ALL of the possible

> values of primes that are +/- 1 mod 10.

HW prove that every prime p = +/-1 mod 10 is of the form

norm(a+b*w) = a^2 + a*b - b^2

for some integer pair [a,b].

Lemma: Every prime p = +/-1 mod 10 is of the form

norm(2*x+y+x*w) = 5*x^2 + 5*x*y + y^2

for some integer pair [x,y].

Proof: Set x = b, y = a-2*b.

David