Multiplicative order
You are encouraged to solve this task according to the task description, using any language you may know.
The multiplicative order of a relative to m is the least positive integer n such that a^n is 1 (modulo m). For example, the multiplicative oder of 37 relative to 1000 is 100 because 37^100 is 1 (modulo 1000), and no number smaller than 100 would do. An algorithm can be found in Bach & Shallit, Algorithmic Number Theory, Volume I: Efficient Algorithms, The MIT Press, 1996.
Exercise 5.8, page 115:
Suppose you are given a prime p and a complete factorization of p-1 . Show how to compute the order of an element a in (Z/(p))* using O((lg p)4/(lg lg p)) bit operations.
Solution, page 337:
Let the prime factorization of p-1 be q1e1q2e2...qkek . We use the following observation: if x^((p-1)/qifi) = 1 (mod p) , and fi=ei or x^((p-1)/qifi+1) != 1 (mod p) , then qei-fi||ordp x . (This follows by combining Exercises 5.1 and 2.10.) Hence it suffices to find, for each i , the exponent fi such that the condition above holds.
This can be done as follows: first compute q1e1, q2e2, ... , qkek . This can be done using O((lg p)2) bit operations. Next, compute y1=(p-1)/q1e1, ... , yk=(p-1)/qkek . This can be done using O((lg p)2) bit operations. Now, using the binary method, compute x1=ay1(mod p), ... , xk=ayk(mod p) . This can be done using O(k(lg p)3) bit operations, and k=O((lg p)/(lg lg p)) by Theorem 8.8.10. Finally, for each i , repeatedly raise xi to the qi-th power (mod p) (as many as ei-1 times), checking to see when 1 is obtained. This can be done using O((lg p)3) steps. The total cost is dominated by O(k(lg p)3) , which is O(k(lg p)4/(lg lg p)) .
J
mo=: 4 : 0 a=. x: x m=. x: y assert. 1=a+.m *./ a mopk"1 |: __ q: m )
mopk=: 4 : 0 a=. x: x 'p k'=. x: y pm=. (p^k)&|@^ t=. (p-1)*p^k-1 NB. totient 'q e'=. __ q: t x=. a pm t%q^e d=. (1<x)+x (pm i. 1:)&> (e-1) */\@$&.> q */q^d )
For example:
37 mo 1000 100 2 mo _1+10^80x 190174169488577769580266953193403101748804183400400
Haskell
Assuming a function to calculate prime power factors,
primeFacsExp :: Integer -> [(Integer, Int)]
and another function
powerMod :: (Integral a, Integral b) => a -> a -> b -> a powerMod m _ 0 = 1 powerMod m x n | n > 0 = f x' (n-1) x' where x' = x `rem` m f _ 0 y = y f a d y = g a d where g b i | even i = g (b*b `rem` m) (i `quot` 2) | otherwise = f b (i-1) (b*y `rem` m) powerMod m _ _ = error "powerMod: negative exponent"
to efficiently calculate powers modulo some integral, we get
multOrder a m | gcd a m /= 1 = error "Arguments not coprime" | otherwise = foldl1' lcm $ map (multOrder' a) $ primeFacsExp m multOrder' a (p,k) = r where pk = p^k t = (p-1)*p^(k-1) -- totient \Phi(p^k) r = product $ map find_qd $ primeFacsExp $ t find_qd (q,e) = q^d where x = powerMod pk a (t `div` (q^e)) d = length $ takeWhile (/= 1) $ iterate (\y -> powerMod pk y q) x