Multiplicative order: Difference between revisions
Content added Content deleted
(Added Java implementation.) |
(Requested clarification) |
||
Line 1: | Line 1: | ||
{{task}} |
{{task}} |
||
{{Template:clarify task}} |
|||
The <i>multiplicative order</i> of<tt> x </tt>relative to<tt> y </tt>is |
The <i>multiplicative order</i> of<tt> x </tt>relative to<tt> y </tt>is |
Revision as of 10:57, 8 December 2007
Multiplicative order
You are encouraged to solve this task according to the task description, using any language you may know.
You are encouraged to solve this task according to the task description, using any language you may know.
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
Java
public BigInteger mo(BigInteger x, BigInteger y){ BigInteger retVal = BigInteger.ZERO; for(;x.modPow(retVal, y) != BigInteger.ONE;retVal = retVal.add(BigInteger.ONE); return retVal; }