Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I am currently gathering some test methods and test suites for random number generator qualities, and am a bit stuck at finding something feasible to test for n-dimensional equidistribution. As input I have an arbitrary amount of bits from that PRNG and a dimension N, and as output I want something like "I am reasonably sure that this is equidistributed in N dimensions". N should ideally be able to go up to more than 600 (It might be a good showcase to see mersenne twister hold up to, but break at 624 with this check)

Now "reasonably" here is quite a bit soft and depends on the efficiency of the tests and the resulting runtime. I don't want to wait days and weeks for an answer. Comparing e.g. with some primality tests, something ideal would be a check that for each iteration halves (or whatever is available) the probabilty of a negative result.

The problem is, I can't find anything reasonable, from an engineering point of view. It seems that for things like mersenne twister these are proven by formal mathematical proves, but that would not work for my testsuite and the desired input. I have found so far the following ideas, but they are not feasible for the mentioned reasons:

  • Similar to three dimensions I could take a point cloud, orient it "properly", project to lower dimensions and "see" that there are hyperplanes at some orientation that are much sparser/denser than the rest. But unless there is some good way to find that orientation, this is all randomly trying until something is found and it quickly takes up excessive resources when going up in dimensions.
  • I could just take pairs of N-dimensional coordinates and check those, but apart from getting only a few orientations in the resulting projection, this quickly gets into hundreds of thousand such pairs (which leads to millions of planes to be checked when I go through 1-N)

So is there anything that is relatively efficient with a useful level of confidence? I am thinking of maybe some N dimensional computation with coordinates that is inherently sensitive to a really good equidistribution and already small deviations from that distribution will make it fail/deviate.

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.