<p>How does this differ from the general concept of One-way functions?<br></p><p>A <b>one-way function</b> is a function that is easy to compute but hard to invert — given the output of the function it is difficult to find any input
which yields this output. The precise meanings of "easy" and "hard" can
be specified mathematically:</p>
<p>"Easy" means that some algorithm can compute the function in polynomial time (in the input size). "Hard" means <i>no</i> such polynomial-time algorithm exists.</p>
<p>With rare exceptions, almost the entire field of  public key cryptography rests on the existence of one-way functions.</p><a href="http://en.wikipedia.org/wiki/One-way_function">http://en.wikipedia.org/wiki/One-way_function
</a><br><p><br></p><div><span class="gmail_quote">On 12/16/06, <b class="gmail_sendername">Jon Awbrey</b> <<a href="mailto:jawbrey@att.net">jawbrey@att.net</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o<br><br>fwd from the NMBRTHRY list:<br><br>> Subj: Hiding small numbers in a huge number?<br>> Date: Sat, 16 Dec 2006 13:19:36 -0500<br>> From: Ben Huke <
<a href="mailto:benhuke@GMAIL.COM">benhuke@GMAIL.COM</a>><br>>   To: <a href="mailto:NMBRTHRY@LISTSERV.NODAK.EDU">NMBRTHRY@LISTSERV.NODAK.EDU</a><br>><br>> Dear number theorists and enthusiasts,<br>><br>> Following is a math-computing problem. If you are interested and want
<br>> to be paid for solving it, please contact me (<a href="mailto:benhuke@gmail.com">benhuke@gmail.com</a>).<br>><br>> Suppose we have a set of n positive 32-bit integers:<br>> X = {x1, x2, ... x _n}<br>>
<br>> Find a function f1 such that with T = f1(x1, x2, ... x_n), it's<br>> computationally infeasible to decompose T back to x_i's. That is, the<br>> tim e it takes to find the original component numbers will increase
<br>> exponential ly with T. However, also find a function f2 such that if r<br>> = f2(T, x) = 0 then we can conclude, with as high a probability (p) as<br>> possible, that x is in X.<br>><br>> For a rough example, we can have:
<br>><br>> f1: T = x1 * x2 * ... * x_n (In this case, with n > 20, is it computationally<br>> infeasible to decompose T back to x_i's ?)<br>><br>> f2: r = T mod x<br>><br>> Further requirements: The solution must have a higher p and have f2 more
<br>> efficient (i.e. requiring less computation) than those in the example.<br>><br>> Please give my your opinion about this problem (e.g., how difficult is<br>> it? Is it possibly solvable?).<br>><br>> Sincerely thanks,
<br>><br>> Ben<br><br>o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o<br>inquiry e-lab: <a href="http://stderr.org/pipermail/inquiry/">http://stderr.org/pipermail/inquiry/</a><br>zhongwen wp: <a href="http://zh.wikipedia.org/wiki/User:Jon_Awbrey">
http://zh.wikipedia.org/wiki/User:Jon_Awbrey</a><br>wikinfo: <a href="http://wikinfo.org/wiki.php?title=User:Jon_Awbrey">http://wikinfo.org/wiki.php?title=User:Jon_Awbrey</a><br>meta: <a href="http://www.getwiki.net/wiki.php?title=User:Jon_Awbrey">
http://www.getwiki.net/wiki.php?title=User:Jon_Awbrey</a><br>wp review: <a href="http://wikipediareview.com/index.php?showuser=398">http://wikipediareview.com/index.php?showuser=398</a><br>o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
<br><br></blockquote></div><br>