Karim Belabas on Tue, 07 Feb 2017 09:40:44 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: bnfisintnorm


* Charles Greathouse [2017-02-07 08:55]:
> Given a prime p = 1 mod 3, how can I use bnfisintnorm to find a (the?)
> value of x such that p = x^2 + 3y^2? I don't understand the output format.

0) Just use

  qfbsolve(Qfb(1,0,3), p)   \\ here, just Cornacchia

1) bnfisintnorm is (more general but) more complicated in this case
because it will solve x^2 - x*y* + y^2 = n and you have to deal with
changes of variables yourself.

2) Another possibility [ a little worse than qfbsolve in this case ] 
is thue(x^2+3, p)  [ returns all solutions,  ]

  (09:37) gp > thue(x^2+3,7)
  %2 = [[-2, -1], [-2, 1], [2, -1], [2, 1]]

  (09:37) gp > p = nextprime(10^1000);
  (09:37) gp >  thue(x^2+3, p);
  time = 957 ms.
  (09:37) gp > qfbsolve(Qfb(1,0,3), p);
  time = 901 ms.


N.B. Update from master before trying thue() on this one: an oversight
caused it to return half-integers in this case [ until 5 minutes ago].

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux         Fax: (+33) (0)5 40 00 21 23
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`