Multiplicative order

Multiplicative order
You are encouraged to solve this task according to the task description, using any language you may know.

This task has been flagged for clarification. Code on this page in its current state may be flagged incorrect once this task has been clarified. See this page's Talk page for discussion.

The multiplicative order of x relative to y is the least positive integer n such that x^n is 1 modulo y . For example, 37 mo 1000 is 100 because 37^100 is 1 modulo 1000 (and no number smaller than 100 would do). Note that the multiplicative order is undefined if x and y are not relatively prime.

There is an algorithm in Bach & Shallit, Algorithmic Number Theory I, exercise 5.8, page 115. A naive algorithm can require more than the age of the universe to produce an answer for large arguments.

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

Java

public BigInteger mo(BigInteger x, BigInteger y){
  BigInteger retVal = BigInteger.ZERO;
  for(;x.modPow(retVal, y) != BigInteger.ONE;retVal = retVal.add(BigInteger.ONE));
  return retVal;
}