Ціле число Блума

У математиці натуральне число 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 — ціле число Блума, а Q_n — множина всіх квадратичних лишків за модулем n і взаємно простих з n і a ∈ Q_n. Тоді:

a має чотири квадратних корені за модулем n, рівно один з яких належить Q_n
Унікальний квадратний корінь з a в Q_n називається головним квадратним коренем за модулем n
Функція f: Q_n → Q_n визначена як f(x) = x² mod n є перестановкою. Оберненою функцією до f буде f ⁻¹(x) = x^{((p − 1)(q − 1) + 4)/8} mod n.^[2]
Для кожного цілого числа Блума n, символ Якобі для -1 за модулем n дорівнює +1, хоча −1 не є квадратичним лишком для n:

\left({\frac {-1}{n}}\right)=\left({\frac {-1}{p}}\right)\left({\frac {-1}{q}}\right)=(-1)^{2}=1

Історія

До розробки сучасних алгоритмів факторизації таких як квадратичне решето та метод решета числового поля, вважалося доцільним вибирати цілі числа Блума як модулі для алгоритму 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

Див. також

[HurdBlum-1] Joe Hurd, Blum Integers (1997), retrieved 17 Jan, 2011 from http://www.gilith.com/research/talks/cambridge1997.pdf [Архівовано 5 березня 2016 у Wayback Machine.]

[2] Menezes, Alfred; van Oorschot, Paul; Vanstone, Scott (1997). Handbook of applied cryptography. Boca Raton: CRC Press. с. 102. ISBN 0849385237. OCLC 35292671.

[1]

[2]