Content deleted Content added
New talk section: Wrong integer multiplication upper bound Tags: Mobile edit Mobile web edit |
|||
Line 197:
Here is a one-way function that is impossible to derive its input based on outputs: f(x)=0. What is this article or definition missing? [[User:Average64|Average64]] ([[User talk:Average64|talk]]) 19:51, 27 May 2014 (UTC)
: This example is discussed in the section "Theoretical definition". f(x)=0 is not a one-way function. Hence nothing is missing here. [[Special:Contributions/92.106.209.242|92.106.209.242]] ([[User talk:92.106.209.242|talk]]) 11:10, 29 May 2014 (UTC)
== Wrong integer multiplication upper bound ==
AFAIK, it's not O(n^2) as stated in the article.
See Fürer's algorithm, it can reach O(n\log n2^{3\log^* n}) [[User:Willrazen|Willrazen]] ([[User talk:Willrazen|talk]]) 19:27, 2 February 2016 (UTC)
| |||