J
Jonas Nilsson
Just for fun I would like to find two strings that have the same crc32. The
probably of doing this for a set of for example one million strings is more
than 99.9999999999999999999999999999999999999999999999997%.
To calculate the chance of $n strings leading to all different crc32 is done
by this code: (assuming randomly distributed crc32 values)
use strict;
my $tmp=1;
my $n=1000000;
my $ant=2**32;
for (0..$n) {
$tmp*=($ant-$_)/$ant;
print "$_\t$tmp\n" unless ($_%10000);
}
If I try to find two string that give the same crc32 however I don't
succeed. I use the code below to spot strings that have the same first 28
bits (to save memory I don't store all 32 bits). The code don't find any
however even after checking 6 million strings!
Why?
Sorry for being a bit off topic.
use strict;
use Digest::CRC qw(crc32);
my $string='aaaaa';
$|=1;
my $v;
for (0..11881375) {
unless ($_%100000) {
print "$_\t",length($v),"\n";
}
my $tmp=crc32($string)>>4;
if (vec($v,$tmp,1)) {
print "$string\n";
}
vec($v,$tmp,1)=1;
$string++;
}
/jN
probably of doing this for a set of for example one million strings is more
than 99.9999999999999999999999999999999999999999999999997%.
To calculate the chance of $n strings leading to all different crc32 is done
by this code: (assuming randomly distributed crc32 values)
use strict;
my $tmp=1;
my $n=1000000;
my $ant=2**32;
for (0..$n) {
$tmp*=($ant-$_)/$ant;
print "$_\t$tmp\n" unless ($_%10000);
}
If I try to find two string that give the same crc32 however I don't
succeed. I use the code below to spot strings that have the same first 28
bits (to save memory I don't store all 32 bits). The code don't find any
however even after checking 6 million strings!
Why?
Sorry for being a bit off topic.
use strict;
use Digest::CRC qw(crc32);
my $string='aaaaa';
$|=1;
my $v;
for (0..11881375) {
unless ($_%100000) {
print "$_\t",length($v),"\n";
}
my $tmp=crc32($string)>>4;
if (vec($v,$tmp,1)) {
print "$string\n";
}
vec($v,$tmp,1)=1;
$string++;
}
/jN