Share
VIDEOS 1 TO 50
Pseudorandom number generators | Computer Science | Khan Academy
Pseudorandom number generators | Computer Science | Khan Academy
Published: 2014/04/28
Channel: Khan Academy Labs
How to Generate Pseudorandom Numbers | Infinite Series
How to Generate Pseudorandom Numbers | Infinite Series
Published: 2017/10/13
Channel: PBS Infinite Series
Pseudorandomness - Exponential sums, equidistribution and pseudo-randomness - Jean Bourgain
Pseudorandomness - Exponential sums, equidistribution and pseudo-randomness - Jean Bourgain
Published: 2016/09/02
Channel: Institute for Advanced Study
cryptography - Pseudorandomness
cryptography - Pseudorandomness
Published: 2016/08/31
Channel: intrigano
Pseudorandom Generators I
Pseudorandom Generators I
Published: 2017/01/19
Channel: Simons Institute
Fundamental Techniques in Pseudorandomness I
Fundamental Techniques in Pseudorandomness I
Published: 2017/01/17
Channel: Simons Institute
Pseudorandom Generators from Polarizing Random Walks
Pseudorandom Generators from Polarizing Random Walks
Published: 2018/09/10
Channel: Simons Institute
Pseudorandomness in Data Structures
Pseudorandomness in Data Structures
Published: 2017/03/06
Channel: Simons Institute
Fundamental Techniques in Pseudorandomness V
Fundamental Techniques in Pseudorandomness V
Published: 2017/02/08
Channel: Simons Institute
Pseudorandomness When the Odds Are Against You
Pseudorandomness When the Odds Are Against You
Published: 2017/02/03
Channel: Simons Institute
Arithmetic Applications of Pseudorandomness I
Arithmetic Applications of Pseudorandomness I
Published: 2017/01/18
Channel: Simons Institute
Packing Degenerate Graphs Using Pseudorandomness
Packing Degenerate Graphs Using Pseudorandomness
Published: 2017/03/06
Channel: Simons Institute
Pseudorandomness and Regularity in Graphs I
Pseudorandomness and Regularity in Graphs I
Published: 2017/01/17
Channel: Simons Institute
Linear-Algebraic Pseudorandomness: Subspace Designs and Dimension Expanders
Linear-Algebraic Pseudorandomness: Subspace Designs and Dimension Expanders
Published: 2017/03/09
Channel: Simons Institute
Fundamental Techniques in Pseudorandomness II
Fundamental Techniques in Pseudorandomness II
Published: 2017/01/17
Channel: Simons Institute
Gambling with Secrets: Part 6/8 (Perfect Secrecy & Pseudorandomness)
Gambling with Secrets: Part 6/8 (Perfect Secrecy & Pseudorandomness)
Published: 2012/05/04
Channel: Art of the Problem
Pseudorandomness and Regularity in Graphs II
Pseudorandomness and Regularity in Graphs II
Published: 2017/01/19
Channel: Simons Institute
Fundamental Techniques in Pseudorandomness IV
Fundamental Techniques in Pseudorandomness IV
Published: 2017/01/18
Channel: Simons Institute
4.3 Pseudo-Randomness
4.3 Pseudo-Randomness
Published: 2018/08/20
Channel: Complexity Explorer
Fundamental Techniques in Pseudorandomness III
Fundamental Techniques in Pseudorandomness III
Published: 2017/01/18
Channel: Simons Institute
Pseudo-Randomness in JavaScript - Wes Chow, CTO of Chartbeat
Pseudo-Randomness in JavaScript - Wes Chow, CTO of Chartbeat
Published: 2014/10/10
Channel: Hakka Labs
cryptography - Pseudorandom Generators
cryptography - Pseudorandom Generators
Published: 2016/08/31
Channel: intrigano
Arithmetic Applications of Pseudorandomness II
Arithmetic Applications of Pseudorandomness II
Published: 2017/01/19
Channel: Simons Institute
Pseudorandomness - Substitution sequences at primes - Peter Sarnak
Pseudorandomness - Substitution sequences at primes - Peter Sarnak
Published: 2016/09/02
Channel: Institute for Advanced Study
Pseudorandomness when the odds are against you - Ronen Shaltiel
Pseudorandomness when the odds are against you - Ronen Shaltiel
Published: 2016/10/12
Channel: Institute for Advanced Study
Pseudorandom 01: Hand Drawn PCBs
Pseudorandom 01: Hand Drawn PCBs
Published: 2016/03/23
Channel: Adafruit Industries
Pseudorandomness
Pseudorandomness
Published: 2012/05/17
Channel: nptelhrd
Randomness and Pseudo-randomness - Avi Wigderson
Randomness and Pseudo-randomness - Avi Wigderson
Published: 2016/03/02
Channel: Institute for Advanced Study
IPAM: Avi Wigderson - "Randomness and Pseudorandomness"
IPAM: Avi Wigderson - "Randomness and Pseudorandomness"
Published: 2014/06/10
Channel: Institute for Pure & Applied Mathematics (IPAM)
Section 4.5 Pseudorandom Numbers
Section 4.5 Pseudorandom Numbers
Published: 2017/10/06
Channel: Michael Venn
Pseudorandom Sequence
Pseudorandom Sequence
Published: 2017/01/09
Channel: Internetwork Security
Pseudorandom 04: Mechanical Keyboards
Pseudorandom 04: Mechanical Keyboards
Published: 2016/04/19
Channel: Adafruit Industries
Pseudorandomness and Regularity in Graphs IV
Pseudorandomness and Regularity in Graphs IV
Published: 2017/01/21
Channel: Simons Institute
Arithmetic Applications of Pseudorandomness III
Arithmetic Applications of Pseudorandomness III
Published: 2017/01/19
Channel: Simons Institute
The Uncanny Usefulness of Constructive Proofs of Pseudorandomness
The Uncanny Usefulness of Constructive Proofs of Pseudorandomness
Published: 2017/03/06
Channel: Simons Institute
Coding Math: Episode 51 - Pseudo Random Number Generators Part I
Coding Math: Episode 51 - Pseudo Random Number Generators Part I
Published: 2016/09/01
Channel: Coding Math
Pseudorandomness and Regularity in Graphs III
Pseudorandomness and Regularity in Graphs III
Published: 2017/01/19
Channel: Simons Institute
Pseudorandomness - Randomness extractors - Avi Wigderson
Pseudorandomness - Randomness extractors - Avi Wigderson
Published: 2016/09/02
Channel: Institute for Advanced Study
Pseudorandom 13: Chiptune
Pseudorandom 13: Chiptune
Published: 2016/08/10
Channel: Adafruit Industries
Threshold Functions: Approximation, Pseudorandomness and Learning
Threshold Functions: Approximation, Pseudorandomness and Learning
Published: 2016/08/17
Channel: Microsoft Research
Dr. Ken Perlin - Pseudo-randomness in procedurlal design
Dr. Ken Perlin - Pseudo-randomness in procedurlal design
Published: 2009/12/22
Channel: Rutgers University
Pseudorandom Generators III
Pseudorandom Generators III
Published: 2017/01/20
Channel: Simons Institute
Random and Pseudorandom (In Our Time)
Random and Pseudorandom (In Our Time)
Published: 2018/08/08
Channel: BBC Podcasts
Pseudorandom 05: Light to Sound
Pseudorandom 05: Light to Sound
Published: 2016/04/27
Channel: Adafruit Industries
Pseudorandom 10: Ferrofluid
Pseudorandom 10: Ferrofluid
Published: 2016/07/13
Channel: Adafruit Industries
Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas
Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas
Published: 2017/03/10
Channel: Simons Institute
Regularity Inheritance in Pseudorandom Graphs
Regularity Inheritance in Pseudorandom Graphs
Published: 2017/03/07
Channel: Simons Institute
PseudoRandom
PseudoRandom
Published: 2018/08/25
Channel: Pavana
Pseudorandom Generators IV
Pseudorandom Generators IV
Published: 2017/01/21
Channel: Simons Institute
CSE571-11-07: Pseudorandom Number Generation and Stream Ciphers
CSE571-11-07: Pseudorandom Number Generation and Stream Ciphers
Published: 2013/08/19
Channel: Raj Jain
NEXT
GO TO RESULTS [51 .. 100]

