# 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?
-
Looks like you also need to wish that $a-1$ and $m$ are also coprime. If not, then there will be more work. – Jyrki Lahtonen Aug 21 '12 at 8:16
@JyrkiLahtonen Yes, It's this more work that I don't have any idea about :D because the input is variable so I need a generic solution – user1613396 Aug 21 '12 at 8:19

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)?