Project Euler Problem #97

Problem #97 concerns finding the last ten digits of a large Mersenne Prime. The question reads:

Project Euler Problem 97: Large non-Mersenne prime
The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form 26972593−1; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2p−1, have been found which contain more digits.
However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 28433×27830457+1.
Find the last ten digits of this prime number.

My solution for this problem involves a famous algorithm known as the Exponentiation by squaring or square and multiply algorithm. Here is my solution:

Solution #1: Square and Multiply Approach

The problem is equivalent to finding the remainder when the given number is divided by 10^10. Clearly, it will leave a remainder of 1 when divided by 2^10. Thus, it suffices to find the remainder when it is divided by 5^10, as afterwards the Chinese Remainder Theorem (CRT) can be used to find a corresponding remainder mod 10^10. The Exponentiation by squaring algorithm allows us to find this remainder quickly. First, the exponent 7830457 is written in binary. (11101110111101110111001). This binary representation tells us which powers of 2 can be added to get the given exponent. With the well known fact that 2^a * 2^b = 2^(a+b), it follows that if we can find the remainder when powers of the form 2^(2^n) are divided by 5^10, we can multiply those powers according to the binary representation to get the remainder when 2^7830457 is divided by 5^10. Finally, we can multiply the result by 28433 and add 1 to get the remainder when the Mersenne Prime is divided by 5^10, and afterwards CRT can be used to get the last 10 digits. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Square and Multiply Approach to Project Euler Problem #97
 '''
 
 import time
 
 def squareAndMultiply(b,e,m):
     l = bin(e)[2:]
     a = len(l)
     exponents = []
     myExponent = b
     while(len(exponents)<a):
         exponents.append(myExponent)
         myExponent = (myExponent**2)%m
     total = 1
     c = l[::-1]
     for x in range(a):
         if(c[x] == '1'):
             total*=exponents[x]
             total%=m
     return total
 
 def projectEulerProblemNinetySeven(a,b,e,c,m):
     return (a*squareAndMultiply(b, e, m) + c)%m
 
 start = time.time()
 print projectEulerProblemNinetySeven(28433, 2, 7830457, 1, 10**10)
 print ("--- %s seconds ---" % (time.time()-start))
 
 print bin(7830457)
 
 '''
 Prints
 
 8739992577
 --- 5.29289245605e-05 seconds ---
 
 for input of a = 28433, b = 2, e = 7830457, c = 1, m = 10**10
 ''' 

And with that, we’re done. The Square and Multiply approach is very common in computer science, so I may reuse this code in other problems.

Thanks for reading! See you tomorrow.