Multiplicative order: Difference between revisions
Content added Content deleted
(Requested clarification) |
(added clarification) |
||
Line 6: | Line 6: | ||
For example,<tt> 37 mo 1000 </tt>is<tt> 100 </tt>because<tt> 37^100 </tt>is<tt> 1 </tt> |
For example,<tt> 37 mo 1000 </tt>is<tt> 100 </tt>because<tt> 37^100 </tt>is<tt> 1 </tt> |
||
modulo<tt> 1000 </tt>(and no number smaller than 100 would do). |
modulo<tt> 1000 </tt>(and no number smaller than 100 would do). |
||
Note that the multiplicative order is undefined if<tt> x </tt>and<tt> y </tt> |
Note that the multiplicative order is undefined if<tt> x </tt>and<tt> y </tt> |
||
are not relatively prime. |
are not relatively prime. |
||
There is an algorithm in Bach & Shallit, <i>Algorithmic Number Theory I</i>, exercise 5.8, page 118. |
|||
A naive algorithm can require more than the age of the universe to produce an answer |
|||
for large arguments. |
|||
=={{header|J}}== |
=={{header|J}}== |
Revision as of 15:31, 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.
There is an algorithm in Bach & Shallit, Algorithmic Number Theory I, exercise 5.8, page 118. A naive algorithm can require more than the age of the universe to produce an answer for large arguments.
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; }