Fwd: Hiding small numbers in a huge number?

[Jon Awbrey]

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