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

У математиці натуральне число 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 і aQn. Тоді:

  • a має чотири квадратних корені за модулем n, рівно один з яких належить Qn
  • Унікальний квадратний корінь з a в Qn називається головним квадратним коренем за модулем n
  • Функція f: QnQn визначена як 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 побудований на цілих числах Блума з такою ж легкістю, як і модулі, побудовані на випадково вибраних простих числах.

Примітки

[ред. | ред. код]
  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.

Список літератури

[ред. | ред. код]

Див. також

[ред. | ред. код]