The multiplicative order of x relative to y is the least integer n  such that 1=y|x^n . The following functions for the multiplicative order implement the algorithm described in Bach & Shallit, Algorithmic Number Theory I, exercise 5.8, page 115.

```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:

```   1+1 i.~ 1000|37^>:i.1000x
100
1000|37^100x
1
37 mo 1000
100

2 mo _1+10^80x
190174169488577769580266953193403101748804183400400```

We use the multiplicative order to find the last 20 decimal digits of the number 37^41^43^5000x :

```m|37^41^43^5000x [ m=: 10^20x
37 (m&|@^) 41^43^5000x
37 (m&|@^) (37 mo m)|41^43^5000x
37 (m&|@^) 41 (37 mo m)&|@^ 43^5000x
37 (m&|@^) 41 (37 mo m)&|@^ (41 mo 37 mo m)|43^5000x
37 (m&|@^) 41 (37 mo m)&|@^ 43 (41 mo 37 mo m)&|@^ 5000x
16242726546587103237```

The first 3 phrases can not be computed directly; the others can, with the penultimate phrase taking less than 1 second on a 500 Mhz Pentium 3.