I was solving a problem containing that equation.
$$key=(\sum_{K=0}^n\frac{1}{a^K})\mod m$$
Given:
- $1 \le a \le 2,000,000,000$
- $0 \le n \le 2,000,000,000$
- $2 \le m \le 2,000,000,000$
- $a$ and $m$ are coprime
My Approach:
To Solve the SECOND part
- Using Geometric Sequence sum I transfered the equation to this form
- I Used Euclid's Extended Algorithm to get the Modular Multiplicative Inverse of "$a$"
- then I used Modular Exponentiation to calculate its modulus to "$m$"
Question:
- What about the first part? how would I calculate it given the problem limits?
Best Answer
If $\gcd(a-1,m)=1$, then there will be no problems using the sum formula for a geometric series. Otherwise I suggest the following that is kind of like the square-and-multiply approach to modular exponentiation.
Write $q=1/a$ (= the modular inverse of $a$) and denote the geometric sum by $$ S(k)=\sum_{i=0}^{k-1} q^i.\qquad\text{<- Edit: A typo here. The upper bound was off by one.} $$ Then we have the length-doubling recurrence relation (all arithmetic done modulo $m$, so if you are so minded, imagine $\%m$ at the end of each addition or product - I prefer to think of this as doing arithmetic in the ring $\mathbb{Z}/m\mathbb{Z}$): $$ S(2k)=S(k)(1+q^k), $$ as well as the add-one recurrence: $$ S(k+1)=q S(k) +1. $$
With the aid of these you can follow the usual square-and-multiply (or rather, double-and-add) logic. So for example to calculate $S(113)$ you need to first calculate $S(112)$ and then apply the add-one -formula. To calculate $S(112)$ you first calculate $S(56)$, and then apply the length-doubling -formula. Apply these ideas recursively.
The complexity looks like to be of the order $O\left((\log_2n)^2\right)$ modular multiplications given that you need to compute all those $q^k$:s for the length doubling formula. It does look like, there is a lot of redundancy there (in that the $q^k$ you will need in the next recursive call has probably already been computed). I'm sure you can build a more efficient recursive procedure from these elements, as it is possible to predetermine exactly which powers $q^k$ are needed! May be what you end up with has linear complexity (in terms of the number of bits in $n$ using the cost of a modular multiplication as a unit)?
Some further shaving may be possible by reorganizing the calculation further.