1,250 bits x 10 streams works:-
------------------------------------------------------------------------------
RESULTS FOR THE UNIFORMITY OF P-VALUES AND THE PROPORTION OF PASSING SEQUENCES
------------------------------------------------------------------------------
generator is <Blum-Blum-Shub>
------------------------------------------------------------------------------
C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 P-VALUE PROPORTION STATISTICAL TEST
------------------------------------------------------------------------------
0 0 2 2 2 1 1 2 0 0 0.534146 10/10 FFT
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
as the above is a very good pass.
Assuming that your RNG is good, just running the FFT is inconclusive. You often get isolated test failures as randomness is pesky, especially as the sample size gets smaller. Randomness is very much a function of sample size. That's why test 'suites' have a broad variety of very simple and very complex tests. So no to "does the Random Number Generator always passes(sic) with all values of n ≥ 1000".
I would also be wary of 100 bitstreams. From experience again, 10 seems a good amount and allows a decent p value to be determined. You'll bang up against diminishing returns after >> 10 bitstreams. So do 10 bitstreams of 1,000,000 bits each (1.25 MB total) to run all the tests. You won't get any p values for the RandomExcursions(Variant) tests but you'll get an indication of success from the pass rate.
A rule of thumb in statistical circles is that you should take 30 samples✝ to be sure of distinguishing a distribution. So you'd use 30 bit streams of 1,000,000 bits each (3.75 MB). I've done that and SP 800-22 produces p values in the RandomExcursions(Variant) tests as well as pass/fail.
But before anything, if you've designed your own TRNG (and presumably the randomness extractor), run ent✝✝. It's ostensibly the most robust randomness test out there. Use 500 kB. If your samples fail ent
, then your TRNG is bad.
✝ Whilst this is an Old Timer's rule of thumb, there is some debate as to its veracity these days with the advent of computers.
✝✝ Or now, there is an updated version called ent3000. It's specifically targetted at DIY TRNG Makers.
/dev/urandom
and see if it's the test parameters or it's NIST implementation. They're not good coders. What is your RNG exactly? $\endgroup$