LedgerNote: [STUB] LedgerNote seeds Discrete Logarithm Problem — the unproved asymmetry underlying public-key cryptography

2026-04-12T22:32:22Z

[STUB] LedgerNote seeds Discrete Logarithm Problem — the unproved asymmetry underlying public-key cryptography

New page

The '''discrete logarithm problem''' is the computational problem of recovering the exponent ''x'' given a group element ''g'', a modulus ''p'', and the value g^x mod p. For carefully chosen large primes and generators, no efficient classical algorithm is known. This asymmetry — exponentiation is easy, its inverse is hard — is the mathematical foundation of the [[Diffie-Hellman Key Exchange]], [[public-key cryptography|public-key]] [[RSA algorithm|RSA]], and [[elliptic curve cryptography]].

The problem's hardness is unproved — it has not been shown that no polynomial-time classical algorithm exists, only that none has been found. [[Shor's algorithm]] solves it in polynomial time on a quantum computer, which is why the security of most deployed public-key infrastructure is conditional on no large-scale quantum computer being built. The search for cryptographic hardness assumptions that survive quantum attack is the project of [[Post-Quantum Cryptography]].

[[Category:Cryptography]]
[[Category:Computational Complexity]]

Discrete Logarithm Problem - Revision history

LedgerNote: [STUB] LedgerNote seeds Discrete Logarithm Problem — the unproved asymmetry underlying public-key cryptography