Сайт о программировании, математике и моделировании
Записи с метками метод Ферма
Длинные числа. Вычисление обратного по модулю
3 Декабрь
При проверке ЭЦП необходимо вычислить величину v = (h(M1))q-2 (mod q). Это можно сделать, по крайней мере, двумя способами:
возведением в степень и вычислением обратного с помощью расширенного алгоритма Евклида. Действительно, в теории чисел известна малая теорема Ферма, которая утверждает, что если р — простое число, а – целое число, не делящееся на р, то ар-1 ≡ 1 (mod p). Читать дальше >
Методы проверки на простоту
1 Декабрь
Все алгоритмы проверки простоты делятся на две больших подгруппы: детерминированные и вероятностные проверки. Алгоритмы первой группы позволяют точно сказать, является число простым или составным. Алгоритмы второй группы позволяют это определить, но с некоторой вероятностью ошибки. Многократное их повторение для одного числа, но с разными параметрами, обычно позволяет сделать вероятность ошибки сколь угодно малой величиной. Читать дальше >
Теория чисел
1 Декабрь
Числа 1,2,3,… называются натуральными. Число 0, а также числа вида ±a, где a натуральное число, называются целыми числами. Отношение двух целых чисел называется рациональной дробью и является формальной записью результата деления одного числа на другое. Деление на ноль не определено. Простым числом называется натуральное число, у которого есть в точности два неравных натуральных делителя. Наибольшим общим делителем двух целых чисел a и b называется наибольшее целое число, которое делит как a, так и b. Обозначения: (a,b) или НОД(a,b). Читать дальше >
