[140783] in North American Network Operators' Group
Re: Had an idea - looking for a math buff to tell me if it's possible
daemon@ATHENA.MIT.EDU (Heath Jones)
Wed May 18 23:03:55 2011
In-Reply-To: <20110519025221.GA2746@panix.com>
Date: Thu, 19 May 2011 04:03:46 +0100
From: Heath Jones <hj1980@gmail.com>
To: Brett Frankenberger <rbf+nanog@panix.com>
Cc: nanog <nanog@nanog.org>
Errors-To: nanog-bounces+nanog.discuss=bloom-picayune.mit.edu@nanog.org
Ha! I was wondering this the whole time - if the size of the counter would
make it a zero sum game. That sux! :)
On 19 May 2011 03:52, Brett Frankenberger <rbf+nanog@panix.com> wrote:
> On Thu, May 19, 2011 at 12:26:26AM +0100, Heath Jones wrote:
> > I wonder if this is possible:
> >
> > - Take a hash of the original file. Keep a counter.
> > - Generate data in some sequential method on sender side (for example
> simply
> > starting at 0 and iterating until you generate the same as the original
> > data)
> > - Each time you iterate, take the hash of the generated data. If it
> matches
> > the hash of the original file, increment counter.
> > - Send the hash and the counter value to recipient.
> > - Recipient performs same sequential generation method, stopping when
> > counter reached.
> >
> > Any thoughts?
>
> That will work. Of course, the CPU usage will be overwhelming --
> longer than the age of the universe to do a large file -- but,
> theoretically, with enough CPU power, it will work.
>
> For a 8,000,000,000 bit file and a 128 bit hash, you will need a
> counter of at least 7,999,999,872 bits to cover the number of possible
> collisions.
>
> So you will need at leat 7,999,999,872 + 128 = 8,000,000,000 bits to
> send your 8,000,000,000 bit file. If your goal is to reduce the number
> of bits you send, this wouldn't be a good choice.
>
> -- Brett
>