WIKIPEDIA ARTICLE

From Wikipedia, the free encyclopedia
  (Redirected from Pseudorandom)
Jump to navigation Jump to search

A pseudorandom process is a process that appears to be random but is not. Pseudorandom sequences typically exhibit statistical randomness while being generated by an entirely deterministic causal process. Such a process is easier to produce than a genuinely random one, and has the benefit that it can be used again and again to produce exactly the same numbers, which is useful for testing and fixing software.

To generate truly random numbers would require precise, accurate, and repeatable system measurements of absolutely non-deterministic processes. Linux uses, for example, various system timings (like user keystrokes, I/O, or least-significant digit voltage measurements) to produce a pool of random numbers. It attempts to constantly replenish the pool, depending on the level of importance, and so will issue a random number. This system is an example, and similar to those of dedicated hardware random number generators. Even with all of this work, it is not random.

History[edit]

The generation of random numbers has many uses (mostly in statistics, for random sampling, and simulation). Before modern computing, researchers requiring random numbers would either generate them through various means (dice, cards, roulette wheels,[1] etc.) or use existing random number tables.

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 L.H.C. Tippett. In 1947, the RAND Corporation generated numbers by the electronic simulation of a roulette wheel;[1] the results were eventually published in 1955 as A Million Random Digits with 100,000 Normal Deviates.

