Content deleted Content added
Tom.Reding (talk | contribs) m Enum 3 author/editor WLs; WP:GenFixes on |
m →Multiplication and factoring: minus; spacing |
||
Line 46:
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 [[integer factorization|finding the 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'' > 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
===The Rabin function (modular squaring)===
| |||