Don't take life too seriously: it's just a temporary situation

Interi di Blum

Teoria dei numeri 

Si chiamano “interi di Blum” gli interi positivi uguali al prodotto di due primi distinti, entrambi della forma 4k + 3, detti anche “primi di Blum”. Per esempio, 133 = 7 • 19 è un intero di Blum.

Devono il loro nome al’esperto venezuelano di informatica Manuel Blum.

Furono studiati in relazione alle loro proprietà nella crittografia, perché per molti algoritmi la scomposizione di un semiprimo è più difficile se questo è un intero di Blum, quindi negli algoritmi crittografici che basano la difficoltà di decrittazione sulla scomposizione di un semiprimo si raccomandava l’utilizzo di interi di Blum; la scoperta di algoritmi per i quali la difficoltà non dipende dal fatto che siano interi di Blum o no ha reso obsoleta questa precauzione.

 

Gli interi di Blum minori di 1000 sono: 21, 33, 57, 69, 77, 93, 129, 133, 141, 161, 177, 201, 209, 213, 217, 237, 249, 253, 301, 309, 321, 329, 341, 381, 393, 413, 417, 437, 453, 469, 473, 489, 497, 501, 517, 537, 553, 573, 581, 589, 597, 633, 649, 669, 681, 713, 717, 721, 737, 749, 753, 781, 789, 813, 817, 849, 869, 889, 893, 913, 917, 921, 933, 973, 989, 993.

 

Qui trovate gli interi di Blum minori di 106.

 

Alcune proprietà degli interi di Blum:

  • sono semiprimi;

  • i loro fattori primi sono interi di Gauss con parte immaginaria nulla;

  • se n è un intero di Blum e a e b sono interi distinti tali che a2b2 mod n, allora Simbolo di Jacobi (±a | n) uguale a meno il simbolo di Jacobi (±b | n), dove Simbolo di Jacobi (a | n) è il simbolo di Jacobi (Williams);

  • se n è un intero di Blum, allora Simbolo di Jacobi (–1 | n), anche se –1 non è un residuo quadratico modulo n;

  • se n è un intero di Blum, il numero di interi positivi k inferiori a n tali che Simbolo di Jacobi (k | n) uguale a 1 è uguale al numero di interi positivi k inferiori a n tali che Simbolo di Jacobi (k | n) uguale a –1.

 

Se n è un intero di Blum, p e q sono i suoi fattori primi e a è un residuo quadratico modulo n non multiplo di p o q, vi sono 4 soluzioni dell’equazione x2a mod n e tra queste Formula per il calcolo dell’unica soluzione che sia un residuo quadratico modulo n è l’unica tale che x sia un residuo quadratico modulo n, detta “radice quadrata principale” di a (Williams). Per esempio, per n = 133 e a = 11, le soluzioni sono 12, 26, 107 e 121; tra queste Calcolo dell’unica soluzione che sia un residuo quadratico modulo 11 è l’unico residuo quadratico modulo 133.

 

Se n è un intero di Blum e p(x) è il minimo periodo della sequenza xk = x2k mod n, p(x) divide λ(λ(n)) per x maggiore di zero, dove λ(x) è la funzione di Carmichael (Blum, Blum e Shub). Se inoltre Ordine di x rispetto a n uguale a λ(n) / 2 e Ordine di 2 rispetto a λ(n) / 2 uguale a λ(λ(n)), allora p(x) = λ(λ(n)).

Per esempio, per n = 129 e x = 11, p(11) = 3, perché la sequenza 112 mod 129 = 121, 114 mod 129 = 64, 118 mod 129 = 97, 1116 mod 129 = 121 ha periodo 3, e 3 divide λ(λ(129)) = λ(42) = 6. Per x = 15, Ordine di 15 rispetto a 129 uguale a λ(129) / 2 uguale a 21, Ordine di 2 rispetto a λ(129) / 2 uguale a λ(λ(129)) uguale a 6 e p(15) = 6 = λ(λ(129)).

 

Se n è un intero di Blum con fattori primi p e q e p1 = (p – 1) / 2, p2 = (p – 3) / 4q1 = (q – 1) / 2q2 = (q – 3) / 4 sono primi (ovvero p1, p2, q1 e q2 sono primi di Sophie Germain), n si chiama “intero di Blum speciale”. In tal caso se 2 è residuo quadratico di al massimo uno tra p1 e q1, allora Ordine di 2 rispetto a λ(n) / 2 uguale a λ(λ(n)) ed esiste almeno un valore di x tra i residui quadratici di n tale che p(x) = λ(λ(n)).

 

Per esempio, n = 517 è un intero di Blum speciale, con p = 11, q = 47, p1 = 5, p2 = 2, q1 = 23 e q2 = 11; 2 è residuo quadratico di 23, ma non di 5, Ordine di 2 rispetto a λ(517) / 2 uguale a λ(λ(517)) uguale a 44, 3 è residuo quadratico modulo 517 e p(3) = 44 = λ(λ(129)).

 

Gli interi di Blum speciali hanno applicazioni in crittografia e nei generatori pseudo casuali di Blum-Blum-Shub.

 

Gli interi di Blum speciali minori di 106 sono: 253, 517, 1081, 1837, 3841, 3949, 7849, 7909, 8257, 15829, 16537, 16873, 22429, 31669, 33097, 33793, 44869, 45397, 46897, 54109, 59953, 62029, 63877, 65197, 66217, 66517, 67633, 79717, 83149, 83677, 84997, 93817, 94921, 95833, 108229, 113137, 118789, 120073, 124069, 129697, 133561, 135313, 136321, 139081, 151789, 153637, 155749, 166681, 168157, 172117, 173857, 174961, 177721, 191713, 193969, 223597, 226297, 231193, 237589, 239437, 240313, 248377, 257389, 258121, 259417, 265033, 268477, 269797, 272929, 278569, 283789, 284209, 311509, 314677, 317377, 321241, 323389, 325657, 340513, 340609, 347677, 351601, 355273, 357529, 359881, 363169, 394669, 405757, 462433, 465949, 467521, 470437, 471229, 480793, 491557, 496777, 500641, 504757, 507553, 508189, 516601, 519277, 524029, 530113, 532477, 533269, 538177, 561361, 564121, 564157, 567589, 570229, 582109, 593377, 616429, 626989, 630157, 645469, 648553, 648637, 651337, 656449, 657961, 665473, 667117, 676177, 681193, 689209, 704077, 718489, 722557, 726961, 732001, 735409, 739717, 755029, 793837, 800437, 812317, 821473, 825217, 848401, 850069, 867229, 875149, 879637, 898117, 924517, 931909, 941713, 955369, 969769, 974257, 979957, 983389, 983641, 985297, 989809.

 

Qui trovate gli interi di Blum speciali minori di 109.

Vedi anche

Interi di Williams.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.