unsigned long long overflow with numbers in the range [10^5,10^10]

Question

I've implemented Repeated square-and-multiply algorithm for exponentiation from book "A Handbook of Applied Cryptography (http:// cacr.uwaterloo.ca/hac/about/chap2. pdf - Algorithm 2.143), that calculates the number (a^k) mod n. The range of numbers a, k and n is [10^5,10^10].

The code works, but there are some cases that seems that occurs an overflow, and I do not know why, because 10^10 < 2^63 -1.

One particular case of error: a = 3807869923 ; k = 1735393391 ; n = 6748918117;

The result should be 65 (http://www.wolframalpha.com/input/?i=%283807869923%5E1735393391%29+mod+6748918117), but the code returns 2608265009.

Code:

/*This function calculates (a^k) mod n.
It implements the algorithm 2.143 from book "Handbook of Applied Cryptography", */
{
    int shifts=0;
    unsigned long long b, f;
    b=1;

    if (k == 0) return b;

    //Gets the number of bits of number k
    while ((k >> shifts) != 0) shifts++;

    f = a;

    //Binary shift to extract the value of bit in position 0

    if (((k >> 0) & 1) == 1)
        b = a;


    for (int i=1; i < shifts; i++)
    {
        f = ((f%n)*(f%n)) % n;

        //Binary shift to extract the value of bit in position i

        if (((k >> i) & 1) == 1)
            b = ((f%n)*(b%n)) % n;

    }
    return b;
}

Answer 1

In the following line of code:

f = ((f%n)*(f%n)) % n;

you might multiple n-1 with itself. n can be as large as 10^10, which means (n-1)^2 can be almost 10^20 which overflows 2^63 - 1.

As barak manos pointed out in the comments below you're using "unsigned long long" which means the limit is 2^64-1, not 2^63-1. This doesn't change the problem however.