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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

39
9.4. Компьютерное упражнение: ряд Фибоначчи по mod m
Пусть m ≥ 2 и f
0
= 1, f
1
= 1, f
n+2
≡ f
n+1
+ f
n
(mod m) для n ≥ 0. Последова-
тельность f
i
повторится, когда два последовательных члена повторяются как
последовательные члены в конце последовательности. Почему это означает,
что последовательность обязательно повторится? Обратите внимание, что
если f
n
≡ f
n+k
, f
n+1
≡ f
n+k+1
, где k > 0, тогда, действительно, f
0
≡ f
k
, f
1
≡ f
k+1
(все
по mod m), так что последовательность повторяется сначала. Задавая k =
= k(m) как можно меньше, мы назовём периодом последовательности Фи-
боначчи по mod m. Например, при m = 7 членами по модулю 7 будут 0, 1, 1,
2, 3, 5, 1, 6, 0, 6, 6, 5, 4, 2, 6, 1, а после всё повторится, так как k(7) = 16. На-
пишите программу для вычисления k(m) для различных значений m и про
-
верьте следующее:
1. Если m – простое число ≡ ± 1 (mod 10), тогда k(m) | (m – 1) является
собственным делителем m – 1?
2. Если m является простым числом ≡ ± 3 (mod 10), тогда k(m) | (2m +
+ 2). Для каких значений m < 1000 k(m) является собственным делителем
2m + 2? (Для m = 7, k(m) = 2m + 2).
3. Для некоторого простого числа р < 1000, k
(p) ≠ k(p
2
).
10. Инверсии по mod m и решения соответствующих сравнений
В этом разделе мы ответим на вопрос: имея а, когда существует b та-
кое, что ab ≡ 1 (mod m)? Мы также вычислим b из а, когда b существует;
b называется инверсией a (mod m), и мы можем записать b ≡ a
–1
.
10.1. Упражнения
1. Решите следующие сравнения (или покажите, что они не имеют
решений):
2x ≡ 3 (mod 7); 10x ≡ 3 (mod 18); 2x ≡ 3 (mod 15);
10x ≡ 15 (mod 17); 10x ≡ 3 (mod 27); 35x ≡ 14 (mod 182).
[Ответы на последние два задания: x ≡ 3 ( mod 27); x ≡ 16 (mod 26)].
2. Предположим, что ax ≡ c (mod m), 0 < a < m. Пусть m = ka + a
1
, где
0 ≤ а
1
< а; таким образом, a
1
является наименьшим положительным вычетом
a (mod m) и k = [m/a]. Используйте axk ≡ ck (mod m), чтобы показать, что
a
1
x ≡ –ck (mod m), которое является другим сравнением того же самого ви-
да, как то, с которого мы начинали, но с коэффициентом при х, который
наименьший положительный). При повторении процесса, коэффициент при
х может случайно стать равным 0; отсюда, на предыдущем шаге коэффици-
ент a′ при х делит m, т. е. сравнение
имеет вид a′x ≡ c′ (mod m). Конечно, ес-
ли a′ | c′, тогда отсутствует решение; в противном случае это равносильно
x ≡ (c′/a′) (mod m′/a′). Достаточно часто коэффициент при х становится еди-
ницей на предыдущем шаге перед тем, как станет 0; в некоторых случаях

Страницы