----- Original Message -----
From: "gfgs pedo" <[EMAIL PROTECTED]>
> > > Oh surely you can do better than that - making it
> > hard to guess the seed
> > > is also clearly a desirable property (and one that
> > the square root "rng"
> > > does not have).
> U can choose any arbitrary seed(greater than 100 bits
> as he (i forgot who) mentioned earlier.Then subject it
> to the Rabin-Miller test.
> Since the seed value is a very large number,it would
> be impossible to determine the actual value.The
> chances the intruder find the correct seed or the
> prime number hence generated is practically verly low.
You act like the only possible way to figure it out is to guess the initial
seed. The truth is that the number used leaves a substantial amount of
residue in it's square root, and there are various rules that can be applied
to square roots as well. Since with high likelihood you will have a lot of
small factors but few large ones, it's a reasonable beginning to simply
store the roots of the first many primes, this gives you a strong network to
work from when looking for those leftover signatures. With decent likelihood
the first 2^32 primes would be sufficient for this when you choose 100 bit
numbers, and this attack will be much faster than brute force. So while you
have defeated brute force (no surprise there, brute force is easy to defeat)
you haven't developed a strong enough generation sequence to really get much
of anywhere.
> > Of course, finding the square root of a 100 digit
> > number to a
> > precision of hundreds of decimal places is a lot of
> > computational
> > effort for no good reason.
> Yes the effort is going to be large but why no good
> reason?
Because it's a broken pRNG, that is extremely expensive to run. If you want
a fast pRNG you look to ciphers in CTR mode, or stream ciphers, if you want
one that's provably good you go to BBS (which is probably faster than your
algorithm anyway). So there's no good reason to implement such an algorithm.
> > BTW, the original poster seemed to be under the
> > delusion that
> > a number had to be prime in order for its square to
> > be irrational,
> > but every integer that is not a perfect square has
> > an irrational
> > square root (if A and B are mutually prime, A^2/B^2
> > can't be
> > simplified).
>
> Nope ,I'm under no such delusion :)
Just the delusion that your algorithm was good.
Joe
