Ціле число Блума
Ця стаття має кілька недоліків. Будь ласка, допоможіть удосконалити її або обговоріть ці проблеми на сторінці обговорення.
|
У математиці натуральне число n є цілим числом Блума, якщо n = p × q — напівпросте число, для якого p і q є різними простими числами, такими що дають остачу 3 при діленні на 4[1]. Тобто, p і q повинні мати вигляд 4t + 3 для деякого цілого t.
Перші кілька цілих чисел Блума — це 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, … (послідовність A016105 з Онлайн енциклопедії послідовностей цілих чисел, OEIS). Ці числа названі так на честь Мануеля Блума, вченого відомого досягненнями в галузі теоретичної інформатики.
Нехай n = p×q — ціле число Блума, а Qn — множина всіх квадратичних лишків за модулем n і взаємно простих з n і a ∈ Qn. Тоді:
- a має чотири квадратних корені за модулем n, рівно один з яких належить Qn
- Унікальний квадратний корінь з a в Qn називається головним квадратним коренем за модулем n
- Функція f: Qn → Qn визначена як f(x) = x2 mod n є перестановкою. Оберненою функцією до f буде f −1(x) = x((p − 1)(q − 1) + 4)/8 mod n.[2]
- Для кожного цілого числа Блума n, символ Якобі для -1 за модулем n дорівнює +1, хоча −1 не є квадратичним лишком для n:
До розробки сучасних алгоритмів факторизації таких як квадратичне решето та метод решета числового поля, вважалося доцільним вибирати цілі числа Блума як модулі для алгоритму RSA. Це більше не вважається корисним запобіжним засобом, оскільки вищенаведені алгоритми здатні факторизувати модуль RSA побудований на цілих числах Блума з такою ж легкістю, як і модулі, побудовані на випадково вибраних простих числах.
- ↑ Joe Hurd, Blum Integers (1997), retrieved 17 Jan, 2011 from http://www.gilith.com/research/talks/cambridge1997.pdf [Архівовано 5 березня 2016 у Wayback Machine.]
- ↑ Menezes, Alfred; van Oorschot, Paul; Vanstone, Scott (1997). Handbook of applied cryptography. Boca Raton: CRC Press. с. 102. ISBN 0849385237. OCLC 35292671.
- Joe Hurd, Blum Integers (1997), retrieved 17 Jan, 2011 http://www.gilith.com/research/talks/cambridge1997.pdf [Архівовано 5 березня 2016 у Wayback Machine.]
- Goldwasser, S. and Bellare, M. http://cseweb.ucsd.edu/~mihir/papers/gb.html [Архівовано 20 травня 2012 у WebCite]. Summer course on cryptography, MIT, 1996—2001