Opened 9 years ago

Closed 7 years ago

#13642 closed defect (fixed)

Modular exponentiation of polynomials

Reported by: caruso Owned by: AlexGhitza
Priority: major Milestone: sage-6.2
Component: algebra Keywords: modular exponentiation, polynomials
Cc: Merged in:
Authors: Xavier Caruso Reviewers: Burcin Erocal, Travis Scrimshaw, Jean-Pierre Flori
Report Upstream: N/A Work issues:
Branch: 878bd99 (Commits, GitHub, GitLab) Commit: 878bd99af7fb041f9a61887693e062cf0b1e20e9
Dependencies: Stopgaps:

Status badges

Description (last modified by jpflori)

A faster implementation of modular exponentiation of polynomials.

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

Attachments (2)

trac_13642_modular_exp_polynomial.patch (3.7 KB) - added by caruso 8 years ago.
trac_13642_modular_exp_polynomial-2.patch (2.8 KB) - added by caruso 8 years ago.

Download all attachments as: .zip

Change History (18)

comment:1 Changed 9 years ago by caruso

  • Status changed from new to needs_review

comment:2 Changed 8 years ago by burcin

  • Reviewers set to Burcin Erocal
  • Status changed from needs_review to needs_work

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.

comment:3 Changed 8 years ago by caruso

  • Status changed from needs_work to needs_review

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.

comment:4 Changed 8 years ago by 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 ?

comment:5 Changed 8 years ago by 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

Changed 8 years ago by caruso

comment:6 Changed 8 years ago by burcin

  • Status changed from needs_review to needs_work

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?

comment:7 Changed 8 years ago by caruso

  • Description modified (diff)
  • Status changed from needs_work to needs_review

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.

Changed 8 years ago by caruso

comment:8 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:9 Changed 8 years ago by chapoton

  • Authors changed from caruso to Xavier Caruso

comment:10 Changed 8 years ago by darij

patchbot:

apply trac_13642_modular_exp_polynomial-2.patch

comment:11 Changed 8 years ago by jdemeyer

  • Description modified (diff)

comment:12 Changed 8 years ago by chapoton

  • Status changed from needs_review to needs_work

some doctests are failing, see patchbot report

comment:13 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:14 Changed 7 years ago by tscrim

  • Branch set to public/ticket/modular_exponents-13642
  • Commit set to 878bd99af7fb041f9a61887693e062cf0b1e20e9
  • Reviewers changed from Burcin Erocal to Burcin Erocal, Travis Scrimshaw
  • Status changed from needs_work to needs_review

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:

d3e730dtrac #13642: modular exponentiation of polynomials
9917b28Reinstated doctest.
878bd99Marked new doctests as "not tested".

comment:15 Changed 7 years ago by jpflori

  • Description modified (diff)
  • Reviewers changed from Burcin Erocal, Travis Scrimshaw to Burcin Erocal, Travis Scrimshaw, Jean-Pierre Flori
  • Status changed from needs_review to positive_review

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.

comment:16 Changed 7 years ago by vbraun

  • Branch changed from public/ticket/modular_exponents-13642 to 878bd99af7fb041f9a61887693e062cf0b1e20e9
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.