Путь: Математика » Теория чисел

Теория чисел НОД, решение ax+by=1, нахождение обратного элемента по модулю Логарифмические алгоритмы. Используются везде. Тест простоты Рабина Известный, быстрый и часто используемый вероятностный тест на простоту числа Есть детерминированный вариант. Генерация больших простых чисел Полиномиальный алгоритм на основе теоремы Ферма. Разложение на множители Сложнейшая проблема криптоаналитиков. Некоторые представленные алгоритмы требуют серьезной математической подготовки. Перевод из одних систем счисления в другие Проиллюстрированы общие принципы и даны примеры Краткое, но исчерпывающее описание. Квадратный корень по простому модулю Решение сравнения x2=a(mod p) Сложность O(lg4n). Китайская теорема об остатках Разложение числа по вычетам и его восстановление. Период бесконечной дроби 1/n Дано натуральное число n>1 Определить длину периода десятичной записи дроби 1/n. Период бесконечной дроби N/M по основанию P Найти длину периода и сам период бесконечной степенной дроби по основанию Р, представляющей рациональное число N/M. Приближение числа в виде дроби Для действительного числа r>0 и натурального числа qmax необходимо найти наилучшее приближение r в виде рациональной дроби p/q, где q<=qmax. Вычисление символа Якоби (Лежанра) z i p Небольшая статья на английском языке с исходником.   Дополнительные материалы: Алгоритмические проблемы теории чисел. Ю.В. Нестеренко z i p Даны пошаговые описания основных алгоритмов теории чисел. Проблема рассмотрена с математической точки зрения, с соответствующими теоремами и доказательствами.