lib.grouptheory Module

A collection of various group-theoretic functions.

lib.grouptheory – A collection of group-theoretic functions

lib.grouptheory.multiplicative_order(a, n)

Find the multiplicative order of \(a \mod n\)

Consider the factorisation of \(n = p_1^{e_1} \times p_2^{e_2} \times \dots \times p_k^{e_k}\) and compute the order of \(a \mod p_i^{e_i} \mbox{, } \forall i \in [1, k]\).

This problem can now be solved by applying the Chinese remainder theorem. In particular, by combining the individual results, \(a \mod p_i^{e_i}\), the Chinese remainder theorem gives \(a \mod n\).

Note

while this approach is sound for large \(n\), the use of factorisation and the Chinese remainder theorem is counterproductive for relatively small \(n\). So, for sufficiently small \(n\), a brute force search is used instead.

Parameters:
  • a (int) – the group element
  • n (int) – the multiplicative group modulus
Return type:

int
Returns:

\(ord_n(a)\)
Raises:
  • TypeError – if \(a\) or \(n\) are not int variables
  • ValueError – if \(n \le 0\)
  • ValueError – if \((a,n) \neq 1\)
 
>>> multiplicative_order(10, 99)
2