Editing One-way function (section)

===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 integer]] ''N''.  The best factoring algorithms known run in <math>O\left(\exp\sqrt[3]{\frac{64}{9} b (\log b)^2}\right)</math>time, where b is the number of bits needed to represent ''N''.

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'' &gt; 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}}).