Least Non-Negative Residue: Large Numbers [closed]

Question

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.

Closed 8 years ago.

I am trying to build a C++ program that can solve the modular congruence:

n^p = x (mod q ),

where n is a small number, and p and q are very large arbitrary primes. I've tried to do this multiple times, but I always run into memory overflow issues. Any help is appreciated.

Answer 1

There is a simple algorithm for b ^ e (mod m):

function powerMod(b, e, m)
    x := 1
    while e > 0
        if e % 2 == 1
            x := (b * x) % m
        b := (b * b) % m
        e := e // 2 # integer division
    return x

You should not calculate b ^ e and then perform the modulo operation, as the intermediate number will be huge. I'll leave it to you to translate to your preferred language with datatypes suitable for storing the large numbers you need. I discuss this algorithm at my blog.

Answer 2

Looking at your comments on your question, it sounds like you are trying to shove very large values into variables that can't hold values that large.

Look here for more information about data types and the ranges they can hold:
http://msdn.microsoft.com/en-us/library/s3f49ktz(v=vs.110).aspx

The largest data type range I found with non negative numbers is unsigned long long. It holds a range of values from 0 to 18,446,744,073,709,551,615.