MultiplicativeOrder

MultiplicativeOrder[k,n]

gives the multiplicative order of k modulo n, defined as the smallest integer such that .

MultiplicativeOrder[k,n,{r1,r2,}]

gives the generalized multiplicative order of k modulo n, defined as the smallest integer such that for some .

Details

  • MultiplicativeOrder is also known as modulo order or hauptexponent.
  • Integer mathematical function, suitable for both symbolic and numerical manipulation.
  • Typically used in modular arithmetic and cryptography.
  • MultiplicativeOrder[k,n] gives the smallest positive integer m such that the remainder when dividing km by n is equal to 1.
  • MultiplicativeOrder returns unevaluated if there is no integer satisfying the necessary conditions.

Examples

open allclose all

Basic Examples  (2)

The multiplicative order of 5 modulo 8:

Plot the sequence with a fixed modulus:

Plot the sequence, varying the modulus:

Scope  (6)

Numerical Manipulation  (4)

Compute using integers:

Generalized multiplicative order:

Compute using large numbers:

TraditionalForm formatting:

Symbolic Manipulation  (2)

Use Solve to find solutions of equations:

Use FindInstance to find solutions:

Applications  (9)

Basic Applications  (5)

Find all primitive roots modulo 43:

A rational number has a digit cycle of length if is prime and 10 is a primitive root for :

Compute MultiplicativeOrder using NestWhileList:

Count number of possible multiplicative orders modulo a given prime number:

The number of divisors of where is prime:

These are in fact the same list:

Number Theory  (4)

The repetition period in Rule for odd divides q[n]:

The digits of in base repeat with period :

The function digitCycleLength gives the digit period for any rational number in base :

This shows that the decimal representation of in base 10 repeats every 3 digits:

Build an RSA-like toy encryption scheme:

Perform a cycling attack. One of the outputs will be the plaintext:

Properties & Relations  (5)

The multiplicative order of a primitive root modulo n is EulerPhi[n]:

EulerPhi divides MultiplicativeOrder:

The result is always positive:

Find the smallest integer such that 2, 3, or 4 mod 7:

Find which of the remainders satisfies :

Solve the discrete log problem with :

Possible Issues  (1)

For nonzero integers k and n, MultiplicativeOrder[k,n] exists if and only if k and n are coprime:

However, 10 and 22 are not coprime:

Interactive Examples  (1)

MultiplicativeOrder of each integer below a given prime number:

Neat Examples  (2)

Visualize when a number has multiplicative order modulo 12:

Ulam spiral of MultiplicativeOrder:

Introduced in 1999
 (4.0)