Элементы теории чисел и криптозащита. Воронков Б.Н - 46 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

46
11.4. Упражнение: теорема Гаусса. Для фиксированного числа m > 1
рассмотрите числа х, которые взаимно просты с m и удовлетворяют усло-
вию: 1 ≤ х < m. (Мы встретим эти числа ещё не раз; иногда они называются
приведенным набором вычетов по модулю m). Теорема Гаусса относится к
произведению P этих чисел по модулю m: она утверждает, что
это произве-
дение дает +1 в случае m = 4, или примет вид p
k
или 2p
k
для нечётного про-
стого числа р и k ≥ 1 в случае, когда произведение равно – 1. Идея очень
простая: каждое число х, как и вышеописано, имеет обратное у такое, что
ху ≡ 1 (mod m), более того, такое число у единственно и 1 ≤ y < m. Если у ≠ х,
тогда в произведении Р появляются
оба х и у и дают 1 при перемножении
одного на другое. Условие, в противоположность, для х = у будет x
2
≡ 1
(mod m), так что Р то же самое, что произведение по (mod m) всех чисел х,
для которых 1 ≤ x < m и x
2
≡ 1 (mod m).
11.5. Проект: магические квадраты
Рассмотрим n × n массив, где строки обозначены 0, 1, . . . , n –1, а ана-
логичные столбцы обозначены 0, 1, . . . , n – 1. Мы желаем заполнить этот
массив целыми числами 0, 1, . . . , n
2
– 1. Представим возможное предписа-
ние для выполнения: разместить целое число k по строкам i и столбцам j,
где модуль n,
i ≡ e + ak + b[k/n] , j ≡ f + ck + d[k/n] (1)
и a, b, c, d, e, f – фиксированные целые числа. (Значение наличия k и [k/n]
состоит в том, что если
будет известен модуль n, то k точно известно, так
как оно лежит между 0 и n
2
– 1). Например, для n = 4, e = f = 0, a = d = 1,
b = c = 0 мы получим левый массив, а для n = 3, e = f = 0, a= 2, b = c = d = 1
мы получим правый массив.
0 4 8 12 0 8 4
1 5 9 13 7 3 2
2 6 10 14 5 1 6
3 7 11 15
Правый массив называется магическим квадратом, так как его строки
и столбцы при сложении дают одно и то же число (именно 12).
1. Допустим,
что (ad – bc, n) = 1. Покажите, что из формулы (1) следует,
что никогда одно место в массиве не будут занимать два целых числа k и k′. Из
этого следует, конечно, что массив точно заполнен числами 0, 1, 2, . . . , n
2
– 1.
2. Теперь примем, что, раз (ad – bc, n) = 1, мы получим (a, n) =
= (b, n) = (c, n) = (d, n) = 1. Рассмотрим особую строку в массиве (фикси-
руя i) такую, что ak + b[k/n] ≡ u (mod n) для фиксированного u и всех k в
строке. Покажите, что два целых числа в различных позициях
в этой строке
не могут иметь одинаковых значений k (mod n), показывая, что они имели
бы тогда одинаковые значения [k/n] (mod n). Используйте свойство (b, n) = 1
и также то, что в противоположность пункту 1 были бы использованы оди-

Страницы