Jason's answer in Java (note i < exp).
private static void testModulus() {
int bse = 5, exp = 55, mod = 221;
int a1 = bse % mod;
int p = 1;
System.out.println("1. " + (p % mod) + " * " + bse + " = " + (p % mod) * bse + " mod " + mod);
for (int i = 1; i < exp; i++) {
p *= a1;
System.out.println((i + 1) + ". " + (p % mod) + " * " + bse + " = " + ((p % mod) * bse) % mod + " mod " + mod);
p = (p % mod);
}
}
5^55 mod221
= ( 5^10 * 5^10 * 5^10 * 5^10 * 5^10 * 5^5) mod221
= ( ( 5^10) mod221 * 5^10 * 5^10 * 5^10 * 5^10 * 5^5) mod221
= ( 77 * 5^10 * 5^10 * 5^10 * 5^10 * 5^5) mod221
= ( ( 77 * 5^10) mod221 * 5^10 * 5^10 * 5^10 * 5^5) mod221
= ( 183 * 5^10 * 5^10 * 5^10 * 5^5) mod221
= ( ( 183 * 5^10) mod221 * 5^10 * 5^10 * 5^5) mod221
= ( 168 * 5^10 * 5^10 * 5^5) mod221
= ( ( 168 * 5^10) mod 221 * 5^10 * 5^5) mod221
= ( 118 * 5^10 * 5^5) mod221
= ( ( 118 * 5^10) mod 221 * 5^5) mod221
= ( 25 * 5^5) mod221
= 112
Chinese Remainder Theorem comes to mind as an initial point as 221 = 13 * 17. So, break this down into 2 parts that get combined in the end, one for mod 13 and one for mod 17. Second, I believe there is some proof of a^(p-1) = 1 mod p for all non zero a which also helps reduce your problem as 5^55 becomes 5^3 for the mod 13 case as 13*4=52. If you look under the subject of "Finite Fields" you may find some good results on how to solve this.
EDIT: The reason I mention the factors is that this creates a way to factor zero into non-zero elements as if you tried something like 13^2 * 17^4 mod 221, the answer is zero since 13*17=221. A lot of large numbers aren't going to be prime, though there are ways to find large primes as they are used a lot in cryptography and other areas within Mathematics.
This is called modular exponentiation(https://en.wikipedia.org/wiki/Modular_exponentiation).
Let's assume you have the following expression:
19 ^ 3 mod 7
Instead of powering 19 directly you can do the following:
(((19 mod 7) * 19) mod 7) * 19) mod 7
But this can take also a long time due to a lot of sequential multipliations and so you can multiply on squared values:
x mod N -> x ^ 2 mod N -> x ^ 4 mod -> ... x ^ 2 |log y| mod N
Modular exponentiation algorithm makes assumptions that:
x ^ y == (x ^ |y/2|) ^ 2 if y is even
x ^ y == x * ((x ^ |y/2|) ^ 2) if y is odd
And so recursive modular exponentiation algorithm will look like this in java:
/**
* Modular exponentiation algorithm
* @param x Assumption: x >= 0
* @param y Assumption: y >= 0
* @param N Assumption: N > 0
* @return x ^ y mod N
*/
public static long modExp(long x, long y, long N) {
if(y == 0)
return 1 % N;
long z = modExp(x, Math.abs(y/2), N);
if(y % 2 == 0)
return (long) ((Math.pow(z, 2)) % N);
return (long) ((x * Math.pow(z, 2)) % N);
}
Special thanks to @chux for found mistake with incorrect return value in case of y and 0 comparison.
Just provide another implementation of Jason's answer by C.
After discussing with my classmates, based on Jason's explanation, I like the recursive version more if you don't care about the performance very much:
For example:
#include<stdio.h>
int mypow( int base, int pow, int mod ){
if( pow == 0 ) return 1;
if( pow % 2 == 0 ){
int tmp = mypow( base, pow >> 1, mod );
return tmp * tmp % mod;
}
else{
return base * mypow( base, pow - 1, mod ) % mod;
}
}
int main(){
printf("%d", mypow(5,55,221));
return 0;
}
This is part of code I made for IBAN validation. Feel free to use.
static void Main(string[] args)
{
int modulo = 97;
string input = Reverse("100020778788920323232343433");
int result = 0;
int lastRowValue = 1;
for (int i = 0; i < input.Length; i++)
{
// Calculating the modulus of a large number Wikipedia http://en.wikipedia.org/wiki/International_Bank_Account_Number
if (i > 0)
{
lastRowValue = ModuloByDigits(lastRowValue, modulo);
}
result += lastRowValue * int.Parse(input[i].ToString());
}
result = result % modulo;
Console.WriteLine(string.Format("Result: {0}", result));
}
public static int ModuloByDigits(int previousValue, int modulo)
{
// Calculating the modulus of a large number Wikipedia http://en.wikipedia.org/wiki/International_Bank_Account_Number
return ((previousValue * 10) % modulo);
}
public static string Reverse(string input)
{
char[] arr = input.ToCharArray();
Array.Reverse(arr);
return new string(arr);
}
To add to Jason's answer:
You can speed the process up (which might be helpful for very large exponents) using the binary expansion of the exponent. First calculate 5, 5^2, 5^4, 5^8 mod 221 - you do this by repeated squaring:
5^1 = 5(mod 221)
5^2 = 5^2 (mod 221) = 25(mod 221)
5^4 = (5^2)^2 = 25^2(mod 221) = 625 (mod 221) = 183(mod221)
5^8 = (5^4)^2 = 183^2(mod 221) = 33489 (mod 221) = 118(mod 221)
5^16 = (5^8)^2 = 118^2(mod 221) = 13924 (mod 221) = 1(mod 221)
5^32 = (5^16)^2 = 1^2(mod 221) = 1(mod 221)
Now we can write
55 = 1 + 2 + 4 + 16 + 32
so 5^55 = 5^1 * 5^2 * 5^4 * 5^16 * 5^32
= 5 * 25 * 625 * 1 * 1 (mod 221)
= 125 * 625 (mod 221)
= 125 * 183 (mod 183) - because 625 = 183 (mod 221)
= 22875 ( mod 221)
= 112 (mod 221)
You can see how for very large exponents this will be much faster (I believe it's log as opposed to linear in b, but not certain.)
/* The algorithm is from the book "Discrete Mathematics and Its
Applications 5th Edition" by Kenneth H. Rosen.
(base^exp)%mod
*/
int modular(int base, unsigned int exp, unsigned int mod)
{
int x = 1;
int power = base % mod;
for (int i = 0; i < sizeof(int) * 8; i++) {
int least_sig_bit = 0x00000001 & (exp >> i);
if (least_sig_bit)
x = (x * power) % mod;
power = (power * power) % mod;
}
return x;
}
What you're looking for is modular exponentiation, specifically modular binary exponentiation. This wikipedia link has pseudocode.
Source: Stackoverflow.com