Blum Integers
Who — in computer science — has supervised more world-leading researchers than anyone else? Well, Manual Blum must be a major contender, with Doctoral students of Len Adleman (co-created of the RSA method), Gary Millar (famous for the Millar-Rabin prime test), Shafi Goldwasser (known for probabilistic encryption and Zero-Knowledge Proofs), and Silvio Micali (famous for pseudorandom methods).
So let’s look at one of Manual’s contributions: Blum integers. These integers were discovered by the mighty Manuel Blum (of the famous Blum Blum Shub fame — here). These related to the solving of the form:
y = x² mod n
and where we need to find values of y for different values of x, and for a given modulus (n). The example if we have:
4 = x² (mod 15)
The valid values of x are 2, 7, 8 and 13.
4 = 2² (mod 15) = 4
4 = 7² (mode 15) = 49 (mod 15) = 4
Sometimes, though, there are no solution, such as for x=3.
A Blum integer is created by multiplying up of two prime numbers (p and q) and where p=3 (mod 4) and q = 3 (mod 4):
n=p * q
Thus we take the prime numbers (p and q) and divide by four, and if we get an answer of 3, we have the required value. For example, 7 is a possible value, as…
