Loading ...
Sorry, an error occurred while loading the content.

24366Re: Impossible to Prove ??

Expand Messages
  • Aldrich
    Aug 4, 2012
    • 0 Attachment
      --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
      >
      >
      >
      > --- 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
      >

      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