Sum of series: a^0+2a^1 + 3*a^2 + 4*a^3 + … + n*a^(n-1) (mod M)

Question

Can someone give me an idea of an efficient algorithm for large n which perform O(log(n)) using recursive function not geometric summation formula.

Answer 1

You need to use the formula for sum of geometric progression: a^1 + a^2 + ... a^n = (a^(n+1) - 1) / (a - 1). Using exponentiation by squaring you can compute (a^(n+1) - 1) in O(log(n)). If M is prime dividing by (a - 1) is simply one more exponentiation - for any U coprime with a prime number p, U^(-1) (mod p) = U^(p-2) (mod p). You can prove this using Fermat's little theorem.