Opened 8 years ago
Last modified 6 months ago
#15867 needs_review defect
Implement modular exponentiation for all polynomial rings
Reported by:  jpflori  Owned by:  

Priority:  major  Milestone:  sage6.4 
Component:  algebra  Keywords:  
Cc:  roed, jdemeyer, pbruin, jakobkroeker  Merged in:  
Authors:  Shashwat Singh  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/ghshashwat1002/mod_exponentation_polynom (Commits, GitHub, GitLab)  Commit:  c37ccc82230f9a45444a7d7e7096c8dbf50c496f 
Dependencies:  Stopgaps:  wrongAnswerMarker 
Description (last modified by )
sage: x = polygen(ZZ) sage: pow(x,100,x+1) x^100
Change History (25)
comment:1 Changed 8 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:2 Changed 8 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:3 Changed 5 years ago by
 Cc roed jdemeyer pbruin jakobkroeker added
 Stopgaps set to wrongAnswerMarker
comment:4 Changed 5 years ago by
 Description modified (diff)
comment:5 Changed 7 months ago by
 Branch set to u/ghshashwat1002/mod_exponentation_polynom
comment:6 Changed 7 months ago by
 Commit set to ff56f1041130acc517426cdd788dd65f6308b55d
comment:7 Changed 7 months ago by
 Status changed from new to needs_review
comment:8 followup: ↓ 12 Changed 7 months ago by
Thanks! Please add your full name in the "Authors" field.
comment:9 followup: ↓ 13 Changed 7 months ago by
Now that the modulus argument is no longer ignored, you should rename it from ignored
to something else (modulus
? mod
?).
comment:10 Changed 7 months ago by
comment:11 Changed 7 months ago by
 Commit changed from ff56f1041130acc517426cdd788dd65f6308b55d to c2a7b16db55073c168ab0512e574740c3cdfd984
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
c2a7b16  Implement modular exponentiation in polynomial rings Flint.

comment:12 in reply to: ↑ 8 Changed 7 months ago by
comment:13 in reply to: ↑ 9 Changed 7 months ago by
Replying to lorenz:
Now that the modulus argument is no longer ignored, you should rename it from
ignored
to something else (modulus
?mod
?).
renamed to modulus
and rewrote history :)
comment:14 followup: ↓ 16 Changed 7 months ago by
To compare to None
, we use is
and is not
rather than ==
and !=
:
 if modulus != None: + if modulus is not None:
comment:15 Changed 7 months ago by
 Commit changed from c2a7b16db55073c168ab0512e574740c3cdfd984 to 82931546c7580795b0cfdea2906af5f8d61a91d1
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
8293154  Implement modular exponentiation in polynomial rings Flint.

comment:16 in reply to: ↑ 14 Changed 7 months ago by
Replying to slelievre:
To compare to
None
, we useis
andis not
rather than==
and!=
: if modulus != None: + if modulus is not None:
Done (and rewrote history) :)
comment:17 followup: ↓ 18 Changed 7 months ago by
This patch makes things better in that it renders the implementation of __pow__
correct, but it is still kind of misses the point: The entire reason why pow()
has a "modulus" argument in the first place is that pow(x, e, m)
can be exponentially faster than pow(x, e) % m
! So, having an implementation of "modular exponentiation" that is simply exponentiation followed by modulo is rather pointless. It should use squareandmultiply with reductions at each step to keep things small.
The other issue is that the patch only affects modular exponentation for one particular univariate polynomial class in Sage, but there are tons of other polynomial implementations that still don't implement this correctly. Presumably, the best way to go would be to implement a generic modularexponentiation function (do we have that already?) and simply call it in each of the polynomial classes when the modulus
argument is given.
comment:18 in reply to: ↑ 17 ; followup: ↓ 21 Changed 6 months ago by
Replying to lorenz:
This patch makes things better in that it renders the implementation of
__pow__
correct, but it is still kind of misses the point: The entire reason whypow()
has a "modulus" argument in the first place is thatpow(x, e, m)
can be exponentially faster thanpow(x, e) % m
! So, having an implementation of "modular exponentiation" that is simply exponentiation followed by modulo is rather pointless. It should use squareandmultiply with reductions at each step to keep things small.The other issue is that the patch only affects modular exponentation for one particular univariate polynomial class in Sage, but there are tons of other polynomial implementations that still don't implement this correctly. Presumably, the best way to go would be to implement a generic modularexponentiation function (do we have that already?) and simply call it in each of the polynomial classes when the
modulus
argument is given.
I am going to begin work on a modular exponentiation function that is more efficient.
But before I begin, I had a few doubts:
 the polynomials are dealt by one of two C libraries: FLINT and NTL, so a general modular exponentiation function on polynomials must be written in python?
 Also, I am having trouble figuring where would I place the code for that, and understanding the organization of the polynomials code in general. If I could be pointed to a developer documentation on the same it will be very helpful
