Теория чисел имеет своим предметом числа и их свойства, числа выступают здесь не как средство или инструмент, а как объект исследования. Натуральные числа изучались еще в Древней Греции (Евклид, Диофант). В XVII веке П. Ферма и в XVIII Л. Эйлер внесли огромный вклад в наши знания о натуральных числах.

 Теория чисел есть конкретная наука. Многие её утверждения допускают практическую проверку, в том числе и с помощью компьютеров. В теории чисел вычисляют давно и очень интенсивно. Всплеск интереса произошел в сравнительно недавнее время в связи с криптографическими приложениями. Потребности криптографии стимулировали исследования классических вопросов теории чисел, в ряде случаев привели к их решению, а также стали источником постановки новых фундаментальных проблем. Задачи, казавшиеся сугубо теоретическими, оказались имеющими большое практическое значение.

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

 В докладе будет рассказано о следующих направлениях исследований в алгоритмической теории чисел.

– Проверка на простоту и построение больших простых чисел.

– Разложение больших целых чисел на множители.

– Дискретное логарифмирование по большому простому модулю.

– Вычислительные задачи на эллиптических кривых.

 Будут указаны связи этих задач с криптографией, затронуты и другие, относящиеся к теме доклада, вопросы.