Modular Multiplicative Inverse &  Modular Exponentiation Equation 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?

 A: 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.
