Essays/Multiplicative Order
< Essays
Jump to navigation
Jump to 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.