Is there an algorithm for calculating the multiplicative order of x modulo y (for y < 1000) that doesn't require a BigInteger type?
-
22-07-2019 - |
Question
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
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;
}
OTHER TIPS
Why exponentiate? Can't you just multiply modulo n in a loop?
(defun multiplicative-order (a n) (if (> (gcd a n) 1) 0 (do ((order 1 (+ order 1)) (mod-exp (mod a n) (mod (* mod-exp a) n))) ((= mod-exp 1) order))))
Or, in ptheudo (sic) code:
def multiplicative_order (a, n) :
if gcd (a, n) > 1 :
return 0
else:
order = 1
mod_exp = a mod n
while mod_exp != 1 :
order += 1
mod_exp = (mod_exp * a) mod n
return order