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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

9
2. Пусть p будет простым числом и p | n, где p и n – оба нечетные и
p < n. Пусть a = (n + 1, p + 1), b = (n – 1, p – 1). Покажите, что (a, b) = 2,
(
a, p) = 1, (b, p) = 1. Докажите, используя решение задания 3 из упражнения
2.1, что
abp | 2(n – p) и, следовательно, что ab < 2n/p.
3.
Свойство делимости, или алгоритм деления. Пусть a и b будут це-
лыми числами и
b ≠ 0. Тогда существуют единственные q и r (частное и
остаток), удовлетворяющие условию
a = bq + r, 0 ≤ r < |b|.
Докажите это, используя следующий метод. Рассмотрите множество
целых чисел
S = {a – bq : q ∈ Z}.
Ясно, что
S содержит неотрицательные целые числа (почему?). Пусть
r будет наименьшим целым числом в S, которое больше нуля. Покажите,
что
r удовлетворяет соотношению 0 ≤ r < |b| (если желаете, рассмотрите
случай
b > 0). Чтобы доказать, что q и r единственны, предположите, что
a = bq + r= bq
1
+ r
1
, где 0 ≤ r< |b| и 0 ≤ r
1
<|b|. Полагая, что r < r
1
, докажите,
что 0 <
r
1
– r < |b| и, используя это условие и r
1
– r = b(q – q
1
), получите про-
тиворечие. Докажите, что если
r
1
= r, то q
1
= q.
3.3. Упражнение на компьютере
Используйте программу для нахождения НОД некоторых пар чисел,
которую Вы можете также проверить вручную (это является хорошим раз-
влечением при опробовании новой программы!). Испытайте также пары,
такие как (666 . . . 6, 777 . . . 7), где используются по
k шестерок и семерок,
так, чтобы результатом было
k единиц. При каком значении k эта программа
выдаст неправильный ответ?
3.4. Упражнение на компьютере: случайные пары
Вы можете создать случайные пары, используя
RANDOMIZE;
a := RANDOM (1000) + 1;
b := RANDOM (1000) + 1.
При этом производятся случайные пары натуральных чисел, заклю-
ченных между 1 и 1000. Запустите программу, скажем, 100 раз и выполните
вычисления для проверки количественного соотношения пар, которые дают
а) НОД = 1; б) НОД = 1 или 2; в) НОД > 10. (Вставьте цикл в программу для
обеспечения выполнения этой программы 100 раз, пока не
будет получен
удовлетворительный результат, так как оператор RANDOMIZE имеет тен-
денцию зависеть от времени, а программа будет выполнена настолько бы-

Страницы