Raising large number to large power and mod it by a large number?

Question

I am stuck with probably simple question. I got 3 large numbers(A,B,C), all integers and i need to do the following: power A to B and modulo the result by C, and then check if the result is equal to 1. Here's my code:

double power = fmod((pow((double)A,(double)B)),(double)C);
    if (power != 1){
        printf("Something!\n");
    }

And it doesnt work(I tried small numbers, like 17 powered by 28 and moduled by 29). Any suggestions on that?

possible duplicate of [finding a^b^c^... mod m](http://stackoverflow.com/questions/4223313/finding-abc-mod-m) — phuclv, Nov 26 '14 at 16:24
@UmNyobe Potentially they can be up to millions,I try to build my implementation of Lucas primality test(not Lucas-Lehmer),and one of the operation is powering number between 0 and N by N-1 and moduling the result — Z1kkurat, Nov 26 '14 at 16:53
possible duplicate of [Optimized way to handle extremely large number without using external library](http://stackoverflow.com/questions/16662430/optimized-way-to-handle-extremely-large-number-without-using-external-library) — Marcin Orlowski, Nov 26 '14 at 18:43

barak manos · Accepted Answer · 2014-11-26T16:58:30.870

0

Try this (in order to avoid arithmetic overflow):

unsigned long long power = 1;
A %= C;
while (B > 0)
{
    power = (power * A) % C;
    B--;
}

You can further improve the runtime performance with this:

unsigned long long power = 1;
A %= C;
while (B > 0)
{
    if (B & 1)
        power = (power * A) % C;
    B >>= 1;
    A = (A * A) % C;
}

edited Nov 26 '14 at 16:58

answered Nov 26 '14 at 16:48

barak manos

29,648
10
62
114

This works if A, B and C is int and unsigned long long is twice as large as int. But we don't know how large are those numbers and what type are they – phuclv Nov 26 '14 at 16:56
@LưuVĩnhPhúc: Correct, but the question implies nothing about the maximum values of the input arguments (`A`, `B` and `C`), so I did my best with the given information... – barak manos Nov 26 '14 at 17:01
yeah, but actually it was answer in many other questions before and this is just a duplicate – phuclv Nov 26 '14 at 17:04
@LưuVĩnhPhúc actually they can be up to millons or even billions, as I try to build my implementation of Lucas primality test(not Lucas-Lehmer),and one of the operation is powering number between 0 and N by N-1 and moduling the result. – Z1kkurat Nov 26 '14 at 17:15

Rafael · Answer 2 · 2014-11-26T16:42:37.463

-1

try this approach

double a,b,c;

a = 1124124124254234;
b = 1124124124254234 * 5;
c = 1124124124254234 * 2;

double power = pow(a,b); 

double mod = fmod(power, c);

if (mod != 1){
    printf("Something!\n");
}

edited Nov 26 '14 at 16:42

answered Nov 26 '14 at 16:21

Rafael

7,605
13
31
46

as above, `%` doesn't work with integer types and the result is not correct due to the limited precision of double – phuclv Nov 26 '14 at 16:38
@LưuVĩnhPhúc `%` only works with integer, it doesn't work with double. – mch Nov 26 '14 at 16:42

score -1 · Answer 3 · answered Nov 26 '14 at 16:27

-1

The min and max sizes for Double are -1.7*10^308 and 1.7*10^308 respectively. If you need bigger you could try long long.

Not sure why you are using fmod. But this should do what you want.

double power = ( pow(A, B) ) % C;
if (power != 1){
        printf("Something!\n");
    }

answered Nov 26 '14 at 16:27

Jacobr365

846
11
24

1

`%` doesn't work with integer types. Besides, it's not correct because double is only accurate to the first few digits – phuclv Nov 26 '14 at 16:38
Works on my computer just fine using his 17, 28, 29 example. I get 1 for that example which is correct according to WolfRamAlpha. – Jacobr365 Nov 26 '14 at 16:44
1

It works by pure luck. Besides, it returns 12 on my computer if I cast the result of pow to unsigned long long, and 0 if I cast to unsigned int. 17^28 needs approximately 114.449 bits and definitely double cannot have that large precision in current machines – phuclv Nov 26 '14 at 16:50

Raising large number to large power and mod it by a large number?

3 Answers3

Linked