Max Alekseyev on Sat, 25 Mar 2023 23:08:10 +0100

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

Re: polrootsmod(f,p) with f%p==0

Hi Karim,

Ok, I understand. 
On a related note, - why does polrootsmod() not allow prime powers as a modulus? 
I see that there is polhensellift() which does Helsel lifting for a given (whole) factorization, and it's natural to expect that there should be a "simplified" version of it that takes care only about roots (i.e., linear factors). It seems that polrootsmod() could do that internally, but it does not. 


On Sat, Mar 25, 2023 at 5:27 PM Karim Belabas <> wrote:
Hi Max,

  first, please show your code: there must be a better solution.

Second, there are a number of drawbacks to what you propose:
- to avoid the error, you can easily trap this exception or test for the
  0 polynomial yourself in a user function, say POLROOTSMOD with the
  semantic you expect. So we have easy and efficient workarounds.

- all polroots* function currently raise an exception on the 0 polynomial;
  polrootsmod handling a finite ring is the only one for which we
  *could* make an exception [together with the obsolete polrootsff]).
  Consistency is nice.

- by "chance" we don't provide root multiplicities in polrootsmod
  [in which case the proposed change wouldn't make sense].
  But polrootsmod and polrootspadic are actually inconsistent with polroots
  and polrootsreal ! (the former don't take multiplicities into account,
  the latter do) It has been requested in the past to fix that
  inconsistency and provide a way to obtain multiplicities [rejected on
  grounds of backward compatibility but it was a close decision].
  This becomes impossible if we make the proposed change.

- the delicate situation is not when you get a memory error but have
  p about parisizemax, the latter being large. Then your machine is going to
  start swapping. For unlucky values of p, this may essentially kill
  your session (huge result gets stored in a variable or history entry and
  then, you get memory errors whenever you try anything new)

All in all, the balance is not is favour of changing this.



* Max Alekseyev [2023-03-25 19:57]:
> Well, there will be a memory allocation error in this case, but it'll work
> fine in many other cases with small p.
> I'd prefer to see a memory error in the case of large p rather than the
> "zero polynomial in FpX_roots" error unconditionally.
> Regards,
> Max
> On Sat, Mar 25, 2023 at 2:36 PM Bill Allombert <
>> wrote:
> > On Sat, Mar 25, 2023 at 12:46:49PM -0400, Max Alekseyev wrote:
> > > Shouldn't polrootsmod(f,p) for a prime p and f%p==0 simply return
> > > vector(p,i,Mod(i-1,p)) instead of the error?
> >
> > Given that p can be arbitrarily large, this is not practical...
> > Just consider polrootsmod(0*x,2^127-1)
> >
> > Cheers,
> > Bill
> >
> >

Pr Karim Belabas, U. Bordeaux, Vice-président en charge du Numérique
Institut de Mathématiques de Bordeaux UMR 5251 - (+33) 05 40 00 29 77