Content deleted Content added
Be more explicit about surjectivity in the lead. It's only a few words longer, and avoids a wishy-washy statement which leaves the reader hanging wondering what the later section says. Some MOS:NOPIPE fixes. |
m →Multiplication and factoring: Fixed typo |
||
Line 41:
===Multiplication and factoring===
The function ''f'' takes as inputs two prime numbers ''p'' and ''q'' in binary notation and returns their product. This function can be "easily" computed in [[big O notation|''O''(''b''<sup>2</sup>)]] time, where ''b'' is the total number of bits of the inputs. Inverting this function requires finding the [[integer factorization|factors of a given
This function can be generalized by allowing ''p'' and ''q'' to range over a suitable set of [[semiprimes]]. Note that ''f'' is not one-way for randomly selected integers {{nowrap|''p'', ''q'' > 1}}, since the product will have 2 as a factor with probability 3/4 (because the probability that an arbitrary ''p'' is odd is 1/2, and likewise for ''q'', so if they're chosen independently, the probability that both are odd is therefore 1/4; hence the probability that ''p'' or ''q'' is even, is {{nowrap|1=1 − 1/4 = 3/4}}).
| |||