Blum Integers

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 when we divide by four, we get 3. The possible prime numbers are then: 3, 7, 11, 19, and so on. The Blum integers then become: 21, 33, 57, 69, 77, 93, 129, 133, 141, 161, 177, 201, 209, 213, 217, 237, 249, ….

Now, these have interesting properties. The first is that when we determine the modular square root of a value, we get four square roots. As an example, let’s say I have p=47 and q=43:

47 = 3 (mod 4) [as this is 15 r 3]

43 = 3 (mod 4) [as this is 14 r 3]

We find N as:

N = 47*43 = 2,021

Next, we find that there are four square root values for each value between 0 and N. Let’s pick a value of y=4. For this, the solutions for x in 4=x² (mod 2021) are:

1976^2=4 (mod 2021)
  2^2=4 (mod 2021)
  2019^2=4 (mod 2021)
  45^2=4 (mod 2021)

For example 1,972² = 3,904,576 and then if we take (mod 2,021) we get 4. Thus our Blum integer always gives us four modulo square roots. Here is a little program to compute a few of these [here]:

import sys
import libnum
p=0
q=0
bitsize=8
if (len(sys.argv)>1):
        bitsize=int(sys.argv[1])

while ((p%4)!=3):
  p=libnum.generate_prime(bitsize)
while ((q%4)!=3):
  q=libnum.generate_prime(bitsize)
print ("\nPrime (p): %d. Length: %d bits, Digits: %d" % (p,libnum.len_in_bits(p), len(str(p)) ))  
print ("\nPrime (q): %d. Length: %d bits, Digits: %d" % (q,libnum.len_in_bits(q), len(str(q)) )) 

n=p*q
print ("N=",n)
print ("The first few values:")
for x in range(2,12):
  if (libnum.has_sqrtmod(x,{p: 1,q:1})):
    res=libnum.sqrtmod(x,{p: 1,q:1})
    y=next(res)
    print ("  %d^2=%d (mod %d)" % (y,x,n))
    y=next(res)
    print ("  %d^2=%d (mod %d)" % (y,x,n))  
    y=next(res)
    print ("  %d^2=%d (mod %d)" % (y,x,n))
    y=next(res)
    print ("  %d^2=%d (mod %d)" % (y,x,n))
    print ()

Here is the code:

Want to know more about Blum’s work? Here is how the Blum family created the random number method based on Blum integers:

and here is how Shafrira Goldwasser used them in probabilistic encryption:

And here are all the things the Manual has been involved with: