Modular exponentiation of polynomials

[caruso]

A faster implementation of modular exponentiation of polynomials.

This implementation is used to improve speed in factorisation of skew polynomials (see ticket #13215).

[burcin]

Thanks for the patch. There are some minor issues, so I'm switching to needs_work. Here is a short review:

• The patch lacks doctests or a commit message.

• The call to _pow_modulus should be of the form self._pow_modulus(right, modulus) instead of Polynomial._pow_modulus(self, right, modulus). If Cython does not recognize that self is a Polynomial, you can declare that in the function definition, e.g. use def __pow__(Polynomial self, right, modulus).

• To extract maximum performance, I suggest replacing calls to self.parent() by direct attribute access (self._parent) and declaring the type of the n in the _pow_modulus() function to be an int, and pow to be Polynomial.

[caruso]

Thanks for you review. I've updated my patch.

• I added doctesta dn a commit message

• I replaced Polynomial._pow_modulus(self, right, modulus) by self._pow_modulus(right, modulus)

• It seems that I can't use self._parent in a def function and I don't want to assume that n fits in a int (e.g. for applications to skew polynomials where I need this function for very large n). I declared the variables pow and r.

[chapoton]

Some remarks (maybe useless, I am no Cython expert)

Maybe you could declare modulus to be a Polynomial ?

Maybe you could declare right to be an Integer (instead of an int) ?

Can you post here some timings to show how much this improves things ?

[caruso]

I declared right to be an Integer but not modulus to be a Polynomial because I guess that it could be also an Integer (or even something else).

Here are timings you are asking for:

sage: k = GF(5)
sage: l = k.extension(x^2 + 2)
sage: R.<x> = l[]
sage: f = R.random_element(5)
sage: h = R.random_element(5)

# Without the patch
sage: timeit("g=pow(f,50,h)")
5 loops, best of 3: 2.43 s per loop

# With the patch
sage: timeit("g=pow(f,50,h)")
5 loops, best of 3: 68.8 ms per loop
sage: timeit("g=pow(f,10000000,h)")
5 loops, best of 3: 276 ms per loop

[burcin]

There are doctests failing in sage/rings/polynomial/polynomial_element.pyx.

It seems that the _pow_modulus() function is duplicating code from sage.rings.arith.power_mod. Isn't there a way to use that function? Does the speed increase justify copying the code here? If we are going to copy it, shouldn't we put it higher in the class hierarchy?

[caruso]

Actually, I did not know the function power_mod (I duplicated and adapted the code from sage.rings.polynomial.polynomial_element.__pow__). I attach a new patch where I just call power_mod instead of _pow_modulus. Timings are comparable. I don't know if it's better this way. I let you judge.

[darij]

patchbot:

apply trac_13642_modular_exp_polynomial-2.patch

[chapoton]

some doctests are failing, see patchbot report

[tscrim]

git version where I marked the new tests as "not tested" which is now #15777. I believe we should merge this in and not make it depend on #15777.

---

New commits:

​d3e730d	trac #13642: modular exponentiation of polynomials
​9917b28	Reinstated doctest.
​878bd99	Marked new doctests as "not tested".

[jpflori]

Let's get this merged.

About the previously failing doctests: they were already failing before this ticket; therefore I agree with the decision to fix them in #15777.