Karim Belabas on Fri, 18 May 2007 12:12:37 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: square root modulo power of prime |
* 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]