Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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:

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?
share|improve this question
    
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

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
Thank you very much :) I got it Accepted ^_^ Although I spent too much reading and analysing but I learned too much things through the way :) thanks for the length-doubling recurrence hint also I didn't know about it as well :) –  user1613396 Aug 22 '12 at 3:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.