Édition du: 20/08/2021 |
INDEX |
Types de Nombres – Diviseurs |
|||
Semi-parfaits (SP) |
||||
ENTIERS de BLUM Blum integers Propriété de
congruence des facteurs |
||
|
Sommaire de cette page >>> Définition >>> Nombres pseudo-aléatoires >>> Liste |
Débutants Glossaire |
Définition Entier de Blum: nombres composés de deux facteurs (semi-premier),
chacun congru
à 3 modulo 4. Autrement dit, chaque facteur est de la forme 4k + 3. Aucun exposant autorisé. Intérêt De tels grands nombres à deux facteurs sont difficiles à factoriser.
Ils font partie des nombres dits RSA. Ces nombres sont utilisés dans l'algorithme Blum Blum Shub. et
convient à la cryptographie. |
Exemple 201 = 3 ×
67 = (0 x 4 + 3)
|
||
Propriété Le nombre M est congru à 1 mod 4. |
Développement M = p × q
= (4a + 3)(4b + 3) = 16ab +12a + 12b + 9 = 4(3a + 3b + 4ab + 2) + 1 ≡ 1 mod 4 |
||
Selon la méthode Blum Blum Shub (BBS) créé par Lenore Blum, Manuel
Blum et Michael Shub en 1968. Il utilise la formule récurrente indiqué en lui injectant une semence
aléatoire x0. Le nombre M est un entier de Blum |
|
||
Exemples de calculs On calcule les quatre premières valeurs. En
modulo 4, les suivantes sont cycliques. Le nombre binaire
de quatre bits retenu est formé à partir du poids fort de la conversion
binaire de chacun de ces quatre nombres |
p, q, x0, valeurs, conversion binaire (pf) 3, 7, 5, [4, 16, 4, 16], [0, 0, 0, 0] 7, 11, 5, [25, 9, 4, 16], [1, 1, 0, 0] 11, 27, 5, [25, 31, 70, 148], [1, 1, 0, 0] 11, 27, 7, [49, 25, 31, 70], [1, 1, 1, 0] 43, 87, 31, [961, 3235, 1648, 3679], [1, 1, 0, 1] |
||
66 de 1 à
1000 Accès à tous ces nombres via le |
Liste 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. Liste avec facteurs [21, {3,
7}], [33, {3, 11}], [57, {3, 19}], [69, {3, 23}], [77, {7, 11}], [93, {3,
31}], [129, {3, 43}], [133, {7, 19}], [141, {3, 47}], [161, {7, 23}], [177,
{3, 59}], [201, {3, 67}], [209, {11, 19}], [213, {3, 71}], [217, {7, 31}],
[237, {3, 79}], [249, {3, 83}], [253, {11, 23}], [301, {7, 43}], [309, {3,
103}], [321, {3, 107}], [329, {7, 47}], [341, {11, 31}], [381, {3, 127}],
[393, {3, 131}], [413, {7, 59}], [417, {3, 139}], [437, {19, 23}], [453, {3,
151}], [469, {7, 67}], [473, {11, 43}], [489, {3, 163}], [497, {7, 71}],
[501, {3, 167}], [517, {11, 47}], [537, {3, 179}], [553, {7, 79}], [573, {3,
191}], [581, {7, 83}], [589, {19, 31}], [597, {3, 199}], [633, {3, 211}], [649,
{11, 59}], [669, {3, 223}], [681, {3, 227}], [713, {23, 31}], [717, {3,
239}], [721, {7, 103}], [737, {11, 67}], [749, {7, 107}], [753, {3, 251}],
[781, {11, 71}], [789, {3, 263}], [813, {3, 271}], [817, {19, 43}], [849, {3,
283}], [869, {11, 79}], [889, {7, 127}], [893, {19, 47}], [913, {11, 83}],
[917, {7, 131}], [921, {3, 307}], [933, {3, 311}], [973, {7, 139}], [989,
{23, 43}], [993, {3, 331}] |
|
542 de 1000 à 10
000 |
Liste 1041, 1057,
1077, 1081, 1101, 1121, 1133, 1137, 1141, 1149, 1169, 1177, 1253, 1257, 1273,
1293, 1317, 1329, 1333, 1337, 1349, 1357, 1389, 1393, 1397, 1401, 1437, 1441,
1457, 1461, 1473, 1477, 1497, 1501, 1509, 1529, 1541, 1561, 1569, 1577, 1589,
1633, 1641, 1661, 1673, 1689, 1713, 1757, 1761, 1793, 1797, 1817, 1821, 1829,
1837, 1841, 1857, 1893, 1897, 1909, 1929, 1941, 1957, 1969, 1977, 1981, 2021,
2033, 2049, 2073, 2077, 2101, 2149, 2157, 2177, 2181, 2189, 2201, 2217, 2229,
2253, 2317, 2321, 2361, 2369, 2413, 2429, 2433, 2449, 2453, 2461, 2469, 2481,
2489, 2497, 2513, 2517, 2537, 2569, 2573, 2577, 2589, 2629, 2641, 2649, 2653,
2661, 2681, 2721, 2733, 2757, 2761, 2773, 2841, 2869, 2881, 2893, 2901, 2913,
2921, 2933, 2949, 2973, 2981, 3013, 3017, 3053, 3057, 3073, 3093, 3097, 3101,
3113, 3117, 3149, 3153, 3173, 3189, 3193, 3197, 3241, 3261, 3269, 3273, 3309,
3317, 3337, 3353, 3369, 3377, 3397, 3401, 3409, 3421, 3437, 3453, 3473, 3489,
3493, 3513, 3521, 3561, 3569, 3629, 3641, 3661, 3669, 3693, 3713, 3749, 3777,
3781, 3817, 3829, 3837, 3841, 3849, 3873, 3901, 3909, 3921, 3937, 3941, 3949,
3953, 3957, 3981, 3997, 4009, 4037, 4061, 4101, 4109, 4117, 4169, 4189, 4193,
4197, 4213, 4237, 4249, 4269, 4281, 4309, 4313, 4317, 4333, 4341, 4353, 4377,
4393, 4413, 4417, 4429, 4449, 4461, 4497, 4501, 4529, 4533, 4541, 4569, 4577,
4593, 4601, 4609, 4613, 4629, 4661, 4677, 4681, 4701, 4713, 4737, 4741, 4749,
4757, 4769, 4781, 4821, 4829, 4837, 4841, 4853, 4857, 4873, 4881, 4897, 4989,
4997, 5001, 5029, 5033, 5053, 5089, 5093, 5097, 5129, 5137, 5149, 5169, 5173,
5177, 5201, 5221, 5241, 5257, 5269, 5277, 5293, 5349, 5357, 5361, 5377, 5401,
5433, 5461, 5469, 5489, 5493, 5497, 5509, 5533, 5541, 5549, 5561, 5601, 5609,
5613, 5633, 5637, 5677, 5721, 5753, 5761, 5773, 5789, 5793, 5833, 5853, 5873,
5893, 5909, 5921, 5937, 5961, 5969, 5977, 5997, 6009, 6013, 6017, 6033, 6041,
6049, 6077, 6081, 6117, 6157, 6169, 6181, 6189, 6193, 6209, 6233, 6249, 6261,
6281, 6289, 6297, 6313, 6333, 6349, 6377, 6393, 6429, 6433, 6457, 6493, 6509,
6533, 6537, 6541, 6557, 6589, 6593, 6609, 6621, 6629, 6677, 6717, 6729, 6753,
6769, 6797, 6801, 6809, 6821, 6861, 6881, 6901, 6913, 6933, 6937, 6941, 6973,
7009, 7017, 7037, 7041, 7053, 7061, 7073, 7097, 7113, 7117, 7133, 7149, 7153,
7169, 7181, 7197, 7201, 7217, 7233, 7249, 7269, 7273, 7277, 7313, 7341, 7357,
7377, 7401, 7409, 7441, 7493, 7509, 7513, 7593, 7597, 7601, 7609, 7613, 7617,
7629, 7637, 7653, 7661, 7697, 7721, 7729, 7737, 7773, 7781, 7849, 7861, 7909,
7941, 7961, 7977, 7981, 7989, 7997, 8013, 8049, 8057, 8061, 8097, 8121, 8129,
8133, 8137, 8141, 8153, 8157, 8173, 8189, 8193, 8197, 8201, 8213, 8257, 8261,
8301, 8309, 8341, 8373, 8401, 8409, 8413, 8417, 8441, 8453, 8457, 8509, 8529,
8549, 8553, 8557, 8561, 8617, 8637, 8657, 8661, 8709, 8717, 8773, 8777, 8781,
8797, 8809, 8813, 8817, 8873, 8881, 8889, 8909, 8913, 8921, 8953, 8977, 8981,
8997, 9017, 9033, 9037, 9053, 9057, 9069, 9073, 9097, 9101, 9121, 9149, 9201,
9229, 9233, 9237, 9249, 9253, 9289, 9301, 9313, 9329, 9353, 9357, 9449, 9481,
9489, 9493, 9501, 9517, 9557, 9561, 9569, 9573, 9589, 9609, 9617, 9637, 9641,
9713, 9753, 9757, 9761, 9777, 9793, 9813, 9853, 9869, 9897, 9913, 9917, 9921,
9937, 9957, 9961, 9969, 9977, 9989, 9993 |
|
Retour |
|
Suite |
|
Voir |
Liens
en haut de page |
Sites |
OEIS A016105
– Blum integers: numbers of the form p * q where p and q are distinct primes
congruent to 3 (mod 4)
Entier de Blum –
Wikipédia
Blum integer – Wikipedia
Blum Blum Shub –
Wikipédia |
Cette page |