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: sage-6.4
Component: algebra Keywords:
Cc: roed, jdemeyer, pbruin, jakobkroeker Merged in:
Authors: Shashwat Singh Reviewers:
Report Upstream: N/A Work issues:
Branch: u/gh-shashwat1002/mod_exponentation_polynom (Commits, GitHub, GitLab) Commit: c37ccc82230f9a45444a7d7e7096c8dbf50c496f
Dependencies: Stopgaps: wrongAnswerMarker

Status badges

Description (last modified by jdemeyer)

sage: x = polygen(ZZ)
sage: pow(x,100,x+1)
x^100

Change History (25)

comment:1 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:2 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:3 Changed 5 years ago by jakobkroeker

  • Cc roed jdemeyer pbruin jakobkroeker added
  • Stopgaps set to wrongAnswerMarker

comment:4 Changed 5 years ago by jdemeyer

  • Description modified (diff)

comment:5 Changed 7 months ago by gh-shashwat1002

  • Branch set to u/gh-shashwat1002/mod_exponentation_polynom

comment:6 Changed 7 months ago by git

  • Commit set to ff56f1041130acc517426cdd788dd65f6308b55d

Branch pushed to git repo; I updated commit sha1. New commits:

ff56f10Implement modular exponentiation in polynomial rings Flint.

comment:7 Changed 7 months ago by gh-shashwat1002

  • Status changed from new to needs_review

comment:8 follow-up: Changed 7 months ago by slelievre

Thanks! Please add your full name in the "Authors" field.

comment:9 follow-up: Changed 7 months ago by lorenz

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 gh-shashwat1002

  • Authors set to Shashwat Singh

comment:11 Changed 7 months ago by git

  • Commit changed from ff56f1041130acc517426cdd788dd65f6308b55d to c2a7b16db55073c168ab0512e574740c3cdfd984

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

c2a7b16Implement modular exponentiation in polynomial rings Flint.

comment:12 in reply to: ↑ 8 Changed 7 months ago by gh-shashwat1002

Replying to slelievre:

Thanks! Please add your full name in the "Authors" field.

Yeah, done! :)

comment:13 in reply to: ↑ 9 Changed 7 months ago by gh-shashwat1002

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 follow-up: Changed 7 months ago by slelievre

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 git

  • Commit changed from c2a7b16db55073c168ab0512e574740c3cdfd984 to 82931546c7580795b0cfdea2906af5f8d61a91d1

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

8293154Implement modular exponentiation in polynomial rings Flint.

comment:16 in reply to: ↑ 14 Changed 7 months ago by gh-shashwat1002

Replying to slelievre:

To compare to None, we use is and is not rather than == and !=:

-                if modulus != None:
+                if modulus is not None:

Done (and rewrote history) :)

Last edited 7 months ago by gh-shashwat1002 (previous) (diff)

comment:17 follow-up: Changed 7 months ago by 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 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 square-and-multiply 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 modular-exponentiation 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 ; follow-up: Changed 6 months ago by gh-shashwat1002

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 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 square-and-multiply 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 modular-exponentiation 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/sage-devel/c/5A8CDkj9jKo

comment:19 follow-up: Changed 6 months ago by nbruin

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^5-1
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 lorenz

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 ; follow-up: Changed 6 months ago by lorenz

Replying to gh-shashwat1002:

  • 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 polynomial-ring classes that do not yet handle the modulus argument.

Last edited 6 months ago by lorenz (previous) (diff)

comment:22 in reply to: ↑ 21 Changed 6 months ago by gh-shashwat1002

Replying to lorenz:

Replying to gh-shashwat1002:

  • 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 polynomial-ring classes that do not yet handle the modulus 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 follow-up: Changed 6 months ago by 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 toy-sized inputs), virtually all of the time will be spent on polynomial arithmetic, which is already implemented in low-level 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 git

  • Commit changed from 82931546c7580795b0cfdea2906af5f8d61a91d1 to c37ccc82230f9a45444a7d7e7096c8dbf50c496f

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

c5054adImplement modular exponentiation in polynomial rings Flint.
c37ccc8modular exponentiation using power_mod() in FLINT

comment:25 in reply to: ↑ 23 Changed 6 months ago by gh-shashwat1002

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 toy-sized inputs), virtually all of the time will be spent on polynomial arithmetic, which is already implemented in low-level 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?

Note: See TracTickets for help on using tickets.