# N algorithm for calculating the multiplicative order of x modulo y (for y < 1000) that doesn't require a BigInteger type

algorithmdiscrete-mathematicsmath

The algorithm I'm using at the moment runs into extremely high numbers very quickly. A step in the algorithm I'm to raises x to the result of the totient function applied to y. The result is that you can run into very large numbers.

Eg. When calculating the multiplicative order of 10 modulo 53:

``````10^totient(53) == 10^52 == 1 * 10^52
``````

The following algorithm fares a bit better either in terms of avoiding large numbers, but it still fails where 10^mOrder is greater than the capacity of the data type:

``````  mOrder = 1
while 10^mOrder % 53 != 1
if mOrder >= i
mOrder = 0;
break
else
mOrder = mOrder + 1
``````

#### Best Solution

Using Modular exponentiation, it is possible to calculate (10 ^ mOrder % 53) or in general, any (a ^ b mod c) without getting values much bigger than c. See Wikipedia for details, there's this sample code, too:

``````Bignum modpow(Bignum base, Bignum exponent, Bignum modulus) {

Bignum result = 1;

while (exponent > 0) {
if ((exponent & 1) == 1) {
// multiply in this bit's contribution while using modulus to keep result small
result = (result * base) % modulus;
}
// move to the next bit of the exponent, square (and mod) the base accordingly
exponent >>= 1;
base = (base * base) % modulus;
}

return result;
}
``````