Title: Optional modulus argument for new function
Type: performance Stage:
Components: Library (Lib) Versions: Python 3.8
Status: open Resolution:
Dependencies: Superseder:
Assigned To: Nosy List: josh.r, lschoe, mark.dickinson, rhettinger, tim.peters
Priority: normal Keywords:

Created on 2019-02-14 19:34 by lschoe, last changed 2019-05-12 10:39 by mark.dickinson.

Messages (7)
msg335557 - (view) Author: Berry Schoenmakers (lschoe) Date: 2019-02-14 19:34
It's nice to see the arrival of the prod() function, see PR11359.

Just as for the built-in pow(x, y[, z]) function it would be very useful to have an optional argument z for computing integer products modulo z. Typical use case in cryptography would be:

prod((pow(x, y, z) for x, y in zip(g, s)), z)

to compute the product of all (potentially many) g[i]**s[i]'s modulo z. 

And, just as with the use of pow(), the intermediate values for prod() may in general grow quickly, hence modular reduction is essential to limit time and space usage.

Maybe an interesting option to add at this stage?
msg335578 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2019-02-15 03:12
I don't think even Mathematica has found a need for this:
msg335579 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2019-02-15 03:30
One other issue is that the arguments to prod() need not be integers, so a modulus argument wouldn't make sense in those contexts.
msg335580 - (view) Author: Josh Rosenberg (josh.r) * (Python triager) Date: 2019-02-15 04:47
"One other issue is that the arguments to prod() need not be integers, so a modulus argument wouldn't make sense in those contexts."

The arguments to pow don't need to be integers either, yet the optional third argument is only really relevant to integers.

Not saying we should do this, but we definitely allow optional arguments that are only meaningful for certain input types in other cases.

The best argument for this change I can come up with from other Python functions is the push for an efficient math.comb (#35431); if we didn't want to bother supporting minimizing intermediate values, math.comb could be implemented directly in terms of math.factorial instead of trying to pre-cancel values. But even that's not a strong argument for this, given the relative frequency with which each feature is needed (the binomial coefficient coming up much more often than modular reduction of huge products).
msg335581 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2019-02-15 04:59
Put me down for -1.  In 40 years of programming, I've needed a modulus on a product exactly zero times.
msg335589 - (view) Author: Berry Schoenmakers (lschoe) Date: 2019-02-15 08:26
I had the same reservations but after rethinking it several times concluded that the modulus argument would fit really well.

Indeed, Mathematica doesn't support the Modulus option for the Product[] function. But they don't even support it for the Power[] function, one needs to use PowerMod[] for that. 

Python has the extra option for its built-in pow(), and sensibly restricts this to the case of integer arguments only. 

To do modular arithmetic, even with big numbers, in Python is really nice and easy using the % operator. And it's all pretty efficient as well. The only exception where efficiency becomes an issue is the pow() function.

To maintain that balance with the new prod() function around, the modulus argument would do the job. We can continue to do all modular arithmetic in a natural way, yielding programs that are perfectly readable and with very decent performance, now with prod() in the language as well.

Taking larger modular products is a common thing to do in modern crypto, and Python is a popular platform for this. Next to the example of prod_i g[i]**s[i] mod z, which is like a Pedersen multi-commitment, it also arises when computing Lagrange coefficients (used in Shamir secret sharing) and related determinants for Vandermonde matrices.

One would also be able to things like prod(range(1, n), n) == n - 1 for Wilson's primality test. (Extending the factorial() function with a modulus argument would be taking things too far, probably, but the modular version would now be available anyway via prod().)

So, my feeling is that there are sufficiently many use cases around. And, I'm kind of assuming that it's not too much effort to add a modulus argument to prod(), but maybe that's not really the case.
msg342252 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2019-05-12 10:39
Put me down for a -1, too.

> One would also be able to things like prod(range(1, n), n) == n - 1 for Wilson's primality test.

That's not the most convincing use-case, since that's a _horribly_ inefficient way to do a primality test in the first place (worse than trial division, even if you take that trial division all the way up to `n - 1` instead of the square root of `n`).
Date User Action Args
2019-05-12 10:39:28mark.dickinsonsetmessages: + msg342252
2019-02-15 21:37:32rhettingersetnosy: + tim.peters
2019-02-15 16:31:43mark.dickinsonsetnosy: + mark.dickinson
2019-02-15 08:26:12lschoesetmessages: + msg335589
2019-02-15 04:59:06rhettingersetmessages: + msg335581
2019-02-15 04:47:39josh.rsetnosy: + josh.r
messages: + msg335580
2019-02-15 03:30:04rhettingersetmessages: + msg335579
2019-02-15 03:12:40rhettingersetmessages: + msg335578
2019-02-14 19:34:36lschoecreate