So What’s A Blum Integer?

So What’s A Blum Integer?

Let’s look at the magic of 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. 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. Let me example this with 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: