0

The all one polynomial modulus is

sum(x**i for i in range(n)) % m

In my case 1 < x < m, 0 < n < m and all are integer. The sum can be simplified to (x**n - 1) / (x - 1). Due to numerical issues integer division needs to be used for larger n. So

(x**n - 1) // (x - 1) % m

is equivalent. Problem is, the power can become quite huge, although Python handles this nicely it gets slow. Python’s 3 argument pow(x,n,m)-function can efficiently calculate powers and modulus in one step, but it’s unclear how to make use of it here. The key is probably a transformation using modulus arithmetics.

Christian
  • 372
  • 3
  • 13
  • `(x**(n+1) - 1) // (x - 1)` is not the equivalent (not the same) to `sum(x**i for i in range(n))` – RomanPerekhrest Feb 22 '23 at 10:05
  • To add to the previous comment: `range(n)` includes integers up to n-1, so it would be `(x**n -1)//(x-1)`. For the rest: see https://stackoverflow.com/questions/1522825/calculating-sum-of-geometric-series-mod-m – Thierry Lathuille Feb 22 '23 at 10:32
  • @ThierryLathuille Are you referring to the selected answer by Jim Lewis or the higher rated answer by braindoper? – Christian Feb 23 '23 at 04:32

0 Answers0