Friday, December 6, 2013

Notes - Discrete Logarithms

The following are notes from Introduction to Cyrptography with Coding Theory.

  • RSA Algorithm relies on the difficulty of factoring, but we can also use the difficulty of discrete logs
  • Fix a prime p. Let α and Β be nonzero integers mod p and suppose
    • Β ≡ αx (mod p)
  • It is difficult to find x assuming we choose a large enough prime
  • α is taken to be a primitive root mod p so that every Β is a power of α (mod p)
  • The size of the largest primes for which discrete logs can be computed is usually about the same size as the largest integers that could be factored
  • This means that discrete logs are another example of one-way functions
    • where f(x) is easy to compute but given y it is computationally infeasible to find x

No comments:

Post a Comment