Lenore Blum and Manuel Blum

The Mighty Blum Integer

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.

Coding

The coding is [here]:

package main

import (


 "fmt"
 "crypto/rand"
 "os"
 "strconv"
 "math/big"


)


func main() {


 bitsize:=256


 argCount := len(os.Args[1:])

        if (argCount>0)  {bitsize,_ = strconv.Atoi(os.Args[1])}


 fmt.Printf("\nSearching for a %d-bit prime number\n",bitsize) 

 prime1, _ := rand.Prime(rand.Reader, bitsize)
 for {
  // Check prime = 3 (mod 4)
  val:=new(big.Int).Mod(prime1,big.NewInt(4))

  fmt.Printf("%v: (mod 4) = %v\n",prime1,new(big.Int).Mod(prime1,big.NewInt(4)) )
  if val.Cmp(big.NewInt(3))==0 { break }
  prime1, _ = rand.Prime(rand.Reader, bitsize)
 }

 prime2, _ := rand.Prime(rand.Reader, bitsize)

 for {
  // Check prime = 3 (mod 4)
  val:=new(big.Int).Mod(prime2,big.NewInt(4))

  fmt.Printf("%v: (mod 4) = %v\n",prime2,new(big.Int).Mod(prime2,big.NewInt(4)) )
  if val.Cmp(big.NewInt(3))==0 { break }
  prime2, _ = rand.Prime(rand.Reader, bitsize)
 }

 fmt.Printf("\np: %v\n",prime1) 
 fmt.Printf("\nq: %v\n",prime2) 
 fmt.Printf("\nN: %v\n",new(big.Int).Mul(prime1,prime2))




}

A sample run for a 256-bit prime [here]:

Searching for a 256-bit prime number
112282040205538378245387818387495810657577046671244984055072403564524069493511: (mod 4) = 3
112881545245901041944818781106057693368114211821905546093446567660035951937543: (mod 4) = 3

p: 112282040205538378245387818387495810657577046671244984055072403564524069493511

q: 112881545245901041944818781106057693368114211821905546093446567660035951937543

N: 12674570201763560371365687606850687951648422601431998074021049138938946233860910684650440234879702248902806026148052473639025541555212252371210899115783473

and for a 512-bit prime number [here]:

Searching for a 512-bit prime number
10609592148122926402216460002147427694388995701270088696863856791744722482024858722304132067594810610748818113700816145378451190985625502355199797972258827: (mod 4) = 3
13163826430445376764785050550779535860702488624028885357968520671045192823259426771030474465699504646316541655699149441219052755935983581817081355390113833: (mod 4) = 1
11612779153043590431238318302375134252050337120407061693674912841140264323484260384681872916458747849721959282675212886476486567240536822112502001662951657: (mod 4) = 1
10183655496066414869152639347257075541538440834723258469030510356742084084819974184983958870526667740242167994057504292600564802762795036886454582503416949: (mod 4) = 1
11193609054527266489971408704597631656428070265299076208075061623875853925266921279436184574359825558624450036692712234871836714278324314966427376249477161: (mod 4) = 1
12980002582249363312152111324649044794274946402085580201644405700618583597867587182675534266569029913737087509914128827649243183189434501727131522231069237: (mod 4) = 1
10996821044814952858944323825460248977058620689256144109937234781547927501852658485217278631750158845815322456418141649071869896853491754942240226425059833: (mod 4) = 1
10635598704421307850114387110714904233111598395449789459947195556654438387069605783933858842587509462263293375145424052743344329659807199457356974519799333: (mod 4) = 1
10385083780084356968699740487015923811572371451458580107683842948814907684091445149474421461342105725163238696476690411356871102143910345331958284954978203: (mod 4) = 3

p: 10609592148122926402216460002147427694388995701270088696863856791744722482024858722304132067594810610748818113700816145378451190985625502355199797972258827

q: 10385083780084356968699740487015923811572371451458580107683842948814907684091445149474421461342105725163238696476690411356871102143910345331958284954978203

N: 110181503330781753458548132956666003365974911500366751026689363766428724321880416002302416399266373412421846082728799402802816906056223728162172474673471232619195017316237435476458575759630981779975212416885280734380090725212930615745116324894589622435539036868892342524969209967946705024005588283646459347881