Математика: Теория чисел.

Быстрое возведение в степень по модулю

Логарифмический алгоритм возведения в степень. Применяется практически везде.

Алгоритм Евклида вычисления НОД и НОК.

Решение уравнения ax + by =1.

Нахождение обратного элемента по модулю.

Логарифмические алгоритмы. Используются везде.

Тест простоты Рабина.

Известный, быстрый и часто используемый вероятностный тест на простоту числа. Есть детерминированный вариант.

Генерация больших простых чисел.

Полиномиальный алгоритм на основе теоремы Ферма.

Разложение на множители

Сложнейшая проблема криптоаналитиков. Некоторые представленные алгоритмы требуют серьезной математической подготовки.

Перевод из одних систем счисления в другие

Проиллюстрированы общие принципы и даны примеры. Краткое, но исчерпывающее описание.

Квадратный корень по простому модулю

Решение сравнения x²=a(mod p). Сложность O(lg⁴n).

Китайская теорема об остатках.

Разложение числа по вычетам и его восстановление.

Длинные числа и операции с ними. Метод Шенхаге-Штрассена. FFT

Подробное описание алгоритмов с исходниками на Си.

Период бесконечной дроби

Найти длину периода и сам период бесконечной степенной дроби по основанию Р, представляющей рациональное число N/M

Приближение числа в виде дроби

Для действительного числа r>0 и натурального числа q_max необходимо найти наилучшее приближение r в виде рациональной дроби p/q, где q<=q_max

Информацию о решении интересных задач можно также найти в разделе Олимпиадные задачи: арифметика.

Архив статей.

Fast Machine Code for Modular Multiplication

Cоздание онкретных ассемблерных программ, реализующих быстрое умножение по модулю.

Алгоритмические проблемы теории чисел. Ю.В. Нестеренко

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

Вверх по странице, к оглавлению и навигации