Blum–Blum–Shub pseudorandom number generator
E118448
The Blum–Blum–Shub pseudorandom number generator is a cryptographically secure generator based on the hardness of factoring large composite numbers, widely studied in theoretical computer science and cryptography.
All labels observed (4)
| Label | Occurrences |
|---|---|
| Blum–Blum–Shub pseudorandom number generator canonical | 5 |
| Blum integer-based trapdoor permutations | 1 |
| Blum-Blum-Shub pseudorandom generator | 1 |
| Blum–Blum–Shub generator | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T990928 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: Blum–Blum–Shub pseudorandom number generator Context triple: [Manuel Blum, notableWork, Blum–Blum–Shub pseudorandom number generator]
-
A.
Blum–Micali pseudorandom number generator
The Blum–Micali pseudorandom number generator is a foundational cryptographic algorithm that produces provably secure pseudorandom bits based on number-theoretic hardness assumptions.
-
B.
Probabilistic Encryption
Probabilistic Encryption is a cryptographic technique that uses randomness in the encryption process so that the same message encrypts to different ciphertexts, enhancing security against attackers.
-
C.
New Directions in Cryptography
New Directions in Cryptography is a landmark 1976 paper that introduced the concepts of public-key cryptography and digital signatures, fundamentally reshaping modern cryptography and secure communications.
-
D.
Merkle puzzles
Merkle puzzles are an early cryptographic protocol that introduced the concept of public-key exchange by allowing two parties to establish a shared secret over an insecure channel using computationally asymmetric “puzzle” problems.
-
E.
Merkle–Damgård construction
The Merkle–Damgård construction is a fundamental method for building collision-resistant cryptographic hash functions from fixed-size compression functions, used in many classic hash algorithms like MD5 and SHA-1.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: Blum–Blum–Shub pseudorandom number generator Target entity description: The Blum–Blum–Shub pseudorandom number generator is a cryptographically secure generator based on the hardness of factoring large composite numbers, widely studied in theoretical computer science and cryptography.
-
A.
Blum–Micali pseudorandom number generator
The Blum–Micali pseudorandom number generator is a foundational cryptographic algorithm that produces provably secure pseudorandom bits based on number-theoretic hardness assumptions.
-
B.
Probabilistic Encryption
Probabilistic Encryption is a cryptographic technique that uses randomness in the encryption process so that the same message encrypts to different ciphertexts, enhancing security against attackers.
-
C.
New Directions in Cryptography
New Directions in Cryptography is a landmark 1976 paper that introduced the concepts of public-key cryptography and digital signatures, fundamentally reshaping modern cryptography and secure communications.
-
D.
Merkle puzzles
Merkle puzzles are an early cryptographic protocol that introduced the concept of public-key exchange by allowing two parties to establish a shared secret over an insecure channel using computationally asymmetric “puzzle” problems.
-
E.
Merkle–Damgård construction
The Merkle–Damgård construction is a fundamental method for building collision-resistant cryptographic hash functions from fixed-size compression functions, used in many classic hash algorithms like MD5 and SHA-1.
- F. None of above. chosen
Statements (46)
| Predicate | Object |
|---|---|
| instanceOf |
cryptographic primitive
ⓘ
pseudorandom number generator ⓘ stream cipher primitive ⓘ |
| advantage | strong theoretical security guarantees ⓘ |
| application |
randomness generation in cryptographic protocols
ⓘ
theoretical constructions of digital signatures ⓘ theoretical constructions of secure encryption schemes ⓘ |
| basedOn |
Blum integer
ⓘ
hardness of integer factorization ⓘ |
| category | cryptographically secure pseudorandom number generator ⓘ |
| comparedTo |
Mersenne Twister
ⓘ
linked to:
MersenneTwister
linear congruential generator ⓘ |
| complexityClassRelation | security reducible to factoring problem ⓘ |
| describedIn | SIAM Journal on Computing ⓘ |
| designGoal |
cryptographic security
ⓘ
unpredictability of output bits ⓘ |
| disadvantage | relatively slow in software ⓘ |
| field |
cryptography
ⓘ
theoretical computer science ⓘ |
| introducedBy |
Lenore Blum
ⓘ
Manuel Blum ⓘ Michael Shub ⓘ |
| modulusType | Blum integer ⓘ |
| namedAfter |
Lenore Blum
ⓘ
Manuel Blum ⓘ Michael Shub ⓘ |
| outputFunction |
least significant bit of x_i
ⓘ
selected bits of x_i ⓘ |
| periodProperty | maximum period related to order of x_0 modulo n ⓘ |
| primeCondition |
p ≡ 3 (mod 4)
ⓘ
q ≡ 3 (mod 4) ⓘ |
| provableProperty | next-bit test hardness equivalent to factoring n ⓘ |
| publicationYear | 1986 ⓘ |
| relatedConcept |
one-way function
ⓘ
pseudorandom bit generator ⓘ quadratic residue ⓘ |
| relatedToProblem | integer factorization problem ⓘ |
| securityAssumption | factoring Blum integers is hard ⓘ |
| securityProperty |
next-bit unpredictability under factoring assumption
ⓘ
provable security under factoring assumption ⓘ |
| seedRequirement |
gcd(x_0, n) = 1
ⓘ
x_0 is quadratic residue modulo n ⓘ |
| stateUpdateFunction | x_{i+1} = x_i^2 mod n ⓘ |
| typicalUse |
benchmark for provable security of PRNGs
ⓘ
research and teaching in cryptography ⓘ |
| usesModulus | n = p · q ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Blum–Blum–Shub pseudorandom number generator Description of subject: The Blum–Blum–Shub pseudorandom number generator is a cryptographically secure generator based on the hardness of factoring large composite numbers, widely studied in theoretical computer science and cryptography.
Referenced by (8)
Full triples — surface form annotated when it differs from this entity's canonical label.
Blum–Micali pseudorandom number generator
→
relatedTo
→
Blum–Blum–Shub pseudorandom number generator
ⓘ
linked to: Blum–Blum–Shub pseudorandom number generator
linked to: Blum–Blum–Shub pseudorandom number generator
linked to: Blum–Blum–Shub pseudorandom number generator