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

qfbsolve

Expand Messages
  • Kermit Rose
    ... Aldrich, here is a partial answer to your question. Bill Allombert is the author of qfbsolve.
    Message 1 of 5 , Sep 22, 2010
    • 0 Attachment
      On 9/22/2010 10:09 AM, primenumbers@yahoogroups.com wrote:
      >
      > There is 1 message in this issue.
      >
      > Topics in this digest:
      >
      > 1.1. Re: "wriggly" probable primes
      > From: Aldrich
      >
      >
      > Message
      > ________________________________________________________________________
      > 1.1. Re: "wriggly" probable primes
      > Posted by: "Aldrich" aldrich617@... aldrich617
      > Date: Wed Sep 22, 2010 1:38 am ((PDT))
      >
      >
      >
      > --- In primenumbers@yahoogroups.com, "djbroadhurst"<d.broadhurst@...> wrote:
      >>

      >> Exercise: Find two pairs of positive integers (x,y) such that
      >> 4065702994722252685573484796054334194691713593576645739409115721859519
      >> = 5x^2 + 5xy + y^2
      >>
      >> Comment: Pari-GP's "qfbsolve" enables a solution in two minutes.
      >> Devotees of "issquare", like Aldrich, may take considerably longer.
      >>
      >> David
      >>
      >
      > How does "qfbsolve" work? Will it enable fast solutions for all
      > A, or just special cases? If it fails to work is A then proved
      > prime?
      >
      > Aldrich
      >
      >

      Aldrich, here is a partial answer to your question.

      Bill Allombert is the author of qfbsolve.

      http://pari.math.u-bordeaux.fr/archives/pari-dev-0311/msg00004.html

      Hello PARI-dev,

      I have added a new function qfbsolve.

      qfbsolve(Q,p):

      Solve the equation Q(x,y) = p over the integers, where Q is a
      imaginary
      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 functions return only one solution and not all the solutions.

      This is a preliminary implementation. I plan to allow non prime p
      and real binary quadratic.

      This use a random polynomial time algorithm similar to cornacchia but
      probably due to Gauss, using the reduction of quadratic form.

      Cheers,
      Bill.
    • Aldrich
      ... Hi Kermit This is interesting material, but it does not really answer any of my questions. I ll check to see if any of references are more illuminating.
      Message 2 of 5 , Sep 23, 2010
      • 0 Attachment
        --- In primenumbers@yahoogroups.com, Kermit Rose <kermit@...> wrote:
        >
        > On 9/22/2010 10:09 AM, primenumbers@yahoogroups.com wrote:
        > >
        > > There is 1 message in this issue.
        > >
        > > Topics in this digest:
        > >
        > > 1.1. Re: "wriggly" probable primes
        > > From: Aldrich
        > >
        > >
        > > Message
        > > ________________________________________________________________________
        > > 1.1. Re: "wriggly" probable primes
        > > Posted by: "Aldrich" aldrich617@... aldrich617
        > > Date: Wed Sep 22, 2010 1:38 am ((PDT))
        > >
        > >
        > >
        > > --- In primenumbers@yahoogroups.com, "djbroadhurst"<d.broadhurst@> wrote:
        > >>
        >
        > >> Exercise: Find two pairs of positive integers (x,y) such that
        > >> 4065702994722252685573484796054334194691713593576645739409115721859519
        > >> = 5x^2 + 5xy + y^2
        > >>
        > >> Comment: Pari-GP's "qfbsolve" enables a solution in two minutes.
        > >> Devotees of "issquare", like Aldrich, may take considerably longer.
        > >>
        > >> David
        > >>
        > >
        > > How does "qfbsolve" work? Will it enable fast solutions for all
        > > A, or just special cases? If it fails to work is A then proved
        > > prime?
        > >
        > > Aldrich
        > >
        > >
        >
        > Aldrich, here is a partial answer to your question.
        >
        > Bill Allombert is the author of qfbsolve.
        >
        > http://pari.math.u-bordeaux.fr/archives/pari-dev-0311/msg00004.html
        >
        > Hello PARI-dev,
        >
        > I have added a new function qfbsolve.
        >
        > qfbsolve(Q,p):
        >
        > Solve the equation Q(x,y) = p over the integers, where Q is a
        > imaginary
        > 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 functions return only one solution and not all the solutions.
        >
        > This is a preliminary implementation. I plan to allow non prime p
        > and real binary quadratic.
        >
        > This use a random polynomial time algorithm similar to cornacchia but
        > probably due to Gauss, using the reduction of quadratic form.
        >
        > Cheers,
        > Bill.
        >

        Hi Kermit

        This is interesting material, but it does not really answer
        any of my questions. I'll check to see if any of references
        are more illuminating.

        Aldrich
      • djbroadhurst
        ... The Cornacchia-Smith algorithm is given by Henri Cohen as CCANT 1.5.2 and by also by Crandall and Pomerance 2.3.12. David
        Message 3 of 5 , Oct 2, 2010
        • 0 Attachment
          --- In primenumbers@yahoogroups.com,
          "Aldrich" <aldrich617@...> wrote:

          > This is interesting material, but it does not really answer
          > any of my questions. I'll check to see if any of references
          > are more illuminating.

          The Cornacchia-Smith algorithm is given by Henri Cohen
          as CCANT 1.5.2 and by also by Crandall and Pomerance 2.3.12.

          David
        • djbroadhurst
          ... Exercise: Find two pairs of positive integers (x,y) such that 5*x^2 + 5*x*y + y^2 = (137^137 + 1992)*(137^137 + 3464) Comment: This exercise may solved in
          Message 4 of 5 , Oct 2, 2010
          • 0 Attachment
            --- In primenumbers@yahoogroups.com,
            "djbroadhurst" <d.broadhurst@...> wrote:

            > The Cornacchia-Smith algorithm is given by Henri Cohen
            > as CCANT 1.5.2 and by also by Crandall and Pomerance 2.3.12.

            Exercise: Find two pairs of positive integers (x,y) such that
            5*x^2 + 5*x*y + y^2 = (137^137 + 1992)*(137^137 + 3464)

            Comment: This exercise may solved in 10 milliseconds.

            David
          • Aldrich
            ... Looks like a special case, a put-up job as the posties say. quibble, quibble. a.
            Message 5 of 5 , Oct 5, 2010
            • 0 Attachment
              --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
              >
              >
              >
              > --- In primenumbers@yahoogroups.com,
              > "djbroadhurst" <d.broadhurst@> wrote:
              >
              > > The Cornacchia-Smith algorithm is given by Henri Cohen
              > > as CCANT 1.5.2 and by also by Crandall and Pomerance 2.3.12.
              >
              > Exercise: Find two pairs of positive integers (x,y) such that
              > 5*x^2 + 5*x*y + y^2 = (137^137 + 1992)*(137^137 + 3464)
              >
              > Comment: This exercise may solved in 10 milliseconds.
              >
              > David
              >

              Looks like a special case, a put-up job as the posties
              say. quibble, quibble.

              a.
            Your message has been successfully submitted and would be delivered to recipients shortly.