Multiplicative order: Difference between revisions

Content added Content deleted

Inline

Revision as of 00:56, 8 December 2007

The multiplicative order of x relative to y is the least 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.

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

@@ Line 1: / Line 1: @@
+{{task}}
 The <i>multiplicative order</i> of<tt> x </tt>relative to<tt> y </tt>is
 the least integer<tt> n </tt>such that<tt> x^n </tt>is<tt> 1 </tt>modulo<tt> y</tt> .