Power of large numbers

[TmX]

A friend of mine gave an interesting puzzle:
Calculate (12345678901234567 ^ 76543210987654321) % 115292150460684697

How to solve this programmatically, without using big number libraries?
I'm sure a bit of number theory is involved, but I'm not sure which theorem to use :red

[dedndave]

Horner's Rule
or, as i call it, Ling Long Kai Fang

http://www.masm32.com/board/index.php?topic=12363.msg100575#msg100575

not sure my version can handle that large of a base, though
you might try factoring the base

and - not sure what "% 115292150460684697" means - lol

[Rockoon]

Looks like C code, where % = Mod

[KeepingRealBusy]

It is, it is a standard calculation for RSA encryption (PGP et.al.), raising a number to a power, modulo another number.

[dedndave]

in that case, the base is prime - no factoring, there   :bg

[raymond]

Just Google for Modular Exponentiation. There are a number of interesting articles related to the use of "binary" exponentiation. The PDF file available from the U. of Wyoming at the bottom of the first page should give you a good background.

[TmX]

Apparently, the divide & conquer approach works.

Code Select Expand

#include <stdio.h>

typedef long long LL;

LL _mul(LL,LL,LL);
LL _pow(LL,LL,LL);

int main(){
printf("%lld\n", _pow(12345678901234567LL,76543210987654321LL,115292150460684697LL));
return 0;
}

LL _mul(LL a, LL b, LL m) {
        LL c;

if (b == 0) return 0;
        c = _mul(a, b/2, m);
        c = (c + c) % m;
        if (b % 2 == 1) c = (c + a) % m;
        return c;
}
 
LL _pow(LL a, LL b, LL m) {
LL c;

        if (b == 0) return 1;
c = _pow(a, b/2, m);
        c = _mul(c, c, m);
        if (b % 2 == 1) c = _mul(c, a, m);
        return c;
}


The result is: 96556738226978975

[Twister]

How long did it take for it to come up with that answer? I punched it into python and it's taking it well over 5 minutes to do the job, and it's still going!  :lol

[MichaelW]

Apparently, the divide & conquer approach works.

It does, but it's very slow, ~2,590,000 cycles versus ~33700 for the GMP mpz_powm function.

And the GMP result is the same 96556738226978975.

Edit:

And part of the reason for the slowness is that _pow gets called a total of 57 times, and _mul a total of 4668 times. That still works out at an average of 548 cycles per call, and while that is in line with the counts I'm seeing for the functions without the recursive calls, it still seems high.

[TmX]

How long did it take for it to come up with that answer? I punched it into python and it's taking it well over 5 minutes to do the job, and it's still going!  :lol

Instantly, on my C2D 2 GHz notebook

[TmX]

Apparently, the divide & conquer approach works.

It does, but it's very slow, ~2,590,000 cycles versus ~33700 for the GMP mpz_powm function.

How did you measure the clock cycles?

[MichaelW]

I compiled with a Microsoft compiler and used these macros.

[TmX]

Ah thank you.
This will come in handy later.  :U