[rc5] RC64 keyspace

Joseph Fisk joe at rm405n-a.roberts.fit.edu
Tue Oct 28 21:24:15 EST 1997


On Tue, 28 Oct 1997, Eric Gindrup wrote:

>         I'm more worried about the storage method for assigned and returned 
>      blocks.  There appears to be a difficulty where an interrupted client 
>      loses a block.  By itself, this is irrelevant.  However, having single 
>      blocks drop out here and there makes the set of assigned and not 
>      returned blocks "interesting", i.e. hard to represent compactly.
>      
>         Assuming that one bit is used to record the assignment of a block 
>      and one bit is used to record the receipt of a block, 2^65 bits will 
>      be needed.  This is 2^32GB (4 Exabytes).  I don't know where *I* would 
>      go to look for a storage system of that magnitude...

Each block is 2^28 keys.  There are total 2^64 keys.  That means there are
2^36 blocks, or 68,719,476,740 blocks.  If two bits are used per block,
you'll need 137438953500 bits, which is 17,179MB.  I think you
accidentally calculated the size of the array needed to keep track of each
individual key!

>         In any event, I'd expect that the Bovine crew is going to need 
>      about 256-times as much storage for this information as was used in 
>      RC5-56.

That sounds right to me, too.  In 56-bit RC5 there were 2^28 blocks.  With
two bits per block you would need 536,870,912 bits, or 67.1MB.

Joseph

**************************************************************************
** C. Joseph Fisk (mdmbkr)                           mdmbkr at chillin.org **
** Visit http://www.distributed.net - the world's fastest supercomputer **
**************************************************************************


----
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the body.



More information about the rc5 mailing list