Re: square root modulo power of prime

["Karim Belabas" <Karim.Belabas@math.u-bordeaux1.fr>]

* Max Alekseyev [2007-05-18 04:13]:
> What is the best way to compute square roots modulo power of prime?
> sqrt() function does not like such modules:
> 
> ? sqrt(Mod(1,5^2))
>  *** sqrt: composite modulus in Fl_sqrt: 25.

The current behaviour is documented:

  ??sqrt
  [...] Intmod  a  prime  and p-adics are allowed as arguments. 

So sqrt(1 + O(5^2)) works.

There is currently no simple way to compute all square roots modulo a
general N [ must factor N yourself into primary factors, use the above,
then forvec ]

> btw, is there any reason why this rather basic function is not
> implemented in pari?

It is relatively expensive to test the inputs, for a marginal
increase in functionnality :

(11:43) gp > p=nextprime(10^20);
(11:43) gp > for(i=1,10^4,sqrt(Mod(2,p)))
time = 236 ms.

(11:43) gp > for(i=1,10^4, ispower(p);sqrt(Mod(2,p)))
time = 1,244 ms.
(11:43) gp > for(i=1,10^4, ispseudoprime(p);sqrt(Mod(2,p)))
time = 1,028 ms.

In these situations, p-adics inputs are clearer and contain much more
information than intmods, allowing us to quickly decide what internal
function to call:

(11:43) gp > for(i=1,10^4,sqrt(2+O(p^2)))
time = 276 ms.

> Similar question about znlog() function. Why it does not work modulo
> power of prime?

Here it's a little different since znlog() is quite a bit slower than
sqrt, so testing the inputs wouldn't be expensive. But consistency is
nice: almost all non-trivial functions operating on intmods assume that
the modulus is prime, for the simple reason that otherwise it should be
factored ( issquare() is an exception )

[ NB: This is a design flaw. The t_INTMOD type is far too simple for general
modular operations: it should allow giving the modulus in factored form.
In fact, even for INTMODs mod a prime, some precomputed data would be
useful (e.g. Montgomery representation to speed up reduction mod N). ]

> Again, what is the best workaround for that?

1) znlog for p-adics (p odd) should work but doesn't [ I'll fix that ]

2) Currently you must use ideallog over Q :

  \\ precomputed
  N = 100;
  nf = nfinit(x);
  bid = idealstar(nf, N);

  \\ discrete log mod a general N
  (11:43) gp > ideallog(nf, 3, bid);
  %4 = [7, 1]~   \\ (Z/N)* has two cyclic components


Cheers,

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