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

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

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