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")
Improve this question
2
  • 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. Commented Apr 7, 2015 at 12:04
  • Hmmm, I have 16 gb of RAM and I'm running Fedora, but wholly crap that's big! Commented Apr 7, 2015 at 12:16

2 Answers 2

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

I beat you by nine seconds, but your knowledge of python trumps my speediness. +1
but you also identified the problem and gave the useful wiki link :-)
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.

Improve this answer

4 Comments

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 — 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? :)
Yeah, going to do that now.
Hmm. Just found this on SO: "How did Python implement the built-in function pow()?" (about modular exponentiation). It seems they basically do the same thing.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.