galois.log_naive

galois.log_naive(beta, alpha, modulus)

Computes the discrete logarithm \(x = \textrm{log}_{\alpha}(\beta)\ (\textrm{mod}\ m)\).

This function implements the naive algorithm. It is included for testing and reference.

Parameters

  • beta (int) – The integer \(\beta\) to compute the logarithm of.

  • alpha (int) – The base \(\alpha\).

  • modulus (int) – The modulus \(m\).

Examples

In [1]: N = 17

In [2]: galois.totatives(N)
Out[2]: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

In [3]: galois.primitive_roots(N)
Out[3]: [3, 5, 6, 7, 10, 11, 12, 14]

In [4]: x = galois.log_naive(3, 7, N); x
Out[4]: 3

In [5]: 7**x % N
Out[5]: 3

In [6]: N = 18

In [7]: galois.totatives(N)
Out[7]: [1, 5, 7, 11, 13, 17]

In [8]: galois.primitive_roots(N)
Out[8]: [5, 11]

In [9]: x = galois.log_naive(11, 5, N); x
Out[9]: 5

In [10]: 5**x % N
Out[10]: 11