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]
