|
Yes, it's invertible, but the thing is that we lie slightly when we write it like that. Instead of normal exponentiation, we chose an operation where Amdahl's Law screws you over. The simplest choice for this lie is that we perform all of the exponentiations modulo a large prime number. The best known algorithms for performing the inverse of exponentiation modulo a large integer with at least one large prime factor (called a discrete logarithm) have some steps that parallelize well, but the steps that don't parallelize well still take thousands of years. (Remember that a large prime number has a large prime factor: itself.) More generally, we can talk about the properties required of this operation we lie about. The two properties we need are quasi-commutativity and the inverse operation being insanely slow. Normal commutativity means f(a, b) = f(b, a), quasicommutativity means f( f( x, a ), b ) = f( f( x, b ), a ). Another common choice for this quasicommutative operation is multiplication of a point in an elliptic curve by a scalar. Again, it's not the normal integer multiplication we're talking about, which can confuse people. It's called multiplication because it's defined in terms of another operation called addition of two points, and it does follow the normal algebraic rules, allowing you to re-use all of the algebra you learned in elementary school, except that you need to remember every time you write the division sign, you need to remember that that step takes thousands of years even on a multi-million-core supercomputer. With points on an elliptic curve, we usually write points with capital letters and scalars with lower-case letters. a * b * P = b * a * P is the quasicommutative operation with a slow inverse that we use for elliptic curve cryptography. Remember that with normal integer exponentiation, x^a * x^b = x^(a+b), so all of the normal algebraic rules would still apply if we changed our notation to use logarithmic space and wrote x^a as aX and x^b as bX, and this is the notation usually used when talking about algebraic groups other than integers modulo large integers ("multiplicative groups modulo large integers"). |