How to calculate modulus of large numbers

Question

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

User · Answer

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;
}

User · Answer

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 - gt  x   2 mod N - gt  x   4 mod - gt      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  gt   0    param y Assumption  y  gt   0    param N Assumption  N  gt  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

User · Answer

What you re looking for is modular exponentiation  specifically modular binary exponentiation  This wikipedia link has pseudocode

User · Answer

Jason s answer in Java  note i  lt  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  lt  exp  i              p    a1          System out println  i   1            p   mod            bse             p   mod    bse    mod     mod     mod           p    p   mod

User · Answer

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

User · Answer

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

User · Answer

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  lt   a1  lt  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  lt   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  lt   p  lt  m and 0  lt   a1  lt  m    As an example  let s compute 5 55 mod 221  First  5 is already reduced mod 221    1   5   5 mod 221 5   5   25 mod 221 25   5   125 mod 221 125   5   183 mod 221 183   5   31 mod 221 31   5   155 mod 221 155   5   112 mod 221 112   5   118 mod 221 118   5   148 mod 221 148   5   77 mod 221 77   5   164 mod 221 164   5   157 mod 221 157   5   122 mod 221 122   5   168 mod 221 168   5   177 mod 221 177   5   1 mod 221 1   5   5 mod 221 5   5   25 mod 221 25   5   125 mod 221 125   5   183 mod 221 183   5   31 mod 221 31   5   155 mod 221 155   5   112 mod 221 112   5   118 mod 221 118   5   148 mod 221 148   5   77 mod 221 77   5   164 mod 221 164   5   157 mod 221 157   5   122 mod 221 122   5   168 mod 221 168   5   177 mod 221 177   5   1 mod 221 1   5   5 mod 221 5   5   25 mod 221 25   5   125 mod 221 125   5   183 mod 221 183   5   31 mod 221 31   5   155 mod 221 155   5   112 mod 221 112   5   118 mod 221 118   5   148 mod 221 148   5   77 mod 221 77   5   164 mod 221 164   5   157 mod 221 157   5   122 mod 221 122   5   168 mod 221 168   5   177 mod 221 177   5   1 mod 221 1   5   5 mod 221 5   5   25 mod 221 25   5   125 mod 221 125   5   183 mod 221 183   5   31 mod 221 31   5   155 mod 221 155   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  gt  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 221        5    5 2  mod 221    125 mod 221     125    5 4  mod 221    112 mod 221  112    5 16  mod 221    112 mod 221    112    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

User · Answer

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  lt  input Length  i                             Calculating the modulus of a large number Wikipedia http   en wikipedia org wiki International Bank Account Number                                                                                     if  i  gt  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

User · Answer

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  lt  sizeof int    8  i              int least sig bit   0x00000001  amp   exp  gt  gt  i           if  least sig bit              x    x   power    mod          power    power   power    mod             return x

User · Answer

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

[math] How to calculate modulus of large numbers?

Examples related to math

Examples related to modulo