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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

47
наковые целые числа. Аналогично покажите, что два целых числа в различ-
ных позициях не могут иметь одинаковые значения для k (mod n) и для [k/n]
(mod n). Докажите, исходя из этого, что сумма целых чисел в строке будет
1
2
n
(n
2
– 1) – одинаковая для каждой строки.
Аналогично докажите, что суммы членов в столбцах одинаковы, так
что квадрат, действительно, магический.
3. Используйте вышеприведённый метод для написания программы
для получения магических квадратов порядка 3 и 5 (идеальным была бы
распечатка чисел в квадратном массиве на экране). Где ошибка при n = 4?
11.6. Проект:
ρ
-метод факторизации Полларда. [7]. Трудно до кон-
ца понять, где этот метод может использоваться, но он дает прекрасные
компьютерные программы и они, по крайней мере, просты для понимания
самого метода! Пусть f(x) = x
2
+ 1 и запишем f
2
(x) = f(f(x)), f
3
(x) = f(f
2
(x)) и
т. д. Пусть a
k
= f
k
(1). (Следовательно, а
1
= 2, а
2
= 5, а
k+1
= a
k
2
+ 1). Конечно,
вместо этого f можно использовать другие полиномы. Предположим, что
мы хотим представить N в виде сомножителей, т. е., найти простое число р
(возможно наименьшее простое число), для которого p | N. Конечно, после-
довательность {a
k
}, взятая по модулю р или по модулю N в конце концов
будет повторяться, и ожидается, что это повторение будет происходить бы-
стрее по mod p, чем по mod N. (Действительно, повторение будет реальной
возможностью, если количество членов превзойдёт
p
). Следовательно, мы
надеемся, что a
i
≡ a
j
(mod p) для j, больших i, при этом j не очень больших.
Заметим, что тогда a
t
≡ a
j-i+t
(mod p) для всех t ≥ i. Конечно, мы не можем
решить задачу нахождения a
i
mod p, пока не знаем, что собой представляет
р, но мы можем решить задачу нахождения a
i
mod N. Просто запишем
p | ((a
j
– a
i
) mod N, N).
(Смысл в том, чтобы разность a
j
– a
i
быстро становилась очень большой).
Проделаем простое усовершенствование: так как i < j, то существует
целое число t, для которого i < t ≤ j и (j – i) | t. (Это становится понятным,
если задать вопрос, почему должно существовать целое число k, для кото-
рого i/(j – – i) < k ≤ j/(j – i), и тогда
используйте t = k(j – i)). Более того,
a
t
= a
k(i–-i )
≡ a
(k+1)(j–1)
≡ a
(k+2)(j–1)
≡ . . . ≡ a
2k(j–1)
≡ a
2t
(mod p), т. е., вместо кон-
троля i и j, мы должны рассмотреть a
t
и a
2t
для t = 1, 2, 3, . . . Таким образом,
метод заключается в следующем.
Зададим x = a
1
= 2, y = a
2
= 5.
Заменим х на f(x), y на f(f(y)); таким образом, теперь x = a
2
, y = a
4
. Най-
дём (x – y, N).
Повторим: теперь х = a
3
, у = a
6
. Найдём (x – y, N).

Страницы