Editing One-way function (section)

===Discrete exponential and logarithm===
[[Modular exponentiation]] can be done in polynomial time. Inverting this function requires computing the [[discrete logarithm]]. Currently there are several popular groups for which no algorithm to calculate the underlying discrete logarithm in polynomial time is known. These groups are all [[finite abelian group]]s and the general discrete logarithm problem can be described as thus.

Let ''G'' be a finite abelian group of [[cardinality]] ''n''. Denote its [[group operation]] by multiplication. Consider a [[Primitive element (finite field)|primitive element]] {{nowrap|''&alpha;'' &isin; ''G''}} and another element {{nowrap|''&beta;'' &isin; ''G''}}. The discrete logarithm problem is to find the positive integer ''k'', where {{nowrap|1 ≤ ''k'' ≤ n}}, such that:

:<math>\alpha^k = \underbrace{\alpha \cdot \alpha \cdot \ldots \cdot \alpha}_{k \; \mathrm{times}} = \beta</math>

The integer ''k'' that solves the equation {{nowrap|1=''&alpha;<sup>k</sup>'' = ''&beta;''}} is termed the '''discrete logarithm''' of ''&beta;'' to the base ''&alpha;''. One writes {{nowrap|1=''k'' = log<sub>''&alpha;''</sub> ''&beta;''}}.

Popular choices for the group ''G'' in discrete logarithm [[cryptography]] are the cyclic groups [[multiplicative group of integers modulo n|('''Z'''<sub>''p''</sub>)<sup>''×''</sup>]] (e.g. [[ElGamal encryption]], [[Diffie–Hellman key exchange]], and the [[Digital Signature Algorithm]]) and cyclic subgroups of [[elliptic curve]]s over [[finite field]]s (''see'' [[elliptic curve cryptography]]).

An elliptic curve is a set of pairs of elements of a [[Field (mathematics)|field]] satisfying {{nowrap|1=''y''<sup>2</sup> = ''x''<sup>3</sup> + ''ax'' + ''b''}}. The elements of the curve form a group under an operation called "point addition" (which is not the same as the addition operation of the field). Multiplication ''kP'' of a point ''P'' by an integer ''k'' (''i.e.'', a [[Group action (mathematics)|group action]] of the additive group of the integers) is defined as repeated addition of the point to itself. If ''k'' and ''P'' are known, it is easy to compute {{nowrap|1=''R'' = ''kP''}}, but if only ''R'' and ''P'' are known, it is assumed to be hard to compute ''k''.