I started a mailing list thread here if that's more appropriate to respond to https://groups.google.com/g/sagedevel/c/5A8CDkj9jKo
comment:19 followup: ↓ 20 Changed 6 months ago by
If you're going to implement this on the level of __pow__
(which, according to python's interface specification is actually a reasonable thing to do), you will need to implement it for FLINT and NTL wrappers separately, since each implements __pow__
, so any inheritance would be overridden.
Also note that "efficient" powering of polynomials modulo other polynomials over QQ is less useful than you might initially think: it helps a LOT to not carry the higher order terms around, but the coefficient swell will still be significant, bounding the feasible powers to a relatively small range. For polynomials over finite fields, where coefficient swell is not an issue, this is an entirely different story.
You probably also want to document what exactly the modulo operation that you're doing, since ZZ[x]
by itself is not a Euclidean ring, so the concept of "remainder" may need further explanation. Are you using some kind of pseudo division?
As an example:
sage: R.<x>=ZZ['x'] sage: f=x^51 sage: m=3*x^2+1 sage: f % m x^5  1 sage: (3*f) % m x^3  3 sage: (9*f) % m x  9
comment:20 in reply to: ↑ 19 Changed 6 months ago by
Replying to nbruin:
You probably also want to document what exactly the modulo operation that you're doing, since
ZZ[x]
by itself is not a Euclidean ring, so the concept of "remainder" may need further explanation. Are you using some kind of pseudo division?
I think this is outside the scope here: The notion of reduction is simply whatever %
does for the parent ring, which should not surprise anyone. Improving the documentation for %
, if deemed insufficient, should be another ticket.
comment:21 in reply to: ↑ 18 ; followup: ↓ 22 Changed 6 months ago by
Replying to ghshashwat1002:
 the polynomials are dealt by one of two C libraries: FLINT and NTL, so a general modular exponentiation function on polynomials must be written in python?
Yes. In fact, I discovered that we already have such a function in Sage: sage.arith.misc.power_mod()
. The documentation (misleadingly) only talks about integers, but the implementation actually works for any ring where %
is defined. I've created #33244 to change this.
This means all we really need to do for this ticket is adding code along the lines of
if modulus is not None: return power_mod(self, exponent, modulus)
to all the .__pow__()
methods in polynomialring classes that do not yet handle the modulus
argument.
comment:22 in reply to: ↑ 21 Changed 6 months ago by
Replying to lorenz:
Replying to ghshashwat1002:
 the polynomials are dealt by one of two C libraries: FLINT and NTL, so a general modular exponentiation function on polynomials must be written in python?
Yes. In fact, I discovered that we already have such a function in Sage:
sage.arith.misc.power_mod()
. The documentation (misleadingly) only talks about integers, but the implementation actually works for any ring where%
is defined. I've created #33244 to change this.This means all we really need to do for this ticket is adding code along the lines of
if modulus is not None: return power_mod(self, exponent, modulus)to all the
.__pow__()
methods in polynomialring classes that do not yet handle themodulus
argument.
Hi, I had already written binary exponentiation (modular) using FLINT C functions directly. I'll replace my work with this.
However, I am wondering, would there be a significant efficiency advantage writing it in cython (and making calls to FLINT functions as opposed to python as in power_mod)
comment:23 followup: ↓ 25 Changed 6 months ago by
There certainly are circumstances where saving on Python overhead is worth it, but my guess is that it won't give a noticeable speedup here. In this algorithm (except for toysized inputs), virtually all of the time will be spent on polynomial arithmetic, which is already implemented in lowlevel code even if you call it from Python. But if your code is already functional, I figure there's no reason not to use it.
Out of curiousity: Do you have an application in mind where you need this operation to be really fast?
comment:24 Changed 6 months ago by
 Commit changed from 82931546c7580795b0cfdea2906af5f8d61a91d1 to c37ccc82230f9a45444a7d7e7096c8dbf50c496f
comment:25 in reply to: ↑ 23 Changed 6 months ago by
Replying to lorenz:
There certainly are circumstances where saving on Python overhead is worth it, but my guess is that it won't give a noticeable speedup here. In this algorithm (except for toysized inputs), virtually all of the time will be spent on polynomial arithmetic, which is already implemented in lowlevel code even if you call it from Python. But if your code is already functional, I figure there's no reason not to use it.
Out of curiousity: Do you have an application in mind where you need this operation to be really fast?
Not at the moment, no.
I just did it with power_mod therefore now. Probably best to reuse functions.
If someone deems it necessary to make power_mod
itself in cython then maybe I could use the code.
I couldn't find a __pow__
in the NTL implementation.
I am honestly struggling trying to find where to put appropriate code. Is there a detailed dev documentation somewhere?
Branch pushed to git repo; I updated commit sha1. New commits:
Implement modular exponentiation in polynomial rings Flint.