CryptoBook
  • CryptoBook
  • Book Plan
  • Style Guide
    • Sample Page
  • Contributors
  • Fundamentals
    • Mathematical Notation
    • Division and Greatest common divisor
      • Euclidean Algorithm
    • Modular Arithmetic
      • Theorems of Wilson, Euler, and Fermat
        • Fermat's Little Theorem in Detail
        • Euler's Theorem in Detail
      • Quadratic Residues
    • Continued Fractions
  • Number Theory
  • Ideals
  • Polynomials With Shared Roots
  • Integer Factorization
    • Pollard rho
    • Sieves
  • Abstract algebra
    • Groups
      • Another take on groups
      • Discrete Log Problem
    • Rings
    • Fields
    • Polynomials
  • Elliptic Curves
    • Untitled
  • Lattices
    • Introduction
    • LLL reduction
      • Gram-Schmidt Orthogonalization
      • Lagrange's algorithm
      • LLL reduction
    • Lattice reduction
      • Minkowski reduced
      • HKZ reduced
      • LLL reduced
    • Applications
      • Coppersmith algorithm
      • Extensions of Coppersmith algorithm
    • Hard lattice problems
    • Lattices of interest
    • Cryptographic lattice problems
      • Short integer solutions (SIS)
      • Learning with errors (LWE)
      • Ring-LWE
      • NTRU
    • Interactive fun
    • Resources and notations
  • Asymmetric Cryptography
  • RSA
    • Proof of correctness
    • RSA application
    • Low Private Component Attacks
      • Wiener's Attack
      • Boneh-Durfee Attack
    • Common Modulus Attack
    • Recovering the Modulus
  • Diffie-Hellman
    • MITM
  • Elliptic Curve Cryptography
  • Symmetric Cryptography
    • Encryption
    • The One Time Pad
    • AES
      • Rijndael Finite Field
      • Round Transformations
  • Hashes
    • Introduction / overview
    • The Birthday paradox / attack
  • Isogeny Based Cryptography
    • Introduction to Isogeny Cryptography
    • Isogenies
    • Isogeny and Ramanujan Graphs
  • Appendices
    • Sets and Functions
    • Probability Theory
Powered by GitBook
On this page
  • Discrete log problem
  • Discrete log over
  • Discrete log over

Was this helpful?

Export as PDF
  1. Abstract algebra
  2. Groups

Discrete Log Problem

PreviousAnother take on groupsNextRings

Last updated 4 years ago

Was this helpful?

Discrete log problem

Given any groupGGGand elementsa,ba,ba,bsuch that an=ba^n=ban=b, the problem of solving fornnnis known as the disctete log problem (DLP). In sage, this can be done for general groups by calling discrete_log

sage: G = DihedralGroup(99)
sage: g = G.random_element()
sage: discrete_log(g^9,g) # note that if the order of g is less than 9 we would get 9 mod g.order()
9

Discrete log over (Z/nZ)∗\left(\mathbb Z/n\mathbb Z\right)^*(Z/nZ)∗

Typically, one considers the discrete log problem in (Z/nZ)∗\left(\mathbb Z/n\mathbb Z\right)^*(Z/nZ)∗, i.e. the multiplicative group of integersmod n\text{mod }nmod n. Explicitly, the problem asks forxxxgiven ax=b(modn)a^x=b\pmod nax=b(modn). This can be done by calling b.log(a) in sage:

sage: R = Integers(99)
sage: a = R(4)
sage: b = a^9
sage: b.log(a)
9

This section is devoted to helping the reader understand which functions are called when for this specific instance of DLP.

Whennnnis composite and not a prime power, discrete_log() will be used, which uses generic algorithms to solve DLP (e.g. Pohlig-Hellman and baby-step giant-step).

When n=pn=pn=pis a prime, Pari znlog will be used, which uses a linear sieve index calculus method, suitable for p<1050∼2166p < 10^{50} \sim 2 ^{166}p<1050∼2166.

When n=pkn = p^kn=pk, SageMath will fall back on the generic implementation discrete_log()which can be slow. However, Pari znlog can handle this as well, again using the linear sieve index calculus method. To call this within SageMath we can use either of the following (the first option being a tiny bit faster than the second)

x = int(pari(f"znlog({int(b)},Mod({int(a)},{int(n)}))"))
x = gp.znlog(b, gp.Mod(a, n))

Example

Given a small prime, we can compare the Pari method with the Sage defaults

p = getPrime(36)
n = p^2
K = Zmod(n)
a = K.multiplicative_generator()
b = a^123456789

time int(pari(f"znlog({int(b)},Mod({int(a)},{int(n)}))")) 
# CPU times: user 879 µs, sys: 22 µs, total: 901 µs
# Wall time: 904 µs
# 123456789

time b.log(a)
# CPU times: user 458 ms, sys: 17 ms, total: 475 ms
# Wall time: 478 ms
# 123456789

time discrete_log(b,a)
# CPU times: user 512 ms, sys: 24.5 ms, total: 537 ms
# Wall time: 541 ms
# 123456789

We can also solve this problem with even larger primes in a very short time

p = getPrime(100)
n = p^2
K = Zmod(n)
a = K.multiplicative_generator()
b = a^123456789

time int(pari(f"znlog({int(b)},Mod({int(a)},{int(n)}))")) 
# CPU times: user 8.08 s, sys: 82.2 ms, total: 8.16 s
# Wall time: 8.22 s
# 123456789

// elliptic curve discrete log functions

Discrete log over E(k)E(k)E(k)