galois.log_naive¶

class 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 [566]: N = 17

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

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

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

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

In [571]: N = 18

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

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

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

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