Differences between revisions 4 and 5
 ⇤ ← Revision 4 as of 2007-12-09 00:37:37 → Size: 1465 Editor: RogerHui Comment: typo ← Revision 5 as of 2008-12-08 10:45:51 → ⇥ Size: 1443 Editor: anonymous Comment: converted to 1.6 markup Deletions are marked like this. Additions are marked like this. Line 60: Line 60: [[BR]] <
> Line 63: Line 63: * [http://mathworld.wolfram.com/MultiplicativeOrder.html MathWorld] * [[MathWorld:MultiplicativeOrder|MathWorld]] Line 65: Line 65: [[BR]] <
>

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 RogerHui.

Essays/Multiplicative Order (last edited 2008-12-08 10:45:51 by anonymous)