Mod power or totient logic issue

Question

Here is some code I adapted that deals with the euler totient function and a power mod function. Every n, f2 is always 3 instead of a variety of numbers. Does anyone see an error? phi(n) and modpow(n) both seem to work fine.

#include <iostream>
using namespace std;

int gcd(int a, int b)
{
    while (b != 0)
    {
        int c = a % b;
        a = b;
        b = c;
    }
    return a;
}

int phi(int n)
{
    int x = 0;
    for (int i=1; i<=n; i++)
    {
        if (gcd(n, i) == 1)
            x++;
    }
    return x;
}

int modpow(int base, int exp, int mod) // from stackoverflow
{
    base %= mod;
    long long result = 1;
    while (exp > 0)
    {
        if (exp & 1)
            result = (result * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}

int f2(int n) // f(f(n)) mod n
{
    long long a = modpow(2, n, phi(n)) + 1;
    return (modpow(2, a, n) + 1) % n;
}

// ...

int main()
{
    int n = 520001;
    while (true)
    {
        cout << "f2 " << f2(n) << endl;
        if (f2(n) == 0)
        {
            // ...
        }

        n += 2;
    }
    return 0;
}

Values of f2(n) should be 9, 458278, 379578, ...

Answer 1

base*base will exceed the size of an int if base >= 65536. Try this fix, seems to work:

int modpow(int base, int exp, int mod) // from stackoverflow
{
    base %= mod;
    long long result = 1;
    while (exp > 0)
    {
        if (exp & 1)
            result = (result * base) % mod;
        base = (int)(((long long)base * (long long)base) % mod);
        exp >>= 1;
    }
    return (int) result;
}