# Multiplicative order Mord(a, n)

Mord(a, n) = Multiplicative order of base a (mod n) or 0.

See: Multiplicative Order -- From MathWorld
And: Wolfram Mathematica Documentation -- MultiplicativeOrder

Here are some notes from my program XICalc - Extra Precision Integer Calculator http://www.oocities.org/hjsmithh/download.html#XICalc :

The multiplicative order function Mord(a, n) is the minimum positive integer e for which a^e == 1 mod n, or zero if no e exists. If a or n is less than 2, zero is returned.

```e = Mord(a, n) // e = Multiplicative order
// multiplicative order of base a (mod n) or zero if it does not exist. From Henri Cohen's book,
// A Course in Computational Algebraic Number Theory, Springer, 1996, Algorithm 1.4.3, page 25.
{
e = 0
if (a <= 1 or n <= 1) return;
if (GCD(a, n) != 1) return;
h = Phi(n); // Euler's Totient Function
factor h by ECM (Elliptic Curve Method)
// h = Prod(pi^vi) i = 1, ..., k
e = h;
for (int i = 1; i <= k; i++)
{
e = e / pi^vi;
g1 = a^e mod n
while (g1 != 1)
{
g1 = g1^pi mod n
e = e * pi
}
}
}
```
This page accessed times since Feb 17, 2006.