Karim Belabas on Sat, 15 Oct 2022 09:51:29 +0200


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

Re: polcyclo: overflow in precp(). 

* Max Alekseyev [2022-10-14 20:25]:
> Dear Karim,
> 
> Thank you for the explanation. As for using t_INTMOD, I see the following
> issue:
> 
> ? polcyclo(22,Mod(10,2))
> %1 = Mod(1, 2)
> ? polcyclo(22,Mod(10,11))
> %2 = Mod(0, 11)
> 
> but
> 
> ? polcyclo(22,Mod(10,22))
>   ***   at top-level: polcyclo(22,Mod(10,22))
>   ***                 ^-----------------------
>   *** polcyclo: impossible inverse in Fl_inv: Mod(11, 22).
>   ***   Break loop: type 'break' to go back to GP prompt
> 
> Why is this happening?

For the same reason as in my previous mail, we use

 (*)    Prod_{d|n} (x^d - 1) ^ mu(n/d)

formally without bothering to check what "x" is. We do take care about
the possibility x^d - 1 = 0 at every step, though: in a field everything
is fine, even if x is a root of unity.

In Z/22Z, checking that x^d != 1 is not enough for x^d - 1 to be invertible ...
All this is documented in ??polcyclo:

  In the evaluated case, the algorithm assumes that a^d - 1 is either 0 or
  invertible, for all d | n. If this is not the case (the base ring has zero
  divisors), use subst(polcyclo(n),x,a).

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251), Université de Bordeaux
Vice-président en charge du Numérique
T: (+33) 05 40 00 29 77; http://www.math.u-bordeaux.fr/~kbelabas/
`