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: |
Description (last modified by )
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)
Change History (18)
comment:1 Changed 9 years ago by
- Status changed from new to needs_review
comment:2 Changed 8 years ago by
- Reviewers set to Burcin Erocal
- Status changed from needs_review to needs_work
comment:3 Changed 8 years ago by
- 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)
byself._pow_modulus(right, modulus)
- It seems that I can't use
self._parent
in a def function and I don't want to assume thatn
fits in aint
(e.g. for applications to skew polynomials where I need this function for very largen
). I declared the variablespow
andr
.
comment:4 Changed 8 years ago by
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
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
comment:6 Changed 8 years ago by
- 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
- 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
comment:8 Changed 8 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:9 Changed 8 years ago by
comment:10 Changed 8 years ago by
patchbot:
apply trac_13642_modular_exp_polynomial-2.patch
comment:11 Changed 8 years ago by
- Description modified (diff)
comment:12 Changed 8 years ago by
- Status changed from needs_review to needs_work
some doctests are failing, see patchbot report
comment:13 Changed 7 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:14 Changed 7 years ago by
- 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
comment:15 Changed 7 years ago by
- 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
- Branch changed from public/ticket/modular_exponents-13642 to 878bd99af7fb041f9a61887693e062cf0b1e20e9
- Resolution set to fixed
- Status changed from positive_review to closed
Thanks for the patch. There are some minor issues, so I'm switching to needs_work. Here is a short review:
_pow_modulus
should be of the formself._pow_modulus(right, modulus)
instead ofPolynomial._pow_modulus(self, right, modulus)
. If Cython does not recognize thatself
is aPolynomial
, you can declare that in the function definition, e.g. usedef __pow__(Polynomial self, right, modulus)
.self.parent()
by direct attribute access (self._parent
) and declaring the type of then
in the_pow_modulus()
function to be anint
, andpow
to bePolynomial
.