Essays/Multiplicative Order

From J Wiki
Jump to: navigation, search

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.



See also



Contributed by Roger Hui.