2

So I have written a program (see below) to run a series of test cases and for each case determine if X exists for A≡X^2(modM) using Euler's Criterion. It works fine for small test cases, such as when A = 0 and M = 2 or A = 4 and M = 7, but when I consider larger test cases, such as when A = 83715323 and M = 118299443, the program just hangs on line 15 (shown below). Why is this program hanging? Is it a limit of python? Should I perhaps just redo it in something like C++?

The Problem Line

if((A[case]**((M[case] - 1)/2) - 1) % M[case]) == 0:

The Whole Program

number_of_cases = int(raw_input())

A = []
M = []

for case in range(number_of_cases):
    A_M = raw_input().split()
    A.append(int(A_M[0]))
    M.append(int(A_M[1]))

for case in range(number_of_cases):

    solution_exists = 0

    if((A[case]**((M[case] - 1)/2) - 1) % M[case]) == 0:
        print ("YES")
        break        

    else:
        print("NO")
sparky2012
  • 55
  • 1
  • 8
  • 1
    Python can handle large numbers just fine. Question is: can your PC? You'll need enough memory to contain the **huge** integer you are constructing for the `(A[case]**((M[case] - 1)/2) - 1)` expression. 83715323 to the power 59149720 requires 468631695 decimal digits (half a billion, roughly), so Python is asking your OS for just about all your memory. And the *swapping* that causes is what makes your program hang. – Martijn Pieters Apr 07 '15 at 12:04
  • Hmmm, I have 16 gb of RAM and I'm running Fedora, but wholly crap that's big! – sparky2012 Apr 07 '15 at 12:16

2 Answers2

4

The integer calculated by A[case]**((M[case] - 1)/2) - 1) can get very large very quickly. It will take a lot of time and memory to calculate this number using any language.

Instead, take advantage of Python's pow operator and its third argument, which allows for efficient modular exponentiation.

Try changing

if((A[case]**((M[case] - 1)/2) - 1) % M[case]) == 0:

to

if pow(A[case], (M[case] - 1)/2 - 1, M[case]) == 0:

The large number A[case]**((M[case] - 1)/2) - 1) is not calculated here: Python increments the power gradually and keeps track of the remainder modulo M[case] at each step.

Alex Riley
  • 169,130
  • 45
  • 262
  • 238
2

You are performing modular exponentiation.

For that reason, you don't need to calculate A[case]**((M[case] - 1)/2) in one statement. This is likely what is causing your hang.

Use the fact that

x**(n) % m == {(x**(n-1) % m) * x} % m

i.e. you can calculate the remainder of x^n for arbitrarily large n without calculating x^n directly by multiplying then getting the remainder repeatedly.

Try breaking up the exponentiation (see the "Memory-efficient method" section of the wiki article) and seeing if it's still slow.

My bet is that it isn't.

Wai Ha Lee
  • 8,598
  • 83
  • 57
  • 92
  • I wish I could accept this answer as well, but the simplest solution was the one put forward by ajcr. However this solution actually helped me to understand what I was doing and is more efficient. – sparky2012 Apr 07 '15 at 12:15
  • @sparky2012 — thanks for the thought. I would hope that the python implementation of modular exponentiation basically does what I describe - it'd be a bit mad if it didn't. Maybe try both and compare? :) – Wai Ha Lee Apr 07 '15 at 12:17
  • Yeah, going to do that now. – sparky2012 Apr 07 '15 at 12:18
  • Hmm. Just found this on SO: "[*How did Python implement the built-in function pow()?*](http://stackoverflow.com/q/5246856/1364007)" (about modular exponentiation). It seems they basically do the same thing. – Wai Ha Lee Apr 07 '15 at 12:27