70:, which are both modeled as being truly random processes in the underlying physics. Since these processes are not practical sources of random numbers, pseudorandom numbers are used, which ideally have the unpredictability of a truly random sequence, despite being generated by a deterministic process.
92:
In some cases where it is important for the sequence to be demonstrably unpredictable, physical sources of random numbers have been used, such as radioactive decay, atmospheric electromagnetic noise harvested from a radio tuned between stations, or intermixed timings of
33:
and repeatable process. Simply put, the problem is that many of the sources of randomness available to humans (such as rolling dice) rely on physical processes not readily available to computer programs.
62:, however, most processes, such as gravitational acceleration, are deterministic, meaning that they always produce the same outcome from the same starting point. Some notable exceptions are
154:
against a class of adversaries if no adversary from the class can distinguish it from the uniform distribution with significant advantage. This notion of pseudorandomness is studied in
120:
The first attempt to provide researchers with a ready supply of random digits was in 1927, when the
Cambridge University Press published a table of 41,600 digits developed by
276:
247:
320:
296:
97:. The time investment needed to obtain these numbers leads to a compromise: using some of these physics readings as a seed for a pseudorandom number generator.
362:
130:
670:
513:
85:. Since the same seed will yield the same sequence every time, it is important that the seed be well chosen and kept hidden, especially in
539:
pseudorandomness, the theory of efficiently generating objects that "look random" despite being constructed using little or no randomness
702:
444:
487:
619:
427:
128:
generated numbers by the electronic simulation of a roulette wheel; the results were eventually published in 1955 as
368:
417:
323:
155:
451:
See especially
Chapter 8: Pseudorandom generators, pp. 284–348, and Appendix C.2: Pseudorandomness, pp. 490–493.
105:
Before modern computing, researchers requiring random numbers would either generate them through various means (
384:
78:
373:
143:
337:
describes a model of computation with bounded resources and one is interested in designing distributions
697:
609:
Oded
Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press. 2008.
396:
390:
217:
190:
147:
588:
376: – Seemingly random, difficult to predict bit stream created by a deterministic algorithm
350:
26:
492:
In RFC 4086, the use of pseudorandom number sequences in cryptography is discussed at length.
379:
43:
653:
570:
Jonathan
Knudson (January 1998). "Javatalk: Horseshoes, hand grenades and random numbers".
30:
252:
223:
8:
67:
47:
518:
402:
305:
281:
94:
664:
440:
423:
86:
63:
643:
464:
125:
399: – Producing a sequence that cannot be predicted better than by random chance
365: – Type of functions designed for being unsolvable by root-finding algorithms
434:
679:
656:
637:
18:
Appearing random but actually being generated by a deterministic, causal process
552:
121:
691:
387: – Algorithm that generates an approximation of a random number sequence
110:
159:
89:
applications, where the pattern's unpredictability is a critical feature.
82:
468:
51:
648:
635:
74:
114:
55:
482:
405: – Pseudo-random signal with characteristics similar to noise
59:
483:
HotBits: Genuine random numbers, generated by radioactive decay
514:"Connoisseurs of Chaos Offer A Valuable Product: Randomness"
507:
505:
42:
The generation of random numbers has many uses, such as for
106:
502:
636:
D. Eastlake, 3rd; J. Schiller; S. Crocker (June 2005).
488:
Using and
Creating Cryptographic-Quality Random Numbers
457:
363:
Cryptographically secure pseudorandom number generator
341:
with certain properties that are pseudorandom against
81:, which must first be provided with a number called a
553:"Web's random numbers are too weak, researchers warn"
308:
284:
255:
226:
73:
In many applications, the deterministic process is a
131:
A Million Random Digits with 100,000 Normal
Deviates
563:
436:Computational Complexity: A Conceptual Perspective
420:, Volume 2: Seminumerical Algorithms (3rd edition)
314:
290:
270:
241:
689:
569:
29:, despite having been produced by a completely
511:
137:
117:, etc.) or use existing random number tables.
25:sequence of numbers is one that appears to be
532:
669:: CS1 maint: numeric names: authors list (
455:Vadhan, S. P. (2012). "Pseudorandomness".
647:
550:
432:
690:
629:
454:
349:is often specified as the output of a
393: – Type of mathematical sequence
639:Randomness Requirements for Security
583:
581:
333:In typical applications, the class
13:
409:
14:
714:
578:
476:
591:. RAND Corporation. January 2001
512:George Johnson (June 12, 2001).
369:List of random number generators
422:. Addison-Wesley Professional,
418:The Art of Computer Programming
156:computational complexity theory
612:
603:
544:
526:
439:. Cambridge University Press.
265:
259:
236:
230:
189:} be a class of functions. A
1:
496:
385:Pseudorandom number generator
79:pseudorandom number generator
37:
703:Theoretical computer science
551:Mark Ward (August 9, 2015).
374:Pseudorandom binary sequence
144:theoretical computer science
7:
356:
138:In computational complexity
10:
719:
682:.
220:between the distributions
100:
589:"A Million Random Digits"
433:Goldreich, Oded (2008).
397:Random number generation
391:Low-discrepancy sequence
158:and has applications to
415:Donald E. Knuth (1997)
173:be finite sets and let
351:pseudorandom generator
316:
292:
272:
243:
676:Best Common Practice.
533:S. P. Vadhan (2012).
380:Pseudorandom ensemble
317:
293:
273:
244:
345:. The distribution
324:uniform distribution
322:is sampled from the
306:
282:
271:{\displaystyle f(Y)}
253:
242:{\displaystyle f(X)}
224:
218:statistical distance
27:statistically random
678:Obsoletes RFC
68:quantum measurement
48:Monte Carlo methods
620:"Pseudorandomness"
519:The New York Times
469:10.1561/0400000010
403:Pseudorandom noise
312:
288:
268:
239:
75:computer algorithm
574:. pp. 16–17.
446:978-0-521-88473-0
315:{\displaystyle Y}
291:{\displaystyle X}
64:radioactive decay
710:
698:Pseudorandomness
683:
674:
668:
660:
651:
649:10.17487/RFC4086
633:
627:
626:
624:
616:
610:
607:
601:
600:
598:
596:
585:
576:
575:
567:
561:
560:
548:
542:
541:
535:Pseudorandomness
530:
524:
523:
509:
472:
450:
330:, is at most ε.
321:
319:
318:
313:
298:is sampled from
297:
295:
294:
289:
277:
275:
274:
269:
248:
246:
245:
240:
126:RAND Corporation
718:
717:
713:
712:
711:
709:
708:
707:
688:
687:
686:
662:
661:
652:. BCP 106.
634:
630:
622:
618:
617:
613:
608:
604:
594:
592:
587:
586:
579:
568:
564:
549:
545:
531:
527:
510:
503:
499:
479:
447:
412:
410:Further reading
359:
307:
304:
303:
283:
280:
279:
254:
251:
250:
225:
222:
221:
140:
124:. In 1947, the
115:roulette wheels
103:
44:random sampling
40:
19:
12:
11:
5:
716:
706:
705:
700:
685:
684:
628:
611:
602:
577:
562:
543:
525:
500:
498:
495:
494:
493:
490:
485:
478:
477:External links
475:
474:
473:
463:(1–3): 1–336.
452:
445:
430:
411:
408:
407:
406:
400:
394:
388:
382:
377:
371:
366:
358:
355:
311:
287:
267:
264:
261:
258:
238:
235:
232:
229:
165:Formally, let
139:
136:
122:L.H.C. Tippett
102:
99:
39:
36:
17:
9:
6:
4:
3:
2:
715:
704:
701:
699:
696:
695:
693:
681:
677:
672:
666:
658:
655:
650:
645:
641:
640:
632:
621:
615:
606:
590:
584:
582:
573:
566:
558:
554:
547:
540:
536:
529:
521:
520:
515:
508:
506:
501:
491:
489:
486:
484:
481:
480:
470:
466:
462:
458:
453:
448:
442:
438:
437:
431:
429:
428:0-201-89684-2
425:
421:
419:
414:
413:
404:
401:
398:
395:
392:
389:
386:
383:
381:
378:
375:
372:
370:
367:
364:
361:
360:
354:
352:
348:
344:
340:
336:
331:
329:
325:
309:
301:
285:
262:
256:
233:
227:
219:
215:
211:
208:if for every
207:
203:
199:
195:
192:
188:
184:
180:
176:
172:
168:
163:
161:
157:
153:
149:
145:
135:
133:
132:
127:
123:
118:
116:
112:
108:
98:
96:
90:
88:
84:
80:
76:
71:
69:
65:
61:
57:
53:
49:
45:
35:
32:
31:deterministic
28:
24:
16:
675:
638:
631:
614:
605:
593:. Retrieved
571:
565:
556:
546:
538:
534:
528:
517:
460:
456:
435:
416:
346:
342:
338:
334:
332:
327:
299:
213:
209:
205:
202:pseudorandom
201:
197:
193:
191:distribution
186:
182:
178:
174:
170:
166:
164:
160:cryptography
152:pseudorandom
151:
148:distribution
141:
129:
119:
104:
91:
72:
41:
23:pseudorandom
22:
20:
15:
83:random seed
52:board games
692:Categories
572:Sun Server
497:References
95:keystrokes
38:Background
595:March 30,
77:called a
665:citation
357:See also
278:, where
204:against
87:security
56:gambling
101:History
60:physics
443:
426:
216:, the
58:. In
623:(PDF)
200:is ε-
196:over
111:cards
54:, or
680:1750
671:link
657:4086
597:2017
441:ISBN
424:ISBN
302:and
249:and
169:and
146:, a
107:dice
66:and
654:RFC
644:doi
557:BBC
465:doi
326:on
212:in
177:= {
150:is
142:In
694::
667:}}
663:{{
642:.
580:^
555:.
537:.
516:.
504:^
459:.
353:.
185:→
181::
162:.
134:.
113:,
109:,
50:,
46:,
21:A
673:)
659:.
646::
625:.
599:.
559:.
522:.
471:.
467::
461:7
449:.
347:D
343:F
339:D
335:F
328:S
310:Y
300:D
286:X
266:)
263:Y
260:(
257:f
237:)
234:X
231:(
228:f
214:F
210:f
206:F
198:S
194:D
187:T
183:S
179:f
175:F
171:T
167:S
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.