Hiding small numbers in a huge number?

[Jonathan Post]

How does this differ from the general concept of One-way functions?

A *one-way function* 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:

"Easy" means that some algorithm can compute the function in polynomial time
(in the input size). "Hard" means *no* such polynomial-time algorithm
exists.

With rare exceptions, almost the entire field of  public key cryptography
rests on the existence of one-way functions.
http://en.wikipedia.org/wiki/One-way_function


On 12/16/06, Jon Awbrey <jawbrey at att.net> wrote:
>
> o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
>
> fwd from the NMBRTHRY list:
>
> > Subj: Hiding small numbers in a huge number?
> > Date: Sat, 16 Dec 2006 13:19:36 -0500
> > From: Ben Huke <benhuke at GMAIL.COM>
> >   To: NMBRTHRY at LISTSERV.NODAK.EDU
> >
> > Dear number theorists and enthusiasts,
> >
> > Following is a math-computing problem. If you are interested and want
> > to be paid for solving it, please contact me (benhuke at gmail.com).
> >
> > Suppose we have a set of n positive 32-bit integers:
> > X = {x1, x2, ... x _n}
> >
> > Find a function f1 such that with T = f1(x1, x2, ... x_n), it's
> > computationally infeasible to decompose T back to x_i's. That is, the
> > tim e it takes to find the original component numbers will increase
> > exponential ly with T. However, also find a function f2 such that if r
> > = f2(T, x) = 0 then we can conclude, with as high a probability (p) as
> > possible, that x is in X.
> >
> > For a rough example, we can have:
> >
> > f1: T = x1 * x2 * ... * x_n (In this case, with n > 20, is it
> computationally
> > infeasible to decompose T back to x_i's ?)
> >
> > f2: r = T mod x
> >
> > Further requirements: The solution must have a higher p and have f2 more
> > efficient (i.e. requiring less computation) than those in the example.
> >
> > Please give my your opinion about this problem (e.g., how difficult is
> > it? Is it possibly solvable?).
> >
> > Sincerely thanks,
> >
> > Ben
>
> o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
> inquiry e-lab: http://stderr.org/pipermail/inquiry/
> zhongwen wp: http://zh.wikipedia.org/wiki/User:Jon_Awbrey
> wikinfo: http://wikinfo.org/wiki.php?title=User:Jon_Awbrey
> meta: http://www.getwiki.net/wiki.php?title=User:Jon_Awbrey
> wp review: http://wikipediareview.com/index.php?showuser=398
> o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20061216/18e31463/attachment-0002.htm>