**University Lecture Series**

Volume: 55;
2010;
114 pp;
Softcover

MSC: Primary 68;

Print ISBN: 978-0-8218-5192-0

Product Code: ULECT/55

List Price: $38.00

AMS Member Price: $30.40

MAA Member Price: $34.20

**Electronic ISBN: 978-1-4704-1650-8
Product Code: ULECT/55.E**

List Price: $38.00

AMS Member Price: $30.40

MAA Member Price: $34.20

#### You may also like

#### Supplemental Materials

# A Primer on Pseudorandom Generators

Share this page
*Oded Goldreich*

A fresh look at the question of randomness was taken in the theory of
computing: A distribution is pseudorandom if it cannot be
distinguished from the uniform distribution by any efficient
procedure. This paradigm, originally associating efficient procedures
with polynomial-time algorithms, has been applied with respect to a
variety of natural classes of distinguishing procedures. The resulting
theory of pseudorandomness is relevant to science at large and is
closely related to central areas of computer science, such as
algorithmic design, complexity theory, and cryptography.

This primer surveys the theory of pseudorandomness, starting with
the general paradigm, and discussing various incarnations while
emphasizing the case of general-purpose pseudorandom generators
(withstanding any polynomial-time distinguisher). Additional topics
include the “derandomization” of arbitrary probabilistic
polynomial-time algorithms, pseudorandom generators withstanding
space-bounded distinguishers, and several natural notions of
special-purpose pseudorandom generators.

The primer assumes basic familiarity with the notion of efficient
algorithms and with elementary probability theory, but provides a
basic introduction to all notions that are actually used. As a
result, the primer is essentially self-contained, although the
interested reader is at times referred to other sources for more
detail.

#### Readership

Advanced undergraduates and computer science majors, graduate students, and research mathematicians interested in complexity theory; cryptography; and pseudorandom generators.

#### Reviews & Endorsements

This book provides basic information about pseudorandom generators, one of the topics with the strongest impact in recent years, not only because of the subject itself but also because of its many applications in all fields of science.

-- Luis Hernandez Encinas, Mathematical Reviews

#### Table of Contents

# Table of Contents

## A Primer on Pseudorandom Generators

- Cover Cover11 free
- Title page iii4 free
- Contents v6 free
- Preface ix10 free
- Introduction 112 free
- General-purpose pseudorandom generators 1122 free
- Derandomization of time-complexity classes 3546
- Space-bounded distinguishers 4758
- Special purpose generators 5970
- Concluding remarks 7788
- Hashing functions 7990
- On randomness extractors 8394
- A generic hard-core predicate 89100
- Using randomness in computation 93104
- Cryptographic applications of pseudorandom functions 99110
- Some basic complexity classes 103114
- Bibliography 107118
- Index 113124 free
- Back Cover Back Cover1130