Multiplicative order
Multiplicative order
You are encouraged to solve this task according to the task description, using any language you may know.
You are encouraged to solve this task according to the task description, using any language you may know.
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 118. 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; }