Целое число Блюма

В математике натуральное число n является целым числом Блюма, если n = p × q — полупростое число , для которого p и q — различные простые числа, конгруэнтные 3 по модулю 4. То есть p и q должны иметь вид 4 t + 3 для некоторого целого числа t . Целые числа этой формы называются простыми числами Блюма. Это означает, что делители целого числа Блюма представляют собой гауссовы простые числа без мнимой части. Первые несколько целых чисел Блюма:

21 , 33 , 57 , 69 , 77 , 93 , 129 , 133 , 141 , 161 , 177 , 201 , 209 , 213 , 217 , 237 , 249 , 253 , 301 , 309 , 321 , 9 , 341 , 381 , 393 , 413 , 417 , 437 , 453 , 469 , 473 , 489 , 497 , ... (последовательность A016105 в OEIS )

Целые числа были названы в честь ученого-компьютерщика Мануэля Блюма .

Свойства

Учитывая, что n = p × q — целое число Блюма, Qn _— множество всех вычетов по модулю n , взаимно простых с n и a ∈ Qn _{квадратичных} . Затем:

• a имеет четыре квадратных корня по модулю n , ровно один из которых также находится в Q _n
• Единственный квадратный корень из a в Q _n называется главным квадратным корнем из числа по модулю n.
• Функция f : Q _n → Q _n, определяемая формулой f ( x ) = x ² mod n — это перестановка. Обратная функция f : f ⁻¹ ( х ) = х ^{(( p −1)( q −1)+4)/8} против н .
• Для каждого целого числа Блюма n −1 имеет символ Якоби по модулю n +1, хотя −1 не является квадратичным вычетом числа n :

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

Ни одно целое число Блюма не является суммой двух квадратов .

История

До того, как были разработаны современные алгоритмы факторизации, такие как MPQS и NFS , считалось полезным выбирать целые числа Блюма в качестве модулей RSA . Это больше не считается полезной предосторожностью, поскольку MPQS и NFS способны факторизовать целые числа Блюма с той же легкостью, что и модули RSA, построенные из случайно выбранных простых чисел.