An error was encountered while trying to add the item to the cart. Please try again.
Copy To Clipboard
Successfully Copied!
A Primer on Pseudorandom Generators

Oded Goldreich Weizmann Institute of Science, Rehovot, Israel
Available Formats:
Softcover ISBN: 978-0-8218-5192-0
Product Code: ULECT/55
List Price: $41.00 MAA Member Price:$36.90
AMS Member Price: $32.80 Electronic ISBN: 978-1-4704-1650-8 Product Code: ULECT/55.E List Price:$38.00
MAA Member Price: $34.20 AMS Member Price:$30.40
Bundle Print and Electronic Formats and Save!
This product is available for purchase as a bundle. Purchasing as a bundle enables you to save on the electronic version.
List Price: $61.50 MAA Member Price:$55.35
AMS Member Price: $49.20 Click above image for expanded view A Primer on Pseudorandom Generators Oded Goldreich Weizmann Institute of Science, Rehovot, Israel Available Formats:  Softcover ISBN: 978-0-8218-5192-0 Product Code: ULECT/55  List Price:$41.00 MAA Member Price: $36.90 AMS Member Price:$32.80
 Electronic ISBN: 978-1-4704-1650-8 Product Code: ULECT/55.E
 List Price: $38.00 MAA Member Price:$34.20 AMS Member Price: $30.40 Bundle Print and Electronic Formats and Save! This product is available for purchase as a bundle. Purchasing as a bundle enables you to save on the electronic version.  List Price:$61.50 MAA Member Price: $55.35 AMS Member Price:$49.20
• Book Details

University Lecture Series
Volume: 552010; 114 pp
MSC: Primary 68;

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.

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

• Chapters
• Chapter 1. Introduction
• Chapter 2. General-purpose pseudorandom generators
• Chapter 3. Derandomization of time-complexity classes
• Chapter 4. Space-bounded distinguishers
• Chapter 5. Special purpose generators
• Concluding remarks
• Appendix A. Hashing functions
• Appendix B. On randomness extractors
• Appendix C. A generic hard-core predicate
• Appendix D. Using randomness in computation
• Appendix E. Cryptographic applications of pseudorandom functions
• Appendix F. Some basic complexity classes

• Reviews

• 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
• Requests

Review Copy – for reviewers who would like to review an AMS book
Permission – for use of book, eBook, or Journal content
Accessibility – to request an alternate format of an AMS title
Volume: 552010; 114 pp
MSC: Primary 68;

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.

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

• Chapters
• Chapter 1. Introduction
• Chapter 2. General-purpose pseudorandom generators
• Chapter 3. Derandomization of time-complexity classes
• Chapter 4. Space-bounded distinguishers
• Chapter 5. Special purpose generators
• Concluding remarks
• Appendix A. Hashing functions
• Appendix B. On randomness extractors
• Appendix C. A generic hard-core predicate
• Appendix D. Using randomness in computation
• Appendix E. Cryptographic applications of pseudorandom functions
• Appendix F. Some basic complexity classes
• 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
Review Copy – for reviewers who would like to review an AMS book
Permission – for use of book, eBook, or Journal content
Accessibility – to request an alternate format of an AMS title
You may be interested in...
Please select which format for which you are requesting permissions.