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