Op maandag 06 mei 2002 15:53 schreef Appie-B het volgende:
heb je toevallig een linkje naar die schattingsmethode?
geen linkie, wel een paar mailtjes er over.
voor de duidelijkheid: er zijn 2^109 punten en de schatting is dat we 58.000.000 punten moeten bepalen. Later is dit aantal aangepast naar 54.8 miljoen ivm een rekenvautje
Hi Debug,
The 58,000,000 figure is because the attack is a birthday-type attack. For
example, the expected number of people that need to be in a room before there
are two with the same birthday is about 32 (or something - I forget the exact
number). Asymptotically, this phenomenon is the following:
Q: How many random numbers between 1 and N must one choose before you'd expect
there to be two that are the same?
A: sqrt[N*pi/2]
In our case, there are about 2^{109} different points, so we expect that two
machines will have hit the same point after about 2^{54.8} total points
computed (or similar). If two machines hit the same point, they shortly after
will report the same DP (but with different p_ct and q_ct parameters). Anyway,
we've computed about 2^{54.8} points when we've recieved 2^{54.8 - 29} ~ 58
million DP.
The (apriori) probability of a collision after having computed 'n' points can
be approximated with a nice function. I will start adding this figure to the
stats when I have time to write the code to do the approxaimation.
Cheers,
Chris
En hier een stukkie over het birthday principe waar de hele berekening op stoelt.
[qoute]
Hi Debug,
Sorry - I just realized that I forgot to reply to your email. Sandy was
right on the money. I will elaborate a little, though, because it's very
important and relevent to the challenge. Loosely, here's why it works:
Suppose there are, say 23 people, in a room. For simplicity, assume also that
birthdays are uniformly distributed between 365 possibilities.
At first, one may be inclined to say that the probability that two of them
have the same birthday is probably about 23/365 ~ 0.063. This is wrong, and
here's why it's so much higher:
* Enumerate the people from 1 to 23.
* Person 1 could have the same b-day as any of the 22 other people.
* Person 2 could have the same b-day as any of the 21 other people
(i.e., excluding person 1, who was already compared to person 2).
* Person 3 could have the same b-day as any of the 20 other people.
...
So there are alot of ways that two people could have the same birthday. Now
here's a bit more rigorous explanation of how to calculate it:
First answer the `opposite' question: What's the probability that all 23
people have unique birthdays?
`Choose' the b-day of person 1. There are 365 ways to do this.
`Choose' the b-day of person 2. There are 364 ways to do this,
so that person 2 has a different b-day than person 1.
`Choose' the b-day of person 3. There are 363 ways to do this.
...
So there are 365*364*363*...*343 ways to choose the birthdays to be all
different. But there are 365^(23) ways in total to choose the birthdays. Since
all of those 365^(23) possibilities are equally likely by assumption, the
probability that all 23 b-days are different is
[365*364*363*...*343]/[365^(23)] ~ .493
So the probability that two people have the same birthday is about
1 - .493 = .507.
Now, calculating the figure for the same challenge we would have 2^(109)
instead of 365. The numbers make it a bit inconvenient to calculate in the
same way, but there are approximation formulas for calc'ing the probability
that are very accurate for numbers this large. In particular, the Poisson
approximation. See, for example:
http://www.pims.math.ca/pi/issue4/page12-14.pdf
Cheers,
Chris[/quote]
:strip_exif()/u/17260/icon.gif?f=community){kind=icon}
of zit ik nou te bazzelen.
:strip_icc():strip_exif()/u/9972/tcficon_n.jpg?f=community)
:strip_icc():strip_exif()/u/30135/images.jpg?f=community)
:strip_icc():strip_exif()/u/3061/Mobster.jpg?f=community)
(zodra ik me een keer verveel 
)