Положительно определённые симметрические матрицы и метод наименьших квадратов717 33. Теоретико-числовые алгоритмы

Те ope тико-числовые алгоритмы

Когда-то теория чисел была классическим примером красивой, но совершенно бесполезной области чистой математики. Сейчас теоретико-числовые алгоритмы широко используются - прежде всего в различных криптографических схемах, где нужны большие простые числа. В этой главе мы основные факты и алгоритмы, используемые в такого рода приложениях.

Раздел 33.1 посвящен основам теории чисел (делимость, сравнения по модулю, теорема об единственности разложения на простые множители). В разделе 33.2 рассматривается один из самых древних алгоритмов - алгоритм Евклида поиска наибольшего общего делителя двух целых чисел. В разделе 33.3 мы напоминаем основные факты арифметики в кольцах вычетов. В разделе 33.4 мы изучим остатки, даваемые кратными данного числа а по данному модулю п, и научимся решать уравнение ах = Ь (mod п) при помощи алгоритма Евклида. Раздел 33.5 посвящен «китайской теореме об остатках». В разделе 33.6 рассматриваются остатки от деления степеней данного числа а по фиксированному модулю; излагается алгоритм вычисления аъ mod п при помощи многократного возведения в квадрат. (Этот алгоритм играет важнейшую роль при проверке простоты чисел.) В разделе 33.7 описывается одна из так называемых криптосистем с открытым ключом - система RSA. Раздел 33.8 содержит вероятностный алгоритм проверки чисел на простоту (с его помощью ищут большие простые числа, используемые для генерации ключей в системе RSA). Наконец, в разделе 33.9 мы приведём достаточно эффективный эвристический алгоритм, помогающий разлагать на множители небольшие целые числа. Отметить, что именно отсутствие (на сегодняшний день) эффективного алгоритма разложения чисел на множители позволяет использовать систему RSA; если такой алгоритм найдётся, вся эта система рухнет в одночасье. (Так что отсутствие алгоритма может быть полезнее его существования!) Арифметические операции с длинными числами Работая с большими целыми числами, мы должны договориться, что считать размером входных данных той или иной задачи, а

также условиться относительно стоимости элементарных арифметических операций.

В этой главе под «большим входом» (входом большого размера) мы будем понимать вход, содержащий большие числа (а не вход, содержащий много чисел - как, скажем, в задаче сортировки). Поэтому размер входа мы будем измерять количеством битов, использованных для записи чисел. Алгоритм, получающий на вход целые числа а\, а2, ,ак, называется полиномиальным (polinomial-time algorithm), если время его работы ограничено многочленом от lg а\, lg а2, , lg ttfcj то есть многочленом от длин исходных данных (в двоичной системе счисления).

До сих пор мы обычно считали, что арифметические действия (умножение, деление, вычисление остатка) выполняются за единицу времени. Это было разумно, пока не использовались большие числа, но теперь такой подход перестаёт быть адекватным. Выполнение арифметических операций само становится достаточно трудоёмким. Поэтому число операций теоретико-числового алгоритма естественнее измерять в битовых операциях (bit operations). Например, простейший метод умножения двух /3-битовых целых чисел требует 0(/32) битовых операций. Аналогичным образом деление /3-битового числа на более короткое или вычисление остатка от деления /3-битового числа на более короткое (стандартными методами) требуют 0(/32) битовых операций (см. упр. 33.1-11.)

Как правило, простейшие алгоритмы не являются оптимальными. Например, несложный алгоритм, использующий метод "разделяй и властвуй", умножает два /3-битовых целых числа, делая 0(/31&3) (битовых) операций, а самый быстрый из известных на сегодняшний день алгоритмов требует 0(/3 lg /3 lg lg /3) операций. На практике обычно применяют простейшие алгоритмы, поэтому в наших расчётах мы будем исходить из оценки оценку 0(/32) для умножения и деления.

В этой главе мы будем обращать внимание и на число арифметических, и на число битовых операций.

33.1. Начальные сведения из теории чисел

В этом разделе мы напомним некоторые свойства множеств целых чисел (Z = {...,-2,-1,0,1,2,...}) и натуральных чисел (N={0,1,2,...}).

Делимость и делители.

Говорят, что d делит a (d divides а, запись d \ а), если а = kd при некотором целом к. Синонимы: «d является делителем а» (d is a divisor of а), «а делится на d». «а кратно d» (a is a multiple of d). Число 0 кратно любому числу. Если а > 0 и d \ а, то \d\ \а\. Если