1108:
A main application of pseudorandom generators lies in the derandomization of computation that relies on randomness, without corrupting the result of the computation. Physical computers are deterministic machines, and obtaining true randomness can be a challenge. Pseudorandom generators can be used to
1257:
While unproven assumption about circuit complexity are needed to prove that the Nisan–Wigderson generator works for time-bounded machines, it is natural to restrict the class of statistical tests further such that we need not rely on such unproven assumptions. One class for which this has been done
1157:
whose seed length is as short as possible. If a full derandomization is desired, a completely deterministic simulation proceeds by replacing the random input to the randomized algorithm with the pseudorandom string produced by the pseudorandom generator. The simulation does this for all possible
61:
Many different classes of statistical tests have been considered in the literature, among them the class of all
Boolean circuits of a given size. It is not known whether good pseudorandom generators for this class exist, but it is known that their existence is in a certain sense equivalent to
1071:
In the 1980s, simulations in physics began to use pseudorandom generators to produce sequences with billions of elements, and by the late 1980s, evidence had developed that a few common generators gave incorrect results in such cases as phase transition properties of the 3D
1812:
The pseudorandom generators used in cryptography and universal algorithmic derandomization have not been proven to exist, although their existence is widely believed. Proofs for their existence would imply proofs of lower bounds on the
1009:, which is widely believed but a famously open problem. The existence of cryptographically secure pseudorandom generators is widely believed. This is because it has been proven that pseudorandom generators can be constructed from any
1048:
used must be random over strings of length |m|. Perfectly secure encryption is very costly in terms of key length. Key length can be significantly reduced using a pseudorandom generator if perfect security is replaced by
1791:
158:
659:
822:
54:
such that no statistical test in the class can distinguish between the output of the generator and the uniform distribution. The random seed itself is typically a short binary string drawn from the
1526:
1646:
251:
736:
948:, and one is interested in designing a pseudorandom generator with small seed length and bias, and such that the output of the generator can be computed by the same sort of algorithm.
1133:
describes the randomized algorithm or class of randomized algorithms that one wants to simulate, and the goal is to design an "efficiently computable" pseudorandom generator against
853:
1460:
882:
688:
421:
1155:
1131:
988:
938:
372:
305:
1383:
1337:
1569:
477:
328:
547:
277:
1418:
1291:
911:
457:
1648:, which is optimal up to constant factors. Pseudorandom generators for linear functions often serve as a building block for more complicated pseudorandom generators.
1420:-space machines. Nisan's generator has been used by Saks and Zhou (1999) to show that probabilistic log-space computation can be simulated deterministically in space
600:
570:
504:
1703:
1683:
348:
957:
66:. Hence the construction of pseudorandom generators for the class of Boolean circuits of a given size rests on currently unproven hardness assumptions.
1100:
showed that NIST testing is not enough to detect weak pseudorandom generators and developed statistical distance based testing technique LILtest.
994:
of size polynomial in the input and with a single bit output, and one is interested in designing pseudorandom generators that are computable by a
1874:
1005:
It is not known if cryptographically secure pseudorandom generators exist. Proving that they exist is difficult since their existence implies
1708:
1036:
Pseudorandom generators have numerous applications in cryptography. For instance, pseudorandom generators provide an efficient analog of
77:
2214:
1657:
612:
2182:
2061:
1963:
1930:
741:
1465:
1582:
2119:
1838:
186:
2142:
2083:
2039:
1850:
1076:
and shapes of diffusion-limited aggregates. Then in the 1990s, various idealizations of physics simulations—based on
1064:, where a large number of messages can be safely encrypted under the same key. Such a construction can be based on a
693:
507:
63:
55:
19:
This page is about the formal concept in theoretical computer science. For the common meaning of this term, see
1109:
efficiently simulate randomized algorithms with using little or no randomness. In such applications, the class
1021:
1343:(1992) showed that this derandomization can actually be achieved with a pseudorandom generator of seed length
1237:
proved that the construction of Nisan and
Wigderson is a pseudorandom generator assuming that there exists a
20:
2090:
Naor, Joseph; Naor, Moni (1990), "Small-bias probability spaces: Efficient constructions and applications",
1182:
can be deterministically simulated in polynomial time. The existence of such a simulation would imply that
1065:
27:
1190:. To perform such a simulation, it is sufficient to construct pseudorandom generators against the family
827:
2075:
2053:
2031:
2219:
1423:
998:
and whose bias is negligible in the circuit size. These pseudorandom generators are sometimes called
995:
858:
664:
381:
2165:
2102:
1136:
1112:
969:
919:
353:
286:
1346:
1300:
375:
1552:
462:
313:
1572:
1537:
1158:
seeds and averages the output of the various runs of the randomized algorithm in a suitable way.
1061:
513:
43:
256:
2160:
2097:
1955:
1948:
1388:
1261:
2091:
1817:
of certain explicit functions. Such circuit lower bounds cannot be proved in the framework of
1297:, it is easy to show that every probabilistic log-space computation can be simulated in space
887:
426:
2224:
1238:
1179:
579:
2150:
Viola, Emanuele (2008). "The Sum of d Small-Bias
Generators Fools Polynomials of Degree D".
1013:
which are believed to exist. Pseudorandom generators are necessary for many applications in
1889:
1294:
1175:
1081:
941:
555:
482:
8:
1547:
1230:
1006:
2197:
2125:
2093:
Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90
1888:
HĂ…stad, Johan; Impagliazzo, Russell; Levin, Leonid A.; Luby, Michael (1 January 1999).
1868:
1814:
1688:
1668:
1246:
991:
333:
1821:
assuming the existence of stronger variants of cryptographic pseudorandom generators.
2178:
2136:
2115:
2079:
2057:
2035:
1959:
1926:
1856:
1846:
1214:) is an arbitrary polynomial, the seed length of the pseudorandom generator is O(log
1050:
2129:
1084:, localization of eigenstates, etc., were used as tests of pseudorandom generators.
2170:
2107:
2006:
1901:
1093:
1025:
1010:
39:
2151:
2025:
1920:
1543:
1172:
1024:
shows that cryptographically secure pseudorandom generators exist if and only if
1044:
in a way that the cipher text provides no information on the plaintext, the key
2067:
2045:
1905:
2208:
1860:
1818:
1234:
1226:
1054:
1037:
1979:
1229:
provided a candidate pseudorandom generator with these properties. In 1997
1096:
to test whether a pseudorandom generator produces high quality random bits.
2011:
1994:
1014:
963:
51:
31:
2111:
1171:
A fundamental question in computational complexity theory is whether all
1097:
1077:
1073:
177:
47:
2174:
2193:
1340:
1222:
165:
164:
that the pseudorandom generator will try to fool, and they are usually
1786:{\displaystyle \ell =d\cdot \log n+O(2^{d}\cdot \log(\epsilon ^{-1}))}
945:
2192:
This article incorporates material from
Pseudorandom generator on
153:{\displaystyle {\mathcal {A}}=\{A:\{0,1\}^{n}\to \{0,1\}^{*}\}}
2153:
1980:"Statistical Testing Techniques for Pseudorandom generation"
1462:. This result was improved by William Hoza in 2021 to space
1068:, which generalizes the notion of a pseudorandom generator.
16:
Term used in theoretical computer science and cryptography
1887:
1801:
1000:
cryptographically secure pseudorandom generators (CSPRGs)
609:
A pseudorandom generator against a family of adversaries
1258:
is the class of machines whose work space is bounded by
654:{\displaystyle ({\mathcal {A}}_{n})_{n\in \mathbb {N} }}
1542:
When the statistical tests consist of all multivariate
817:{\displaystyle G_{n}:\{0,1\}^{\ell (n)}\to \{0,1\}^{n}}
176:. The notation in the codomain of the functions is the
1060:
Pseudorandom generators may also be used to construct
1040:. It is well known that in order to encrypt a message
958:
Cryptographically secure pseudorandom number generator
1711:
1691:
1671:
1585:
1555:
1521:{\displaystyle O(\log ^{1.5}n/{\sqrt {\log \log n}})}
1468:
1426:
1391:
1349:
1303:
1264:
1139:
1115:
972:
922:
890:
861:
830:
744:
696:
667:
615:
582:
558:
516:
485:
465:
429:
384:
356:
336:
316:
289:
259:
189:
80:
1919:
Katz, Jonathan; Lindell, Yehuda (20 December 2020).
1890:"A Pseudorandom Generator from any One-way Function"
1641:{\displaystyle \ell =\log n+O(\log(\epsilon ^{-1}))}
1993:Razborov, Alexander; Rudich, Steven (August 1997).
1241:that can be computed in time 2 on inputs of length
2050:Computational Complexity: A Conceptual Perspective
1947:
1785:
1697:
1685:small-bias generators fools polynomials of degree
1677:
1640:
1563:
1520:
1454:
1412:
1377:
1331:
1285:
1149:
1125:
982:
932:
905:
876:
847:
816:
730:
682:
653:
594:
564:
541:
498:
471:
451:
415:
366:
342:
322:
299:
271:
245:
168:. Sometimes the statistical tests are also called
152:
1845:. Lindell, Yehuda (Second ed.). Boca Raton.
160:be a class of functions. These functions are the
2206:
2198:Creative Commons Attribution/Share-Alike License
246:{\displaystyle G:\{0,1\}^{\ell }\to \{0,1\}^{n}}
1992:
1796:
1807:
805:
792:
771:
758:
530:
517:
234:
221:
209:
196:
147:
138:
125:
113:
100:
91:
2027:Computational Complexity: A Modern Approach
1918:
1293:. Using a repeated squaring trick known as
731:{\displaystyle (G_{n})_{n\in \mathbb {N} }}
1873:: CS1 maint: location missing publisher (
2164:
2101:
2010:
1557:
722:
645:
2089:
2072:Foundations of Cryptography: Basic Tools
1576:
1252:
1999:Journal of Computer and System Sciences
1945:
1658:Pseudorandom generators for polynomials
1531:
690:is a family of pseudorandom generators
2207:
1166:
1103:
1057:are based on pseudorandom generators.
2149:
1662:
1837:
824:is a pseudorandom generator against
1922:Introduction to Modern Cryptography
1843:Introduction to modern cryptography
62:(unproven) circuit lower bounds in
13:
1804:that produce a single output bit.
1651:
1142:
1118:
975:
951:
925:
848:{\displaystyle {\mathcal {A}}_{n}}
834:
622:
359:
292:
83:
14:
2236:
916:In most applications, the family
1161:
1455:{\displaystyle O(\log ^{1.5}n)}
1206:and output a single bit, where
877:{\displaystyle \varepsilon (n)}
683:{\displaystyle \varepsilon (n)}
606:of the pseudorandom generator.
416:{\displaystyle A(G(U_{\ell }))}
64:computational complexity theory
2215:Algorithmic information theory
2196:, which is licensed under the
2024:Sanjeev Arora and Boaz Barak,
1986:
1972:
1954:. Wolfram Media, Inc. p.
1939:
1912:
1881:
1831:
1780:
1777:
1761:
1739:
1665:proves that taking the sum of
1635:
1632:
1616:
1607:
1515:
1472:
1449:
1430:
1407:
1395:
1372:
1353:
1326:
1307:
1280:
1268:
1150:{\displaystyle {\mathcal {A}}}
1126:{\displaystyle {\mathcal {A}}}
1022:pseudorandom generator theorem
983:{\displaystyle {\mathcal {A}}}
933:{\displaystyle {\mathcal {A}}}
900:
894:
871:
865:
789:
784:
778:
711:
697:
677:
671:
634:
616:
446:
433:
410:
407:
394:
388:
367:{\displaystyle {\mathcal {A}}}
300:{\displaystyle {\mathcal {A}}}
218:
122:
1:
2141:: CS1 maint: date and year (
1824:
1378:{\displaystyle O(\log ^{2}n)}
1332:{\displaystyle O(\log ^{2}n)}
69:
21:Pseudorandom number generator
1564:{\displaystyle \mathbb {F} }
1066:pseudorandom function family
472:{\displaystyle \varepsilon }
323:{\displaystyle \varepsilon }
36:pseudorandom generator (PRG)
28:theoretical computer science
7:
1797:For constant-depth circuits
1202:) whose inputs have length
1062:symmetric key cryptosystems
542:{\displaystyle \{0,1\}^{k}}
10:
2241:
2076:Cambridge University Press
2054:Cambridge University Press
2032:Cambridge University Press
1925:. CRC Press. p. 262.
1808:Limitations on probability
1655:
1579:achieves a seed length of
1535:
1087:
1053:. Common constructions of
955:
378:between the distributions
272:{\displaystyle \ell <n}
18:
1946:Wolfram, Stephen (2002).
1906:10.1137/S0097539793244708
1894:SIAM Journal on Computing
1573:epsilon-biased generators
1413:{\displaystyle O(\log n)}
1286:{\displaystyle O(\log n)}
996:polynomial-time algorithm
1194:of all circuits of size
1092:NIST announced SP800-22
990:usually consists of all
906:{\displaystyle \ell (n)}
452:{\displaystyle A(U_{n})}
1802:Constant depth circuits
1538:small-bias sample space
1031:
595:{\displaystyle n-\ell }
44:deterministic procedure
2012:10.1006/jcss.1997.1494
1787:
1699:
1679:
1642:
1577:Naor & Naor (1990)
1575:. The construction of
1565:
1522:
1456:
1414:
1379:
1333:
1287:
1151:
1127:
984:
934:
907:
878:
849:
818:
732:
684:
655:
596:
566:
543:
500:
473:
453:
417:
368:
344:
324:
301:
281:pseudorandom generator
273:
247:
154:
2112:10.1145/100216.100244
1950:A New Kind of Science
1788:
1705:. The seed length is
1700:
1680:
1643:
1566:
1523:
1457:
1415:
1380:
1334:
1288:
1253:For logarithmic space
1218:) and its bias is â…“.
1176:randomized algorithms
1152:
1128:
1082:correlation functions
985:
935:
908:
879:
850:
819:
733:
685:
656:
597:
567:
565:{\displaystyle \ell }
544:
501:
499:{\displaystyle U_{k}}
474:
454:
418:
369:
345:
325:
302:
274:
248:
155:
2159:. pp. 124–127.
2096:, pp. 213–223,
1709:
1689:
1669:
1583:
1553:
1532:For linear functions
1466:
1424:
1389:
1347:
1301:
1262:
1137:
1113:
970:
942:model of computation
920:
888:
859:
828:
742:
694:
665:
613:
580:
556:
514:
508:uniform distribution
483:
463:
427:
382:
376:statistical distance
354:
334:
314:
287:
257:
187:
78:
56:uniform distribution
2175:10.1109/CCC.2008.16
1231:Russell Impagliazzo
1167:For polynomial time
1104:For derandomization
52:pseudorandom string
1815:circuit complexity
1783:
1695:
1675:
1638:
1561:
1518:
1452:
1410:
1375:
1329:
1283:
1147:
1123:
980:
930:
903:
874:
845:
814:
728:
680:
651:
592:
562:
539:
496:
469:
449:
413:
364:
340:
320:
297:
269:
243:
150:
2184:978-0-7695-3169-4
2062:978-0-521-88473-0
1965:978-1-57955-008-0
1932:978-1-351-13302-9
1698:{\displaystyle d}
1678:{\displaystyle d}
1513:
1295:Savitch's theorem
1180:decision problems
1051:semantic security
1026:one-way functions
576:and the quantity
343:{\displaystyle A}
162:statistical tests
40:statistical tests
2232:
2220:Pseudorandomness
2188:
2168:
2158:
2146:
2140:
2132:
2105:
2017:
2016:
2014:
1995:"Natural Proofs"
1990:
1984:
1983:
1976:
1970:
1969:
1953:
1943:
1937:
1936:
1916:
1910:
1909:
1900:(4): 1364–1396.
1885:
1879:
1878:
1872:
1864:
1835:
1792:
1790:
1789:
1784:
1776:
1775:
1751:
1750:
1704:
1702:
1701:
1696:
1684:
1682:
1681:
1676:
1647:
1645:
1644:
1639:
1631:
1630:
1571:, one speaks of
1570:
1568:
1567:
1562:
1560:
1544:linear functions
1527:
1525:
1524:
1519:
1514:
1497:
1495:
1484:
1483:
1461:
1459:
1458:
1453:
1442:
1441:
1419:
1417:
1416:
1411:
1384:
1382:
1381:
1376:
1365:
1364:
1338:
1336:
1335:
1330:
1319:
1318:
1292:
1290:
1289:
1284:
1239:decision problem
1156:
1154:
1153:
1148:
1146:
1145:
1132:
1130:
1129:
1124:
1122:
1121:
1094:Randomness tests
1011:one-way function
989:
987:
986:
981:
979:
978:
940:represents some
939:
937:
936:
931:
929:
928:
912:
910:
909:
904:
884:and seed length
883:
881:
880:
875:
854:
852:
851:
846:
844:
843:
838:
837:
823:
821:
820:
815:
813:
812:
788:
787:
754:
753:
737:
735:
734:
729:
727:
726:
725:
709:
708:
689:
687:
686:
681:
660:
658:
657:
652:
650:
649:
648:
632:
631:
626:
625:
601:
599:
598:
593:
571:
569:
568:
563:
548:
546:
545:
540:
538:
537:
505:
503:
502:
497:
495:
494:
478:
476:
475:
470:
458:
456:
455:
450:
445:
444:
422:
420:
419:
414:
406:
405:
373:
371:
370:
365:
363:
362:
349:
347:
346:
341:
329:
327:
326:
321:
306:
304:
303:
298:
296:
295:
278:
276:
275:
270:
252:
250:
249:
244:
242:
241:
217:
216:
159:
157:
156:
151:
146:
145:
121:
120:
87:
86:
2240:
2239:
2235:
2234:
2233:
2231:
2230:
2229:
2205:
2204:
2185:
2166:10.1.1.220.1554
2156:
2134:
2133:
2122:
2103:10.1.1.421.2784
2021:
2020:
1991:
1987:
1978:
1977:
1973:
1966:
1944:
1940:
1933:
1917:
1913:
1886:
1882:
1866:
1865:
1853:
1836:
1832:
1827:
1810:
1799:
1768:
1764:
1746:
1742:
1710:
1707:
1706:
1690:
1687:
1686:
1670:
1667:
1666:
1660:
1654:
1652:For polynomials
1623:
1619:
1584:
1581:
1580:
1556:
1554:
1551:
1550:
1540:
1534:
1496:
1491:
1479:
1475:
1467:
1464:
1463:
1437:
1433:
1425:
1422:
1421:
1390:
1387:
1386:
1385:that fools all
1360:
1356:
1348:
1345:
1344:
1314:
1310:
1302:
1299:
1298:
1263:
1260:
1259:
1255:
1173:polynomial time
1169:
1164:
1141:
1140:
1138:
1135:
1134:
1117:
1116:
1114:
1111:
1110:
1106:
1090:
1034:
974:
973:
971:
968:
967:
960:
954:
952:In cryptography
944:or some set of
924:
923:
921:
918:
917:
889:
886:
885:
860:
857:
856:
839:
833:
832:
831:
829:
826:
825:
808:
804:
774:
770:
749:
745:
743:
740:
739:
721:
714:
710:
704:
700:
695:
692:
691:
666:
663:
662:
644:
637:
633:
627:
621:
620:
619:
614:
611:
610:
581:
578:
577:
557:
554:
553:
533:
529:
515:
512:
511:
490:
486:
484:
481:
480:
464:
461:
460:
440:
436:
428:
425:
424:
401:
397:
383:
380:
379:
358:
357:
355:
352:
351:
335:
332:
331:
315:
312:
311:
291:
290:
288:
285:
284:
258:
255:
254:
237:
233:
212:
208:
188:
185:
184:
141:
137:
116:
112:
82:
81:
79:
76:
75:
72:
38:for a class of
24:
17:
12:
11:
5:
2238:
2228:
2227:
2222:
2217:
2203:
2202:
2189:
2183:
2147:
2121:978-0897913614
2120:
2087:
2068:Oded Goldreich
2065:
2046:Oded Goldreich
2043:
2019:
2018:
1985:
1971:
1964:
1938:
1931:
1911:
1880:
1851:
1841:(2014-11-06).
1839:Katz, Jonathan
1829:
1828:
1826:
1823:
1819:natural proofs
1809:
1806:
1798:
1795:
1782:
1779:
1774:
1771:
1767:
1763:
1760:
1757:
1754:
1749:
1745:
1741:
1738:
1735:
1732:
1729:
1726:
1723:
1720:
1717:
1714:
1694:
1674:
1656:Main article:
1653:
1650:
1637:
1634:
1629:
1626:
1622:
1618:
1615:
1612:
1609:
1606:
1603:
1600:
1597:
1594:
1591:
1588:
1559:
1536:Main article:
1533:
1530:
1517:
1512:
1509:
1506:
1503:
1500:
1494:
1490:
1487:
1482:
1478:
1474:
1471:
1451:
1448:
1445:
1440:
1436:
1432:
1429:
1409:
1406:
1403:
1400:
1397:
1394:
1374:
1371:
1368:
1363:
1359:
1355:
1352:
1328:
1325:
1322:
1317:
1313:
1309:
1306:
1282:
1279:
1276:
1273:
1270:
1267:
1254:
1251:
1168:
1165:
1163:
1160:
1144:
1120:
1105:
1102:
1089:
1086:
1055:stream ciphers
1033:
1030:
977:
956:Main article:
953:
950:
927:
902:
899:
896:
893:
873:
870:
867:
864:
842:
836:
811:
807:
803:
800:
797:
794:
791:
786:
783:
780:
777:
773:
769:
766:
763:
760:
757:
752:
748:
724:
720:
717:
713:
707:
703:
699:
679:
676:
673:
670:
647:
643:
640:
636:
630:
624:
618:
602:is called the
591:
588:
585:
572:is called the
561:
536:
532:
528:
525:
522:
519:
493:
489:
468:
448:
443:
439:
435:
432:
412:
409:
404:
400:
396:
393:
390:
387:
361:
339:
330:if, for every
319:
294:
268:
265:
262:
240:
236:
232:
229:
226:
223:
220:
215:
211:
207:
204:
201:
198:
195:
192:
174:distinguishers
149:
144:
140:
136:
133:
130:
127:
124:
119:
115:
111:
108:
105:
102:
99:
96:
93:
90:
85:
71:
68:
15:
9:
6:
4:
3:
2:
2237:
2226:
2223:
2221:
2218:
2216:
2213:
2212:
2210:
2201:
2199:
2195:
2190:
2186:
2180:
2176:
2172:
2167:
2162:
2155:
2154:
2148:
2144:
2138:
2131:
2127:
2123:
2117:
2113:
2109:
2104:
2099:
2095:
2094:
2088:
2085:
2084:9780521791724
2081:
2077:
2073:
2069:
2066:
2063:
2059:
2055:
2051:
2047:
2044:
2041:
2040:9780521424264
2037:
2033:
2029:
2028:
2023:
2022:
2013:
2008:
2004:
2000:
1996:
1989:
1981:
1975:
1967:
1961:
1957:
1952:
1951:
1942:
1934:
1928:
1924:
1923:
1915:
1907:
1903:
1899:
1895:
1891:
1884:
1876:
1870:
1862:
1858:
1854:
1852:9781466570269
1848:
1844:
1840:
1834:
1830:
1822:
1820:
1816:
1805:
1803:
1794:
1772:
1769:
1765:
1758:
1755:
1752:
1747:
1743:
1736:
1733:
1730:
1727:
1724:
1721:
1718:
1715:
1712:
1692:
1672:
1664:
1659:
1649:
1627:
1624:
1620:
1613:
1610:
1604:
1601:
1598:
1595:
1592:
1589:
1586:
1578:
1574:
1549:
1545:
1539:
1529:
1510:
1507:
1504:
1501:
1498:
1492:
1488:
1485:
1480:
1476:
1469:
1446:
1443:
1438:
1434:
1427:
1404:
1401:
1398:
1392:
1369:
1366:
1361:
1357:
1350:
1342:
1323:
1320:
1315:
1311:
1304:
1296:
1277:
1274:
1271:
1265:
1250:
1248:
1245:but requires
1244:
1240:
1236:
1235:Avi Wigderson
1232:
1228:
1227:Avi Wigderson
1224:
1219:
1217:
1213:
1209:
1205:
1201:
1197:
1193:
1189:
1185:
1181:
1177:
1174:
1162:Constructions
1159:
1101:
1099:
1095:
1085:
1083:
1079:
1075:
1069:
1067:
1063:
1058:
1056:
1052:
1047:
1043:
1039:
1038:one-time pads
1029:
1027:
1023:
1018:
1016:
1012:
1008:
1003:
1001:
997:
993:
965:
959:
949:
947:
943:
914:
897:
891:
868:
862:
840:
809:
801:
798:
795:
781:
775:
767:
764:
761:
755:
750:
746:
718:
715:
705:
701:
674:
668:
641:
638:
628:
607:
605:
589:
586:
583:
575:
559:
552:The quantity
550:
534:
526:
523:
520:
509:
491:
487:
466:
441:
437:
430:
402:
398:
391:
385:
377:
337:
317:
310:
282:
266:
263:
260:
238:
230:
227:
224:
213:
205:
202:
199:
193:
190:
181:
179:
175:
171:
167:
163:
142:
134:
131:
128:
117:
109:
106:
103:
97:
94:
88:
67:
65:
59:
57:
53:
49:
45:
41:
37:
33:
29:
22:
2225:Cryptography
2191:
2152:
2092:
2071:
2049:
2026:
2005:(1): 24–35.
2002:
1998:
1988:
1974:
1949:
1941:
1921:
1914:
1897:
1893:
1883:
1842:
1833:
1811:
1800:
1663:Viola (2008)
1661:
1548:finite field
1541:
1256:
1242:
1220:
1215:
1211:
1207:
1203:
1199:
1195:
1191:
1187:
1183:
1170:
1107:
1091:
1078:random walks
1070:
1059:
1045:
1041:
1035:
1019:
1015:cryptography
1004:
999:
966:, the class
964:cryptography
961:
915:
608:
603:
573:
551:
308:
280:
182:
173:
169:
161:
73:
60:
50:to a longer
46:that maps a
35:
32:cryptography
25:
1249:of size 2.
1098:Yongge Wang
1074:Ising model
574:seed length
459:is at most
183:A function
178:Kleene star
170:adversaries
48:random seed
2209:Categories
2194:PlanetMath
1825:References
1546:over some
1341:Noam Nisan
1223:Noam Nisan
946:algorithms
855:with bias
661:with bias
166:algorithms
70:Definition
2161:CiteSeerX
2098:CiteSeerX
1869:cite book
1861:893721520
1770:−
1766:ϵ
1759:
1753:⋅
1728:
1722:⋅
1713:ℓ
1625:−
1621:ϵ
1614:
1596:
1587:ℓ
1508:
1502:
1486:
1444:
1402:
1367:
1321:
1275:
1221:In 1991,
892:ℓ
863:ε
790:→
776:ℓ
719:∈
669:ε
642:∈
590:ℓ
587:−
560:ℓ
467:ε
403:ℓ
318:ε
261:ℓ
219:→
214:ℓ
143:∗
123:→
2137:citation
2130:14031194
2078:(2001),
2056:(2008),
2034:(2009),
1247:circuits
992:circuits
738:, where
479:, where
283:against
1088:Testing
1028:exist.
604:stretch
506:is the
2181:
2163:
2128:
2118:
2100:
2082:
2060:
2038:
1962:
1929:
1859:
1849:
1007:P ≠NP
374:, the
2157:(PDF)
2126:S2CID
307:with
279:is a
253:with
42:is a
2179:ISBN
2143:link
2116:ISBN
2080:ISBN
2058:ISBN
2036:ISBN
1960:ISBN
1956:1085
1927:ISBN
1875:link
1857:OCLC
1847:ISBN
1233:and
1225:and
1178:for
1032:Uses
1020:The
423:and
309:bias
264:<
74:Let
34:, a
30:and
2171:doi
2108:doi
2007:doi
1902:doi
1756:log
1725:log
1611:log
1593:log
1505:log
1499:log
1481:1.5
1477:log
1439:1.5
1435:log
1399:log
1358:log
1312:log
1272:log
1184:BPP
962:In
510:on
350:in
172:or
26:In
2211::
2177:.
2169:.
2139:}}
2135:{{
2124:,
2114:,
2106:,
2074:,
2070:,
2052:,
2048:,
2030:,
2003:55
2001:.
1997:.
1958:.
1898:28
1896:.
1892:.
1871:}}
1867:{{
1855:.
1793:.
1528:.
1339:.
1186:=
1080:,
1017:.
1002:.
913:.
549:.
180:.
58:.
2200:.
2187:.
2173::
2145:)
2110::
2086:.
2064:.
2042:.
2015:.
2009::
1982:.
1968:.
1935:.
1908:.
1904::
1877:)
1863:.
1781:)
1778:)
1773:1
1762:(
1748:d
1744:2
1740:(
1737:O
1734:+
1731:n
1719:d
1716:=
1693:d
1673:d
1636:)
1633:)
1628:1
1617:(
1608:(
1605:O
1602:+
1599:n
1590:=
1558:F
1516:)
1511:n
1493:/
1489:n
1473:(
1470:O
1450:)
1447:n
1431:(
1428:O
1408:)
1405:n
1396:(
1393:O
1373:)
1370:n
1362:2
1354:(
1351:O
1327:)
1324:n
1316:2
1308:(
1305:O
1281:)
1278:n
1269:(
1266:O
1243:n
1216:n
1212:n
1210:(
1208:s
1204:n
1200:n
1198:(
1196:s
1192:F
1188:P
1143:A
1119:A
1046:k
1042:m
976:A
926:A
901:)
898:n
895:(
872:)
869:n
866:(
841:n
835:A
810:n
806:}
802:1
799:,
796:0
793:{
785:)
782:n
779:(
772:}
768:1
765:,
762:0
759:{
756::
751:n
747:G
723:N
716:n
712:)
706:n
702:G
698:(
678:)
675:n
672:(
646:N
639:n
635:)
629:n
623:A
617:(
584:n
535:k
531:}
527:1
524:,
521:0
518:{
492:k
488:U
447:)
442:n
438:U
434:(
431:A
411:)
408:)
399:U
395:(
392:G
389:(
386:A
360:A
338:A
293:A
267:n
239:n
235:}
231:1
228:,
225:0
222:{
210:}
206:1
203:,
200:0
197:{
194::
191:G
148:}
139:}
135:1
132:,
129:0
126:{
118:n
114:}
110:1
107:,
104:0
101:{
98::
95:A
92:{
89:=
84:A
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.