Prev: Regarding pseudo-random functions for Pollard's Rho factoring method
Next: Call for Papers: International Conference on Chemical Engineering ICCE 2010
From: ww josé on 17 Jun 2010 12:33 Hello, I am invoking your help on a problem I cannot solve. Consider 16 sets of 2^{23} 32-bit random integers. We denote these sets S_{i,j} such that S is a 4x4 matrix, whose cells are the sets. Thus, for 0<i,j<3, the set S_{i,j} contains 2^{23} 32-bit random elements. A 32-bit integer is viewed as a couple of two 16-bit integers (a,b)=a*0x10000+b. We want to find 4 values (a_0, a_1, a_2, a_3) and 4 values (b_0, b_1, b_2, b_3) such that: for all 0<i,j<3 we have (a_i, b_j) \in S_{i,j}. It seems to me that it is related to a generalized birthday paradox but the main issue seems to be the dependence on both lines and columns. Thanks for your help. Best regards, -- J
From: Peter Pearson on 17 Jun 2010 12:42 On Thu, 17 Jun 2010 09:33:04 -0700 (PDT), ww jos� <wwjoze(a)gmail.com> wrote: [snip] > Consider 16 sets of 2^{23} 32-bit random integers. We denote these > sets S_{i,j} such that S is a 4x4 matrix, whose cells are the sets. > Thus, for 0<i,j<3, the set S_{i,j} contains 2^{23} 32-bit random > elements. > A 32-bit integer is viewed as a couple of two 16-bit integers > (a,b)=a*0x10000+b. > We want to find 4 values (a_0, a_1, a_2, a_3) and 4 values (b_0, b_1, > b_2, b_3) such that: > for all 0<i,j<3 we have (a_i, b_j) \in S_{i,j}. [snip] So a_0 must be in the intersection of S_{0,0}, S_{0,1}, S_{0,2}, and S_{0,3}, right? That must narrow it down a lot. -- To email me, substitute nowhere->spamcop, invalid->net.
From: Francois Grieu on 18 Jun 2010 04:24 On 17/06/2010 18:42, Peter Pearson wrote: > On Thu, 17 Jun 2010 09:33:04 -0700 (PDT), ww jos� <wwjoze(a)gmail.com> wrote: > [snip] >> Consider 16 sets of 2^{23} 32-bit random integers. We denote these >> sets S_{i,j} such that S is a 4x4 matrix, whose cells are the sets. >> Thus, for 0<i,j<3, the set S_{i,j} contains 2^{23} 32-bit random >> elements. >> A 32-bit integer is viewed as a couple of two 16-bit integers >> (a,b)=a*0x10000+b. >> We want to find 4 values (a_0, a_1, a_2, a_3) and 4 values (b_0, b_1, >> b_2, b_3) such that: >> for all 0<i,j<3 we have (a_i, b_j) \in S_{i,j}. > [snip] > > So a_0 must be in the intersection of S_{0,0}, S_{0,1}, S_{0,2}, and > S_{0,3}, right? That must narrow it down a lot. I think that the OP wants (a_i, b_j) *NOT* in S_{i,j}. Francois Grieu
From: ww josé on 18 Jun 2010 04:40
On 18 juin, 10:24, Francois Grieu <fgr...(a)gmail.com> wrote: > On 17/06/2010 18:42, Peter Pearson wrote: > > > On Thu, 17 Jun 2010 09:33:04 -0700 (PDT), ww josé <wwj...(a)gmail.com> wrote: > > [snip] > >> Consider 16 sets of 2^{23} 32-bit random integers. We denote these > >> sets S_{i,j} such that S is a 4x4 matrix, whose cells are the sets. > >> Thus, for 0<i,j<3, the set S_{i,j} contains 2^{23} 32-bit random > >> elements. > >> A 32-bit integer is viewed as a couple of two 16-bit integers > >> (a,b)=a*0x10000+b. > >> We want to find 4 values (a_0, a_1, a_2, a_3) and 4 values (b_0, b_1, > >> b_2, b_3) such that: > >> for all 0<i,j<3 we have (a_i, b_j) \in S_{i,j}. > > [snip] > > > So a_0 must be in the intersection of S_{0,0}, S_{0,1}, S_{0,2}, and > > S_{0,3}, right? That must narrow it down a lot. > > I think that the OP wants (a_i, b_j) *NOT* in S_{i,j}. > > Francois Grieu Actually, it was right: (a_i, b_j) needs to be in S_{i,j}. But I think that with the given dimensions, the problem won't have any solution w.h.p. Consider sets of size 2^23 and pick (a_0, a_1, a_2, a_3) and (b_0, b_1, b_2, b_3) uniformily at random in [0, 2^16-1]. With high probability there will be a at least one b_j such that (a_i,b_j) \in S_{i,j}. And even further, the restriction of S_{i,j} to (a_i, *) where a_i is fixed would be of size 2^23/2^16=2^7. Thus, if we consider (a_0, a_1, a_2, a_3) fixed, we reduced the problem to finding a b_j in the four S_{i,j=0,1,2,3} for all i. I think this is where the generalized birthday paradox intervene, with four lists. They are of size 2^7 and their intersection would we non null with proba (2^7/2^16)^4 = 2^{-9*4}=2^{-36}. Am I correct? -- J |