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

Если p и q - два простых числа, конгруэнтных 3 по модулю 4, то n = pq иногда называют целым числом Блюма. Если n - это целое число Блюма, у каждого квадратичного вычета ровно четыре квадратных корня, один из которых также является квадратом - это главный квадратный корень. Например, главный квадратный корень 139 mod 437 - это 24. Остальные три корня - это 185, 252 и 413.

Генераторы

Если p - простое число, и g меньше, чем p, то g называется генератором по модулю p, если для каждого числа b от 1 до p - 1 существует некоторое число a, что g^a ? b (mod p).

Иными словами, g является примитивом по отношению к p. Например, если p = 11, то 2 - это генератор по модулю 11:

2¹⁰ = 1024 ? 1 (mod 11)

2¹ = 2 ? 2 (mod 11)

2⁸ = 256 ? 3 (mod 11)

2² = 4 ? 4 (mod 11)

2⁴ = 16 ? 5 (mod 11)

2⁹ = 512 ? 6 (mod 11)

2⁷ = 128 ? 7 (mod 11)

2³ = 8 ? 8 (mod 11)

2⁶ = 64 ? 9 (mod 11)

2⁵ = 32 ? 10 (mod 11)

Каждое число от 1 до 10 может быть представлено как 2^a (mod p). Для p = 11 генераторами являются 2, 6, 7 и 8. Другие числа не являются генераторами. Например, генератором не является число 3, потому что не существует решения для

3^a ? 2 (mod 11)

В общем случае проверить, является ли данное число генератором, нелегко. Однако задщача упрощается, если известно разложение на множители для p - 1. Пусть q₁, q₂, ... , q_n - это различные простые множители p - 1. Чтобы проверить, является ли число g генератором по модулю p, вычислите

g⁽^p^-1)/^q mod p

для всех значений q = q₁, q₂, ... , q_n.

Если это число равно 1 для некоторого q, то g не является генератором. Если для всех значений q рассчитанное значение не равно 1, то g - это генератор.

Например, пусть p = 11. Простые множители p - 1 = 10 - это 2 и 5. Для проверки того, является ли число 2 генератором, вычислим:

2^(11-1)/5 (mod 11) = 4

2^(11-1)/2 (mod 11) = 10

Ни один из ответов не равен 1, поэтому 2 - это генератор.

Проверим, является генератором ли число 3:

3^(11-1)/5 (mod 11) = 9

3^(11-1)/2 (mod 11) = 1

Следовательно, 3 - это не генератор.

При необходимости обнаружить генератор по модулю p просто случайно выбирайте число от 1 до p - 1 и проверяйте, не является ли оно генератором. Генераторов достаточно, поэтому один из них вы, скорее всего, найдете быстро.