Least Non-Negative Residue: Large Numbers

Question

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.

Maybe. I can check to see if it still decipherable. It will take a sec though because I'm running Windows Server in parallel on a Mac. — Trancot, Jun 11 '13 at 22:17
I say "decipherable" because where the code is stored is but one of many blocks of unrelated code all commented out in main. This is because it is just a test .cpp file, so I have a bunch of commented out programs all in one .cpp file. Does that make sense? — Trancot, Jun 11 '13 at 22:19
Yes it does. It would help if you could simplify as much as possible before presenting here. — suspectus, Jun 11 '13 at 22:21
When I say large number I mean something like 94^1355894606365957843469521488463510701121587912991797864784158488712181744589731257712176047767743727. — Trancot, Jun 11 '13 at 22:21
Damn. It seems as though I overwrote the test.cpp file. The only thing there is an empty function body. — Trancot, Jun 11 '13 at 22:24
Do you not use [version control](http://hginit.com/)? Does your editor not store backups, or editing history? — Peter Wood, Jun 11 '13 at 22:25
yes, although you would likely need a library that would cope with numbers of that size, — suspectus, Jun 11 '13 at 22:26
I have Visual Studio 2012. You are saying there is a way to recover it? How? No, I don't use this "version control" you speak of. — Trancot, Jun 11 '13 at 22:28
@BarisaBarukh integers won't go that big without some help. You need a [Big Number library](http://stackoverflow.com/questions/12988099/big-numbers-library-in-c). — Peter Wood, Jun 11 '13 at 22:29
While I half-suspect that this is a wind-up, some interpretations of it could be solved, in principle. My most immediate question is this: which of n, p, x and q are known, and which do you need the program to find? Without this clarification, calls for source code are probably premature. — aSteve, Jun 11 '13 at 22:34
What is a wind-up? n, p, and q are all known (privately using a some method or broadcast); however, x is not known. I need a way to find this x given these three knowns and the congruence. — Trancot, Jun 11 '13 at 22:35
What about these people's [ideas](http://stackoverflow.com/questions/2708851/what-is-an-efficient-way-to-get-the-least-non-negative-residue-modulo-n-in-c)? — Trancot, Jun 11 '13 at 22:40
Just as and aside, does anybody here know of a decent random character scrambler? — Trancot, Jun 11 '13 at 22:46
A wind-up is a 'silly question' asked because it has no good answers. Finding x is easy - it is (n*p)%q - but you need to evaluate that with a suitable data-type. I recommend reading this: http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic There are suitable libraries for C/C++ but none are "easy" to use. You can do this in one line of Python. — aSteve, Jun 11 '13 at 22:47
OK, so I know that n can be at most a certain integer, say e, so then I must ensure that e*p<=18,446,744,073,709,551,615, right? — Trancot, Jun 11 '13 at 22:49
This just all smells like OP is fishing for somebody to do the work for him — Joe Runde, Jun 11 '13 at 22:57
@MrBarukh, in that case, use GMP or MPIR http://www.mpir.org/ (or an alternative of your choice) and evaluate (n*p)%q. If only x is unknown, your only difficulty is that C++ has no native support for "large" integers. — aSteve, Jun 11 '13 at 23:01
@MrBarukh (P.S. Sorry, I had misread n^p as n*p - my mistake.) — aSteve, Jun 12 '13 at 08:32

score 2 · Accepted Answer · answered Jun 11 '13 at 23:04

2

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.

answered Jun 11 '13 at 23:04

user448810

17,381
4
34
59

What do you mean by `e := e // 2 # integer division`? – Trancot Jun 12 '13 at 01:53
unsigned long long powerMod( unsigned long long b , unsigned long long e , unsigned long long m ) { int x = 1; while( e > 0 ) { if( e % 2 == 1 ) { x = ( b*x ) % m; } b = ( b*b) % m; e = e – Trancot Jun 12 '13 at 01:53
This will run for quite some time won't it? – Trancot Jun 12 '13 at 01:56
Integer division ignores remainders; thus e // 2 (where the double-slash indicates integer division) is the same as floor(e / 2). The runtime is O(log2 e), which is quite fast. See the Wikipedia page for Modular Exponentiation for details. – user448810 Jun 12 '13 at 03:57

score 1 · Answer 2 · answered Jun 11 '13 at 22:34

1

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.

answered Jun 11 '13 at 22:34

Doug

78
7

Will that number be the same on my system though? – Trancot Jun 11 '13 at 22:36
This is the maximum value for an unsigned 64bit integer. (0xffffffffffffffff) which equals 18,446,744,073,709,551,615. Those values are true on Visual Studio 2012. So to answer your question, you will not be able to use big numbers like you want to without help from a library of some sort like the Big Number Library that Peter Wood mentioned in the comment section to your question post. If using that solves your problem, please make sure to upvote his comment. – Doug Jun 11 '13 at 22:40
Did you see Peter Wood's comment? – Trancot Jun 11 '13 at 22:41

Least Non-Negative Residue: Large Numbers

2 Answers2