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

Back to ToC