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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

10
стро, что время не скажется на результат. Можно использовать петлю за-
держки или такой параметр как RANDSEED (i*i).
3.5. Упражнение на компьютере: модификация алгоритма Евклида
Рассмотрим две строки: a = bq
1
+ r
2
, т. е., r
2
= a – bq
1
, и b = r
2
q
2
+ r
3
,
т. е.,
r
3
= b – r
2
q
2
. Если a заменить на a – bq
1
= a – b[a/b], а затем b заменить
на
b – a q
2
= b – a[b/a] (продолжать, пока новое a ≠ 0!), тогда конечными
значениями
a и b будут r
2
и r
3
, соответственно. Повторяя эту процедуру
снова, получим
r
4
и r
5
, и т. д. Напишите программу, которая выполнит эти
изменения. Добавив цикл в упражнение 3.4 и последнюю модификацию, Вы
можете сравнить скорости вычисления НОД случайных пар. Какая про-
грамма работает быстрее?
3.6. Проект: взаимно простые пары
Рассмотрим «эвристический подход», который предсказывает соотно-
шение между парами чисел, которые должны быть взаимно простыми. Возь-
мем все числа, большие нуля. «Вероятность» того, что положительное число
a
делится на
h приблизительно равна 1/h в смысле, что из ряда чисел 1, . . . , n
точно
h, 2h, 3h, . . . , [n/h|h] являются произведениями h, а [n/h]/n будет близ-
ким к 1/
h. Пусть p
h
будет вероятностью того, что два положительных случайно
выбранных числа имеют НОД =
h. Заметим, что (a, b) = h ⇔ a/h, b/h являются
целыми числами, а (
a/h, b/h) = 1. Таким образом, вероятность того, что для
двух случайно выбранных чисел НОД =
h, составляет p
h
= (1/h)(1/h)p
1
. Так как
каждая пара положительных чисел должна иметь
некоторый НОД ≥ 1, мы по-
лучим
∑
∞
=1k
p
k
= 1, т. е., p
1
h=
∞
∑
1
h
– 2
= 1.
Бесконечная сумма
(/ )1 h
∑
2
, как известно [8], равна π
2
/6. Таким обра-
зом, вероятность
p
1
двух случайно выбранных чисел быть взаимно простыми
равна приблизительно 6/
π
2
= 0.6079. Используя этот результат, найдите веро-
ятность того, что два произвольно взятых положительных числа имеют НОД =
1 или 2? Что вы скажите о НОД
> 10? Напишите программу, которая исполь-
зует 1000 случайных пар чисел, и вычислите количество взаимно простых чи-
сел, у которых НОД
≤ 2 и у которых НОД > 10. Сравните результаты с теоре-
тическими предсказаниями. Также используйте все 2500 пар
a и b, где 1 ≤ a ≤
≤ 50 и 1 ≤ b ≤ 50 вместо случайной совокупности пар.
3.7. Упражнение на компьютере
Для вычисления НОД, а именно (330, 140), можно выполнить следую-
щие вычисления, начиная с конца и продолжая к началу: 10 =
50 – 40 = 50 –

Страницы