How to calculate modulus of large numbers?
MathModuloMath Problem Overview
How to calculate modulus of 5^55 modulus 221 without much use of calculator?
I guess there are some simple principles in number theory in cryptography to calculate such things.
Math Solutions
Solution 1 - Math
Okay, so you want to calculate a^b mod m. First we'll take a naive approach and then see how we can refine it.
First, reduce a mod m. That means, find a number a1 so that 0 <= a1 < m and a = a1 mod m. Then repeatedly in a loop multiply by a1 and reduce again mod m. Thus, in pseudocode:
a1 = a reduced mod m
p = 1
for(int i = 1; i <= b; i++) {
p *= a1
p = p reduced mod m
}
By doing this, we avoid numbers larger than m^2. This is the key. The reason we avoid numbers larger than m^2 is because at every step 0 <= p < m and 0 <= a1 < m.
As an example, let's compute 5^55 mod 221. First, 5 is already reduced mod 221.
1 * 5 = 5 mod 2215 * 5 = 25 mod 22125 * 5 = 125 mod 221125 * 5 = 183 mod 221183 * 5 = 31 mod 22131 * 5 = 155 mod 221155 * 5 = 112 mod 221112 * 5 = 118 mod 221118 * 5 = 148 mod 221148 * 5 = 77 mod 22177 * 5 = 164 mod 221164 * 5 = 157 mod 221157 * 5 = 122 mod 221122 * 5 = 168 mod 221168 * 5 = 177 mod 221177 * 5 = 1 mod 2211 * 5 = 5 mod 2215 * 5 = 25 mod 22125 * 5 = 125 mod 221125 * 5 = 183 mod 221183 * 5 = 31 mod 22131 * 5 = 155 mod 221155 * 5 = 112 mod 221112 * 5 = 118 mod 221118 * 5 = 148 mod 221148 * 5 = 77 mod 22177 * 5 = 164 mod 221164 * 5 = 157 mod 221157 * 5 = 122 mod 221122 * 5 = 168 mod 221168 * 5 = 177 mod 221177 * 5 = 1 mod 2211 * 5 = 5 mod 2215 * 5 = 25 mod 22125 * 5 = 125 mod 221125 * 5 = 183 mod 221183 * 5 = 31 mod 22131 * 5 = 155 mod 221155 * 5 = 112 mod 221112 * 5 = 118 mod 221118 * 5 = 148 mod 221148 * 5 = 77 mod 22177 * 5 = 164 mod 221164 * 5 = 157 mod 221157 * 5 = 122 mod 221122 * 5 = 168 mod 221168 * 5 = 177 mod 221177 * 5 = 1 mod 2211 * 5 = 5 mod 2215 * 5 = 25 mod 22125 * 5 = 125 mod 221125 * 5 = 183 mod 221183 * 5 = 31 mod 22131 * 5 = 155 mod 221155 * 5 = 112 mod 221
Therefore, 5^55 = 112 mod 221.
Now, we can improve this by using exponentiation by squaring; this is the famous trick wherein we reduce exponentiation to requiring only log b multiplications instead of b. Note that with the algorithm that I described above, the exponentiation by squaring improvement, you end up with the right-to-left binary method.
a1 = a reduced mod m
p = 1
while (b > 0) {
if (b is odd) {
p *= a1
p = p reduced mod m
}
b /= 2
a1 = (a1 * a1) reduced mod m
}
Thus, since 55 = 110111 in binary
1 * (5^1 mod 221) = 5 mod 2215 * (5^2 mod 221) = 125 mod 221125 * (5^4 mod 221) = 112 mod 221112 * (5^16 mod 221) = 112 mod 221112 * (5^32 mod 221) = 112 mod 221
Therefore the answer is 5^55 = 112 mod 221. The reason this works is because
55 = 1 + 2 + 4 + 16 + 32
so that
5^55 = 5^(1 + 2 + 4 + 16 + 32) mod 221
= 5^1 * 5^2 * 5^4 * 5^16 * 5^32 mod 221
= 5 * 25 * 183 * 1 * 1 mod 221
= 22875 mod 221
= 112 mod 221
In the step where we calculate 5^1 mod 221, 5^2 mod 221, etc. we note that 5^(2^k) = 5^(2^(k-1)) * 5^(2^(k-1)) because 2^k = 2^(k-1) + 2^(k-1) so that we can first compute 5^1 and reduce mod 221, then square this and reduce mod 221 to obtain 5^2 mod 221, etc.
The above algorithm formalizes this idea.
Solution 2 - Math
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.)
Solution 3 - Math
/* 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;
}
Solution 4 - Math
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
Solution 5 - Math
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.
Solution 6 - Math
What you're looking for is modular exponentiation, specifically modular binary exponentiation. This wikipedia link has pseudocode.
Solution 7 - Math
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);
}
Solution 8 - Math
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);
}
}
Solution 9 - Math
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;
}
Solution 10 - Math
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][1] for found mistake with incorrect return value in case of y and 0 comparison.
[1]: https://stackoverflow.com/users/2410359/chux "@chux"