## qfbsolve

Expand Messages
• ... Aldrich, here is a partial answer to your question. Bill Allombert is the author of qfbsolve.
Message 1 of 5 , Sep 22, 2010
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))
>
>
>
>>

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

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

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.
Message 2 of 5 , Sep 23, 2010
--- 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))
> >
> >
> >
> >>
>
> >> 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
> >
> >
>
>
> 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
>
> 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
• ... 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
"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
• ... 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

> 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.
Message 5 of 5 , Oct 5, 2010
>
>
>
>
> > 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.