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

У математиці натуральне число n є цілим числом Блума, якщо n = p × q — напівпросте число, для якого p і q є різними простими числами, такими що дають остачу 3 при діленні на 4. Тобто, 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, … (Шаблон: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.
• Для кожного цілого числа Блума 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 http://www.gilith.com/research/talks/cambridge1997.pdf Шаблон:Webarchive
• Goldwasser, S. and Bellare, M. http://cseweb.ucsd.edu/~mihir/papers/gb.html Шаблон:Webarchive. Summer course on cryptography, MIT, 1996—2001

Див. також

• Модульна арифметика
• Асиметричні алгоритми шифрування