Blum integer
E505280
A Blum integer is a special type of composite number formed as the product of two distinct prime numbers each congruent to 3 modulo 4, widely used in cryptography and pseudorandom number generation.
Statements (47)
| Predicate | Object |
|---|---|
| instanceOf |
composite number
ⓘ
mathematical concept ⓘ |
| appearsIn |
complexity-theoretic cryptography literature
ⓘ
theory of pseudorandom bit generators ⓘ |
| category |
computational number theory
ⓘ
cryptographic number theory ⓘ |
| definition | a composite number n that is the product of two distinct primes p and q with p ≡ 3 (mod 4) and q ≡ 3 (mod 4) ⓘ |
| example |
21 is a Blum integer because 21 = 3 × 7 and 3 ≡ 3 (mod 4), 7 ≡ 3 (mod 4)
ⓘ
33 is a Blum integer because 33 = 3 × 11 and 3 ≡ 3 (mod 4), 11 ≡ 3 (mod 4) ⓘ |
| field | number theory ⓘ |
| generalizationOf | special case of a semiprime with additional congruence conditions on the primes ⓘ |
| hasAdvantage |
provides strong hardness assumptions for cryptographic constructions
ⓘ
simplifies analysis of quadratic residues modulo n ⓘ |
| hasConstraint |
n must be large for security
ⓘ
p and q must be kept secret in cryptographic applications ⓘ |
| hasForm | n = p × q ⓘ |
| hasProperty |
for a Blum integer n, exactly half of the elements with Jacobi symbol 1 modulo n are quadratic residues
ⓘ
for a Blum integer n, the Chinese remainder theorem gives a 1–1 correspondence between square roots modulo n and pairs of square roots modulo p and q ⓘ for a Blum integer n, −1 is not a quadratic residue modulo p or q ⓘ if n is a Blum integer, then λ(n) = lcm(p − 1, q − 1) is even and typically divisible by 4 ⓘ if n is a Blum integer, then φ(n) = (p − 1)(q − 1) is divisible by 4 ⓘ n has exactly four square roots modulo n for any quadratic residue ⓘ n is square-free ⓘ p and q are distinct primes ⓘ p ≡ 3 (mod 4) ⓘ q ≡ 3 (mod 4) ⓘ the Jacobi symbol (a/n) does not uniquely determine quadratic residuosity modulo n ⓘ the factorization of a Blum integer can be recovered from an oracle that distinguishes quadratic residues from non-residues with Jacobi symbol 1 modulo n ⓘ |
| introducedInContext | construction of provably secure pseudorandom generators ⓘ |
| namedAfter | Manuel Blum NERFINISHED ⓘ |
| nonExample |
15 is not a Blum integer because 5 ≡ 1 (mod 4)
ⓘ
49 is not a Blum integer because it is not a product of two distinct primes ⓘ |
| relatedTo |
Blum integer-based trapdoor permutations
NERFINISHED
ⓘ
RSA modulus ⓘ hardness of factoring Blum integers ⓘ integer factorization problem ⓘ quadratic residues modulo n ⓘ quadratic residuosity problem NERFINISHED ⓘ |
| usedIn |
Blum–Blum–Shub pseudorandom number generator
NERFINISHED
ⓘ
Goldwasser–Micali cryptosystem NERFINISHED ⓘ Rabin cryptosystem variants ⓘ bit commitment schemes ⓘ cryptography ⓘ digital signature schemes ⓘ probabilistic encryption schemes ⓘ pseudorandom number generation ⓘ zero-knowledge proofs ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.