Content deleted Content added
→Universal one-way function: Narrowed down the specific article section. |
→The Rabin function (modular squaring): Link to Rabin signature algorithm, not to broken textbook encryption scheme. |
||
Line 49:
The '''Rabin function''',<ref name=Goldreich />{{rp|57}} or squaring [[modular arithmetic|modulo]] <math>N=pq</math>, where {{mvar|p}} and {{mvar|q}} are primes is believed to be a collection of one-way functions. We write
:<math>\operatorname{Rabin}_N(x)\triangleq x^2\bmod N</math>
to denote squaring modulo {{mvar|N}}: a specific member of the '''Rabin collection'''. It can be shown that extracting square roots, i.e. inverting the Rabin function, is computationally equivalent to factoring {{mvar|N}} (in the sense of [[polynomial-time reduction]]). Hence it can be proven that the Rabin collection is one-way if and only if factoring is hard. This also holds for the special case in which {{mvar|p}} and {{mvar|q}} are of the same bit length. The [[Rabin
===Discrete exponential and logarithm===
| |||