John von Neumann was a pioneer in computer-based random number generators. In 1949, Derrick Henry Lehmer invented the linear congruential generator, which was for a long time used in most pseudorandom number generators. Today, most generators in use are based on linear recurrence (for instance, the Xorshift family). With the spread of the use of computers, algorithmic pseudorandom number generators replaced random number tables, and "true" random number generators (hardware random number generators) are used in only a few cases.

Almost random[edit]

A pseudorandom variable is a variable which is created by a deterministic algorithm, often a computer program or subroutine, which in most cases takes random bits as input. The pseudorandom string will typically be longer than the original random string, but less random (less entropic in the information theory sense). This can be useful for randomized algorithms.

Pseudorandom number generators are widely used in such applications as computer modeling (e.g., Markov chains), statistics, experimental design, etc.

In computational complexity[edit]

In theoretical computer science, a distribution is pseudorandom against a class of adversaries if no adversary from the class can distinguish it from the uniform distribution with significant advantage.[2] This notion of pseudorandomness is studied in computational complexity theory and has applications to cryptography.

Formally, let S and T be finite sets and let F = {f: ST} be a class of functions. A distribution D over S is ε-pseudorandom against F if for every f in F, the statistical distance between the distributions f(X), where X is sampled from D, and f(Y), where Y is sampled from the uniform distribution on S, is at most ε.

In typical applications, the class F describes a model of computation with bounded resources and one is interested in designing distributions D with certain properties that are pseudorandom against F. The distribution D is often specified as the output of a pseudorandom generator.

Cryptography[edit]

Though random numbers are needed in cryptography, the use of pseudorandom number generators (whether hardware or software or some combination) is insecure. When random values are required in cryptography, the goal is to make a message as hard to crack as possible, by eliminating or obscuring the parameters used to encrypt the message (the key) from the message itself or from the context in which it is carried. Pseudorandom sequences are deterministic and reproducible; all that is required in order to discover and reproduce a pseudorandom sequence is the algorithm used to generate it and the initial seed. So the entire sequence of numbers is only as powerful as the randomly chosen parts - sometimes the algorithm and the seed, but usually only the seed.

