Karim Belabas on Sat, 16 Jul 2011 12:00:34 +0200


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

Re: znlog() behavior


* Max Alekseyev [2011-07-16 11:32]:
> I suspect the following error (issued by pari/gp development svn-13224
> version) is a bug, isn't it?
> 
> ? znlog(2,znprimroot(2^67-1))
>   ***   at top-level: znlog(2,znprimroot(2
>   ***                 ^--------------------
>   *** znlog: gen_Shanks_log: supplied order (= 67) is incorrect.

Not really :

(11:46) gp > ??znprimroot 
znprimroot(n):

   returns a primitive root (generator) of (Z/nZ)^*, whenever this latter group
is cyclic  (n = 4 or n = 2p^k or n = p^k,  where p is an odd prime and k >= 0).
If the group is not cyclic, the result is undefined. [...]
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

(11:46) gp > factor(2^67-1)
%1 = 
[   193707721 1]

[761838257287 1]

znprimroot() contains a few sanity checks but doesn't go out of its way to
prove that its input satisfies the above prerequisites, since this allows
slightly faster computations. In this case, these fail and the function returns
something which looks like a primitive root (and *would* be a primitie root
assuming one existed). 

znlog() then correctly warns you that something is wrong with your input.

Junk in, junk out :-)

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  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-bordeaux1.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`