Randomness and reseeding?

[Linas Vepstas]

On Tue, Dec 12, 2006 at 12:20:02PM -0800, Susan Margulies wrote:
> 
> Well... just bear with me here. I have a family of graphs, and I am 
> testing them for a particular property in algebraic geometry. I tested 
> graphs 2 - 6 and noticed that if I allowed my probability to be .4, I 
> had a 90% success rate of finding my algebraic property. When I tested 
> graphs 7-9, I found my property. But 10 and above, suddenly the 
> algorithm was failing, even though the success rate should be 90%, if 
> everything else is equal (a big assumption!) I checked 
> deterministically, and discovered that graph 10 still had the 
> property.

i.e. you put graph 10 first, and that time it worked?

You may want to study up on the theory of pseudo-random number 
generators. I don't know about those in gmp, but many are 
just (prime) polynomials over a finite field, and most others 
are elliptic curves.  Thus, if your graph gives you some variety 
or ideal, its possible that the polynomial used in the 
random number generator is somehow a prime factor of your graph.
In which case, it might not appear to be random at all.

On the other hand, if you had a way of easily discovering that
a pseudo-random number sequence is not actually random, then
you would explode cryptography as we know it today.  The 
fundamental principles of cryptography are such that the 
output of a pseudo-random number generoator should be random
to the point of undetectability, because, if you can spot a 
pattern, you've broken the code. 

It might be a detour from your intent, but you should investigate 
what's going on. Although the first step is to make use you 
are correctly using a real prng, and not accidentally misusing 
it, or accidentally using some miniature test stub. It would be
interesting to know if the problem occurs only with certain
prng's but not others.

--linas