Multiplicative order: Difference between revisions
Content added Content deleted
(make this a task) |
(Added Java implementation.) |
||
Line 35: | Line 35: | ||
2 mo _1+10^80x |
2 mo _1+10^80x |
||
190174169488577769580266953193403101748804183400400 |
190174169488577769580266953193403101748804183400400 |
||
=={{header|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; |
|||
} |
Revision as of 02:20, 8 December 2007
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
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; }