NDLI: A Simple Unpredictable Pseudo-Random Number Generator

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Blum, L. Blum, M. Shub, M.
Copyright Year	1986
Abstract	Two closely-related pseudo-random sequence generators are presented: The ${1 / P}$generator, with input P a prime, outputs the quotient digits obtained on dividing 1 by P. The $x^2 \bmod N$generator with inputs N, $x_0 $ (where $N = P \cdot Q$ is a product of distinct primes, each congruent to 3 mod 4, and $x_0 $ is a quadratic residue $\bmod N$), outputs $b_0 b_1 b_2 \cdots $ where $b_i = {\operatorname{parity}}(x_i )$ and $x_{i + 1} = x_i^2 \bmod N$.From short seeds each generator efficiently produces long well-distributed sequences. Moreover, both generators have computationally hard problems at their core. The first generators sequences, however, are completely predictable (from any small segment of $2\|P\| + 1$ consecutive digits one can infer the seed, P, and continue the sequence backwards and forwards), whereas the second, under a certain intractability assumption, is unpredictable in a precise sense. The second generator has additional interesting properties: from knowledge of $x_0 $ and N but notP or Q, one can generate the sequence forwards, but, under the above-mentioned intractability assumption, one can not generate the sequence backwards. From the additional knowledge of P and Q, one can generate the sequence backwards; one can even jump about from any point in the sequence to any other. Because of these properties, the $x^2 \bmod N$generator promises many interesting applications, e.g., to public-key cryptography. To use these generators in practice, an analysis is needed of various properties of these sequences such as their periods. This analysis is begun here.
Starting Page	364
Ending Page	383
Page Count	20
File Format	PDF
ISSN	00975397
DOI	10.1137/0215025
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	2
Volume Number	15
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2006-07-13
Access Restriction	Subscribed
Subject Keyword	quadratic residuacity random Monte Carlo one-time pad pseudo-random cryptography Jacobi symbol secure transactions computational complexity public-key encryption
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Jacobi symbol are harder to predict than legendre symbol in sylar encryption system.

Design of a New Cryptography Algorithm using Reseeding-Mixing Pseudo Random Number Generator

Pseudorandom Functions and Factoring

The Discrete Logarithm Hides $O(\log n)$ Bits

Chain Rule Protection over the Internet Using PUGGAD Algorithm

A note on Yao’s theorem about pseudo-random generators

Steganography using Cryptography and Pseudo Random Numbers

Linear complexity of Legendre-polynomial quotients

Parallel Monte Carlo methods for derivative security pricing (2000)

A Simple Unpredictable Pseudo-Random Number Generator

Similar Documents

Jacobi symbol are harder to predict than legendre symbol in sylar encryption system.

Design of a New Cryptography Algorithm using Reseeding-Mixing Pseudo Random Number Generator

Pseudorandom Functions and Factoring

The Discrete Logarithm Hides $O(\log n)$ Bits

Chain Rule Protection over the Internet Using PUGGAD Algorithm

A note on Yao’s theorem about pseudo-random generators

Steganography using Cryptography and Pseudo Random Numbers

Linear complexity of Legendre-polynomial quotients

Parallel Monte Carlo methods for derivative security pricing (2000)

A Simple Unpredictable Pseudo-Random Number Generator