Talk:Random number generator

Blum Blum Shub

Paging a real mathematician...paging a real mathematician...

I don't have ready access to the SIAM Journal for Blum-Blum-Shub, and it's been a while since I've even formatted the equations. Collaboration here would be very very welcome, but what we need is an article that has useful content, not just links and editorializing.

Howard C. Berkowitz 15:26, 3 August 2008 (CDT)

Assuming you are talking about "A Simple Unpredictable Pseudo-Random Number Generator", I have access to the article. What do you need to know? I know very little probability theory and statistics though, so I'm not sure how much help I can be. -- Jitse Niesen 04:27, 4 August 2008 (CDT)

That's it, I believe. They aren't my strongest mathematical areas, but I wanted to see a little more of what the paper actually said, and get an idea how it would be implemented, than the summaries/reviews. I didn't follow one proof appearing elsewhere, and hoped the original might be better written. Howard C. Berkowitz 11:03, 4 August 2008 (CDT)

BBS is covered in detail in Menezes, van Oorschot & Vanstone, Handbook of Applied Cryptography, Chapter 5, page 186. Large parts of that, including the relevant section, are online [1] Sandy Harris 11:37, 4 August 2008 (CDT)

Thanks! Howard C. Berkowitz 12:14, 4 August 2008 (CDT)

Structure — how many articles

Wikipedia has [2] as a disambiguation page with links to several other things. Do we need that structure or something similar here? Certainly pseudo-random generators and true RNGs are quite different. How many articles do we need and with what structure? Sandy Harris 16:15, 3 August 2008 (CDT)

It's not clear to me that Wikipedia is setting tbe best example. In this particular case, the article is titled "Random number". Physical-measurement-based and pseudorandom generators are subtopics. The techniques for generating random sequences that follow a probability density function are common to physical-random and pseudo-random generators. The techniques of testing also apply to both, as it has been shown that apparent physical sources of randomness may show self-similarity. When the self-similarity is demonstrated, post-processing can break it and give a non-self-similar output.

This structure, I believe, works without breaking up the core concepts. It would be perfectly reasonable to have articles on specific techniques, such as BBS or radioactive counting.

In other words, what is the problem that needs to be solved? Howard C. Berkowitz 19:39, 3 August 2008 (CDT)

I'm not sure there is a problem. However, in case there might be one, it seems worth discussing early on to ensure we get the structure we need right before doing a lot of writing.

For example, I'd say pseudo-random generators and real random number generators need to be separate articles (of course linking to each other). WP has articles for both, and another separate one on applications of randomness. I'm not sure of the right structure, but I think some discussion is called for. Sandy Harris 20:01, 3 August 2008 (CDT)

Ummm...might I suggest that citing Wikipedia as the reason for doing something might not be the best argument on Citizendium, which was established as an alternative to Wikipedia, and many authors and editors came to CZ to get away from Wikipedia?

RFC 4098 discusses physical and pseudorandom generators in an integrated way. Knuth starts out discussing PRNGs, but the rest of the chapter (about half the book) is about testing for randomness, regardless of the source. Schneier, in section 17.13, discusses PRNGs and physical generators together. Goldwasser and Bellare discuss, in the same chapter, PRNGs, removing self-similarities from physical sources, and proofs that some PRNGs may be theoretically, but not computationally, breakable.

So, no, I don't see any good reason to separate the two areas. In fact, I think it's highly advisable to discuss the general approaches in a compare-and-contrast way, although it is very reasonable to have separate articles on detailed individual methods. Howard C. Berkowitz 20:15, 3 August 2008 (CDT)

Self-siimilarity of physical phenomena

Before deleting all reference to postprocessing physical phenomena that show self-similarity, could you clarify if you are saying fractal only, or all self-similarity? See the Goldwasser, Shafi & Mihir Bellare, who suggest that there may be self-similarity that is not necessaruly fractal.

Howard C. Berkowitz 01:58, 9 August 2008 (CDT)

Computer generation

I'd like to add a separate section covering true RNGs on computers, things like /dev/random, Schneier's Yarrow, ... Links to RFC 4086 and Gutmann [3], ... I think this needs to be a separate section, after the more general discussion of randomness from physical sources and before getting into PRNGs.

I'd also want to move "manual generation" from where it is now, exactly where I want to put the new section, up to the top of the article where I think it fits well as introductory/historical text. Sandy Harris 02:42, 23 October 2008 (UTC)

So the new sequence would be roughly:

1. Introduction
2. Completely manual means (i.e., coin tossing, not manually operating a radiation detector)
3. Physical random
4. Computer true random
5. PRNG

Somewhere, some common text on testing randomness.

If this is an article on random numbers, why are the sections sequential? (just wondering) Howard C. Berkowitz 03:09, 23 October 2008 (UTC)

Added a bit to the introduction

(also put in some table of contents formatting)

There's now a draft paragraph, and internal wikilink, to testing. I'm not wedded to the exact language, but I think some of this should be in the introduction.

As I think about it, I'm inclined to think that there should be some pros and cons, possibly as a table, in each major section. Manual generation has a low entry cost if you don't have a computer, but the personnel costs actually may be high. Radioactive counters are usually quite trustworthy with a good view of cosmic radiation, but may not sense enough external counts if deep in a shelter, and an artificial radioactive source adds cost and possibly hazards. You also might not want to depend on cosmic radiation if you needed random numbers aboard a deep space probe. ...and so forth...

It's looking good. Howard C. Berkowitz 13:38, 23 October 2008 (UTC)

New from NIST

Just announced. Not sure where it fits in the article, so just dropping it here. "NIST Special Publication 800-108 Recommendation for Key Derivation Using Pseudorandom Functions" [4] Probably goes with the RFC and the Gutmann paper.Sandy Harris 07:56, 9 November 2008 (UTC)

Move to "random number generator"?

It has been suggested at Talk:Block_cipher#Some_remarks that this article should be titled "random number generator". I agree, even though checking history I find it was me that chose the current title. Anyone care to comment or should I just move it? Sandy Harris

Push toward approval?

Of the four main symmetric crypto primitives, one (Block cipher) is approved, two (Stream cipher and Hash (cryptography)) are not even close and probably won't be until other people start contributing there. This one is the closest we have to approvability; much of it is pretty good.

However, it does need work, especially in the "Testing" section. I've done about all I can. Anyone care to do the rest? Sandy Harris 04:30, 27 November 2010 (UTC)

A year and a half has gone by since I asked the question above. We have several new computer writers. Anyone up for it now? Sandy Harris 03:11, 10 July 2012 (UTC)

Links

[5] Toshiba high-performance RNG, probably goes in somewhere. Sandy Harris 23:13, 2 December 2010 (UTC)

US gov't withdraws Green Card lottery results [6] because a programming error made the numbers insufficiently random. Sandy Harris 20:04, 13 May 2011 (CDT)

Quantum RNG research [7] Sandy Harris 01:38, 15 April 2012 (UTC)