There are many examples in cryptographic history of ciphers, otherwise excellent, in which random choices were not random enough and security was lost as a direct consequence. The World War II Japanese PURPLE cipher machine used for diplomatic communications is a good example. It was consistently broken throughout World War II, mostly because the "key values" used were insufficiently random. They had patterns, and those patterns made any intercepted traffic readily decryptable. Had the keys (i.e. the initial settings of the stepping switches in the machine) been made unpredictably (i.e. randomly), that traffic would have been much harder to break, and perhaps even secure in practice.[3]

Users and designers of cryptography are strongly cautioned to treat their randomness needs with the utmost care. Absolutely nothing has changed with the era of computerized cryptography, except that patterns in pseudorandom data are easier to discover than ever before. Randomness is, if anything, more important than ever.

In security[edit]

Since pseudorandom numbers are in fact deterministic, a given seed will always determine the same pseudorandom number. This attribute is used in security, in the form of rolling code to avoid replay attacks, in which a command would be intercepted to be used by a thief at a later time.[4] This is defeated using a pseudorandom number generator to generate a different key each time. Since the pseudorandom can be synchronized between the two systems, an intercepted key would not work a second time, since the interceptor cannot guess the next number from an intercepted number.

Monte Carlo method simulations[edit]

A Monte Carlo method simulation is defined as any method that utilizes sequences of random numbers to perform the simulation. Monte Carlo simulations are applied to many topics including quantum chromodynamics, cancer radiation therapy, traffic flow, stellar evolution and VLSI design. All these simulations require the use of random numbers and therefore pseudorandom number generators, which makes creating random-like numbers very important.

A simple example of how a computer would perform a Monte Carlo simulation is the calculation of π. If a square enclosed a circle and a point were randomly chosen inside the square the point would either lie inside the circle or outside it. If the process were repeated many times, the ratio of the random points that lie inside the circle to the total number of random points in the square would approximate the ratio of the area of the circle to the area of the square. From this we can estimate pi, as shown in the Python code below utilizing a SciPy package to generate pseudorandom numbers with the MT19937 algorithm. Note that this method is a computationally inefficient way to numerically approximate π.

import scipy
N=100000
x_array = scipy.random.rand(N) 
y_array = scipy.random.rand(N) 
# generate N pseudorandom independent x and y-values on interval [0,1)
N_qtr_circle = sum(x_array**2+y_array**2 < 1) 
# Number of pts within the quarter circle x^2 + y^2 < 1 centered at the origin with radius r=1. 
# True area of quarter circle is pi/4 and has N_qtr_circle points within it.
# True area of the square is 1 and has N points within it, hence we approximate pi with
pi_approx = 4*float(N_qtr_circle)/N # Typical values: 3.13756, 3.15156

See also[edit]

References[edit]

  1. ^ a b "A Million Random Digits | RAND". www.rand.org. Retrieved 2017-03-30. 
  2. ^ Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press. 2008.
  3. ^ Alberto-Perez. "How the U.S. Cracked Japan's 'Purple Encryption Machine' at the Dawn of World War II". io9. Retrieved 2017-03-30. 
  4. ^ Brain, M., "How Remote Entry Works", HowStuffWorks Auto Auto Basics. Retrieved July 8, 2018.

Further reading[edit]

External links[edit]

Disclaimer

None of the audio/visual content is hosted on this site. All media is embedded from other sites such as GoogleVideo, Wikipedia, YouTube etc. Therefore, this site has no control over the copyright issues of the streaming media.

All issues concerning copyright violations should be aimed at the sites hosting the material. This site does not host any of the streaming media and the owner has not uploaded any of the material to the video hosting servers. Anyone can find the same content on Google Video or YouTube by themselves.

The owner of this site cannot know which documentaries are in public domain, which has been uploaded to e.g. YouTube by the owner and which has been uploaded without permission. The copyright owner must contact the source if he wants his material off the Internet completely.

Powered by YouTube
Wikipedia content is licensed under the GFDL and (CC) license