A Blum integer [1] is created by multiplying two prime numbers (\(p\) and \(q\)) and where \(p=3 \pmod 4\) and \(q = 3 \pmod 4\): \(n=p \times 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, ...
Blum Integers |
Theory
These related to the solving of the form: \(y = x^2 \pmod n\), and where we need to find values of \(y\) for different values of \(x\), and for a given modulus (\(n\)). For example, if we have:
\(4 = x^2 \pmod{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 \pmod 4\) and q = 3 (mod 4):
\(n=p \times 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. We also get a single quadratic root. Let's take an example. For p=47 and q=43, we have:
\(47 = 3 \pmod 4\) [as this is 15 r 3]
\(43 = 3 \pmod 4\) [as this is 14 r 3]
We find N as:
\(N = 47 \times 43 = 2021\)
Next we have find the four square root values for each value between 0 and \(N-1\). Let's pick a value of \(y=4\). For this the solutions for \(x\) in \(4=x^2 \pmod{2021}\) are:
\(1976^2=4 \pmod {2021}\)
\(2^2=4 \pmod {2021}\)
\(2019^2=4 \pmod {2021}\)
\(45^2=4 \pmod {2021}\)
For example \(1972^2 = 3904576\) and then if we take \(\pmod{2021}\)) we get 4. Thus our Blum integer always gives us four modulo square roots.
Coding
The coding is here:
import sys import libnum def legendre_symbol(a, p): """ Compute the Legendre symbol a|p using Euler's criterion. p is a prime, a is relatively prime to p (if p divides a, then a|p = 0) Returns 1 if a has a square root modulo p, -1 otherwise. """ ls = pow(a, (p - 1) // 2, p) return -1 if ls == p - 1 else ls p=0 q=0 bitsize=6 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 () print ("Here are the Z*p: values up to 1000") for a in range(0, n): rtn= libnum.jacobi(a,n) if (rtn==1): print (a,end=',') if (a==1000): sys.exit()
A sample run:
Prime (p): 43. Length: 6 bits, Digits: 2 Prime (q): 59. Length: 6 bits, Digits: 2 N= 2537 The first few values: 2535^2=4 (mod 2537) 1890^2=4 (mod 2537) 647^2=4 (mod 2537) 2^2=4 (mod 2537) 298^2=9 (mod 2537) 2534^2=9 (mod 2537) 3^2=9 (mod 2537) 2239^2=9 (mod 2537) Here are the Z*p: values up to 1000 1,2,4,8,9,15,16,17,18,21,25,30,32,33,34,35,36,37,39,41,42,49,50,53,55,57,60,61,64,65,66,68,69,70,72,73,74,77,78,79,81,82,84,87,89,91,93,95,98,100,106,107,110,113,114,115,120,121,122,127,128,130,131,132,133,135,136,138,139,140,141,143,144,145,146,148,149,151,153,154,155,156,157,158,161,162,164,167,168,169,174,178,179,181,182,186,189,190,191,193,196,197,200,201,203,209,211,212,213,214,217,220,225,226,227,228,230,233,235,239,240,242,244,247,249,251,253,254,255,256,260,262,264,266,270,271,272,276,278,280,281,282,286,288,289,290,291,292,293,296,297,298,299,302,303,306,307,308,309,310,311,312,313,314,315,316,317,319,322,324,327,328,329,333,334,335,336,338,341,347,348,349,351,355,356,357,358,359,361,362,364,369,372,375,377,378,379,380,382,386,392,394,400,402,403,406,409,411,415,418,419,421,422,424,425,426,428,434,437,439,440,441,450,452,454,456,457,460,461,463,466,467,469,470,477,478,479,480,484,485,487,488,489,494,495,497,498,502,503,505,506,508,510,512,513,515,517,519,520,524,525,528,529,532,540,542,544,545,547,549,551,552,555,556,557,560,561,562,564,571,572,576,578,580,581,582,584,585,586,587,589,592,594,595,596,597,598,599,601,604,606,611,612,614,615,616,617,618,619,620,621,622,624,625,626,628,629,630,632,634,638,643,644,648,654,656,657,658,661,663,666,667,668,669,670,672,673,676,679,682,685,687,691,693,694,696,697,698,702,707,709,710,711,712,713,714,716,718,721,722,723,724,728,729,735,737,738,739,744,750,751,754,756,758,760,763,764,771,772,773,777,781,783,784,787,788,789,795,800,801,804,806,807,811,812,815,818,819,822,825,827,830,831,833,836,837,838,839,841,842,844,848,849,850,852,853,855,856,859,861,863,865,868,871,874,875,877,878,880,882,883,887,893,899,900,901,904,907,908,912,913,914,915,920,922,923,925,926,929,932,934,935,937,938,940,947,954,956,958,959,960,961,963,968,969,970,971,974,975,976,978,983,988,990,991,993,994,995,996
Although there are four roots, the unique square root of \(a\) in the quadratic residue and is named the principal square root of a modulo n. In the example above, notice that 647 is not in the quadratic residue, and thus the principal square root is 2.
A clear example is:
Prime (p): 47. Length: 6 bits, Digits: 2 Prime (q): 43. Length: 6 bits, Digits: 2 N= 2021 1541^2=6 (mod 2021) 695^2=6 (mod 2021) 1326^2=6 (mod 2021) 480^2=6 (mod 2021) Here are the Z*p: values up to 1000 1, 4, 5, 6, 9, 14, 16, 17, 19, 20, 21, 22, 24, 25, 26, 29, 30, 33, 36, 39, 45, 46, 49, 53, 54, 56, 59, 62, 64, 68, 69, 70, 73, 74, 76, 77, 79, 80, 81, 82, 83, 84, 85, 88, 91, 93, 95, 96, 97, 100, 101, 102, 103, 104, 105, 110, 111, 113, 114, 116, 120, 121, 122, 123, 125, 126, 130, 132, 134, 137, 142, 143, 144, 145, 150, 151, 153, 156, 161, 163, 165, 169, 171, 173, 174, 178, 179, 180, 183, 184, 189, 195, 196, 197, 198, 199, 201, 211, 212, 213, 214, 216, 217, 218, 223, 224, 225, 227, 230, 233, 234, 236, 238, 239, 245, 248, 251, 253, 254, 256, 257, 259, 261, 262, 265, 266, 267, 269, 270, 271, 272, 276, 278, 280, 283, 287, 289, 292, 294, 295, 296, 297, 298, 299, 304, 307, 308, 310, 313, 314, 316, 318, 320, 321, 323, 324, 327, 328, 332, 334, 336, 337, 340, 341, 345, 349, 350, 351, 352, 353, 354, 357, 361, 362, 364, 365, 370, 372, 373, 374, 379, 380, 381, 382, 384, 385, 386, 388, 389, 393, 395, 397, 399, 400, 401, 403, 404, 405, 406, 407, 408, 409, 410, 412, 414, 415, 416, 417, 418, 419, 420, 421, 425, 427, 431, 433, 438, 439, 440, 441, 442, 444, 447, 449, 451, 452, 455, 456, 458, 462, 463, 464, 465, 467, 469, 471, 474, 475, 477, 479, 480, 481, 482, 484, 485, 486, 487, 488, 492, 493, 494, 497, 498, 499, 500, 501, 503, 504, 505, 510, 515, 520, 525, 526, 528, 529, 531, 533, 536, 541, 543, 546, 548, 550, 551, 554, 555, 558, 561, 562, 565, 568, 570, 572, 573, 576, 577, 579, 580, 582, 586, 587, 593, 600, 604, 605, 606, 607, 609, 610, 612, 613, 615, 617, 618, 619, 621, 622, 623, 624, 625, 627, 630, 631, 634, 638, 641, 643, 644, 650, 652, 657, 659, 660, 661, 662, 663, 666, 670, 671, 673, 676, 677, 678, 683, 684, 685, 686, 687, 691, 692, 693, 694, 696, 709, 710, 711, 712, 713, 715, 716, 718, 719, 720, 723, 725, 726, 727, 729, 732, 734, 736, 737, 738, 741, 742, 743, 747, 749, 750, 751, 754, 755, 756, 757, 763, 765, 766, 769, 780, 781, 782, 784, 788, 789, 792, 793, 796, 804, 805, 815, 819, 822, 823, 825, 826, 827, 829, 831, 833, 837, 839, 841, 843, 844, 845, 848, 851, 852, 853, 855, 856, 858, 859, 864, 865, 868, 870, 871, 872, 873, 874, 879, 883, 886, 887, 889, 890, 892, 895, 896, 900, 901, 906, 907, 908, 909, 914, 915, 917, 918, 920, 922, 923, 927, 931, 932, 933, 936, 937, 941, 943, 944, 945, 947, 951, 952, 953, 956, 957, 961, 966, 967, 973, 975, 977, 978, 979, 980, 982, 983, 985, 990, 992, 993, 995, 997, 999,
Notice that 695 does not exist, but 480 exists (and is the single principal square root).
References
[1] Blum, M. (1983). Coin flipping by telephone a protocol for solving impossible problems. ACM SIGACT News, 15(1), 23-27 [here].