-
@ jimbocoin 🃏
2025-03-03 12:12:17
Intuitively, discrete log is hard for the same reason that division is harder than multiplication in standard arithmetic—you have to search for the answer.
In standard multiplication, there’s a straightforward, if tedious, process for finding the answer. You multiply the component digits, then add everything up.
In long division, you have to guess the right number, then multiply, then subtract, then guess again. It’s the guesses that are expensive.
In standard long division, you develop an intuition about what number to guess. That’s because the numeric field is continuous and linear (number line).
But in cryptography we use modulo arithmetic over discrete fields. Modulo means it wraps around. Discrete means no fractions.
So, for example, math in mod 7 would only use the numbers 0, 1, 2, 3, 4, 5, and 6. Any mathematical result that would normally be outside these bounds gets capped by wrapping back to the beginning. 5 + 3 = 1, for instance, because there is no 7 so you wrap around back to 0.
On such a small field (mod 7), division isn’t very expensive. You can just check all 7 choices to see what multiplies to the chosen value. But the fields used by cryptography are enormous. The prime field used by secpk256 (#Bitcoin’s elliptic curve) is only slightly smaller than 2^256.
To make things even harder, rather than having all the numbers be scalars in a line (0, 1, 2, …), elliptic curve cryptography uses points on a curve. The formula for secpk256 is:
y^2 = x^3 + 7
Given any two points that both satisfy this equation, you can add them together, much like in standard arithmetic. Adding a point to itself is like multiplication (2x). Division is the opposite operation: finding the number, which multiplied by a given point gives another given point.
For some reason, these multiplication and division operations are called power and log in elliptic curve math. So the “discrete log problem” is really performing division in the elliptic curve space of an extremely large prime field.
The discrete log problem is hard because there’s no way to go back through the modulus operator that clips the discrete field, causing it to wrap around. The only way to perform division on the elliptic curve is to search, but the prime field is so large as to make this impossible.