Введение

Слова ``цифра'' и ``шифр'' (устар. ``шифра'') имеют первоисточником арабское            [sifr] - пустое, отсутствующее, нуль.

М.Фасмер ``Этимологический словарь русского языка''

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

Первоначально целью, которую авторы ставили при написании настоящего пособия, было именно изложение основ (начал) теории чисел с небольшой криптографической ``приманкой'' в виде алгоритма RSA - наиболее распространенной на сегодняшний день схемы открытого шифрования. Однако по мере написания пособия увеличивался крен в сторону прикладных и даже технических аспектов информационных технологий; так что если читатель бросит взгляд на последние параграфы, то обнаружит там не столько теорию чисел, но, напротив, больше цитат из художественной литературы, апеллирующих к здравому смыслу.

При отборе и изложении материала авторы руководствовались прежде всего соображениями наглядности и самодостаточности. Для достижения наглядности, мы, во-первых, ввели режим жесткой экономии обозначений и определений, во-вторых, иногда пренебрегали строгостью доказательств в пользу идейных их основ и, в-третьих, все, что представилось возможным, проиллюстрировали примерами:

LONGUM ITER EST PER PRÆCEPTA, BREVE ET EFFIXAX PER EXEMPLA1

Самодостаточность же пособия понимается в том смысле, что все используемые результаты можно найти в нем самом. К сожалению, нам не удалось следовать этому принципу до конца: так, например, студент первого курса университета еще может не знать определения натурального логарифма (с. 17) или метода Ньютона решения уравнений и поэтому идейная основа теоремы 3.16 может по первоначалу ускользнуть от его понимания. Однако же эти исключения не носят принципиального характера, т.е. не будут препятствовать пониманию основных идей.

Этими же принципами мы руководствовались и при изложении в главе 2 основ криптографии открытого ключа: мы включили ровно столько результатов, сколько в состоянии объяснить. В последнее время на русском языке вышло большое количество книг по криптографии; среди них есть и неплохие, как, например, монография А.Саломаа [4]. К сожалению, мы пока не встречали хорошей учебной литературы, по которой человек, совершенно незнакомый с материалом, мог бы самостоятельно его изучить или хотя бы быстро овладеть базовыми его идеями. Именно этим обстоятельством мы и оправдываем появление настоящего пособия. В принципе нетерпеливый читатель может начать чтение сразу с § 7, а к результатам главы 1 обращаться по мере необходимости.

Отдельное замечание касается примеров и упражнений. Без самостоятельного решения читателем упражнений вся теория будет выглядеть несколько умозрительной. Упражнения главы 1 не предполагают использования вычислительной техники сложнее калькулятора. Напротив, упражнения второй главы, иллюстрирующие практическое применение криптографических схем, требуют уже персонального компьютера и специальных пакетов программ, позволяющих производить символьные вычисления. Авторы пользовались пакетом MAPLE V Release 5, который считают достаточно удобным даже для ленивого пользователя. Краткое описание использованных функций можно найти в § 9.

Авторы благодарят Е.А.Калинину за ценные замечания и помощь при наборе.


1(лат.) Долог путь поучений, краток и успешен на примерах.