Content deleted Content added
m →Multiplication and factoring: minus; spacing |
m →Discrete exponential and logarithm: ital, {{nowrap}} |
||
Line 56:
[[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|''α'' ∈ ''G''}} and another element {{nowrap|''β'' ∈ ''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=''α''<sup>''k''</sup> = ''β''}} is termed the '''discrete logarithm''' of ''β'' to the base ''α''. One writes {{nowrap|1=''k'' = log<sub>''α''</sub> ''β''}}.
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''.
===Cryptographically secure hash functions===
| |||