Читать онлайн «Вычислительно сложные задачи теории чисел»

Серия Суперкомпьютерное В учебном пособии подробно рассматриваются четыре задачи, привлекающие внимание Образование исследователей на протяжении последних десятилетий: разложение больших составных чисел на множители, дискретное логарифмирование в мультипликативной группе вы- четов по простому модулю, решение больших разреженных систем линейных уравнений над конечными полями, вычисление ранга эллиптических кривых, определенных над Вычислительно сложные полем рациональных чисел. Наиболее быстрые алгоритмы решения первых двух задач основаны на так называ- емом алгоритме решета числового поля, сводящем их к решению больших разрежен- задачи теории чисел ных систем линейных уравнений над конечными полями. Системы эти настолько вели- ки, что к ним не применимы обычные алгоритмы решения. Используются специальные Е. А. Гречников, С. В. Михайлов, блочные итерационные алгоритмы. Эта область прикладной теории чисел активно развивается во всем мире в связи Ю. В. Нестеренко, И. А. Поповян с приложениями в криптографии. Из-за отсутствия нижних оценок сложности решения этих теоретико-числовых задач, единственным способом проверки надежности исполь- зуемых криптографических алгоритмов служит их практическая проверка с использо- ванием самых совершенных алгоритмов и наиболее мощной вычислительной техники. Вычислительно сложные Ю. В. Нестеренко – чл. корр. РАН, профессор, заведую- щий кафедрой теории чисел механико-математического факуль- тета МГУ, специалист в области теории диофантовых приближе- С. В. Михайлов – кандидат физ. -мат. наук, сотрудник ка- федры теории чисел механико-математического факультета МГУ.