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
 | 
Pages: 1
Prev: Regarding pseudo-random functions for Pollard's Rho factoring method
Next: Call for Papers: International Conference on Chemical Engineering ICCE 2010