Задачи и упражнения

1. Докажите, что для наибольшего общего делителя двух целых чисел а и га, а также любого натурального с, выполнено равенство НОД (ас, тс) = |с| • НОД (а, т). Более того, если НОД (а, с) = 1, то выполнено НОД (а, cm) — НОД (а, га).

Воспользовавшись сформулированными выше равенствами, постройте алгоритм вычисления наибольшего общего делителя чисел, а и т, использующий только операцию деления на двойку (без использования деления с остатком).

2. Докажите обобщенный вариант леммы Безу: для любого натурального п>2и любых целых чисел ai,…, а_п найдутся такие целые числа х,…, х_п, что.

• 3. Пусть задано натуральное число т > 1. Утверждение теоремы 9.6 позволяет нам решить уравнение р (т) = х относительно неизвестного х. Предложите алгоритм решения обратного уравнения If (x) = 771.
• 4. Упростите соотношения (9.18) и (9.19), задающие групповой закон в группе точек эллиптической кривой. Минимизируйте число умножений и сложений в поле К, а также число переменных, используемых для хранения промежуточных значений.

Дополнительная литература к 9-й главе

• 1. Бухштаб АЛ. Теория чисел. — М.:Просвещение. — 1966.
• 2. Дэвенпорт Г. Высшая арифметика.

  Введение

  в теорию чисел.

• — М.:Наука. — 1965.
• 3. Нестеренко А.Ю. Теоретико-числовые алгоритмы в криптографии. — М.:МИЭМ. — 2012.
• 4. Blake /., Seroussi G., Smart N. Elliptic Curves In Cryptography.
• — Cambridge University Press. — 1999.
• 5. Hankerson D., Menezes A., Vanstone S. Guide to elliptic curve cryptography. — Springer — 2004. — 332p.
• 6. Silverman J.H. The Arithmetic Of Elliptic Curves. — Springer.
• — 1986.