Функции для решения квадратичных сравнений. Реализация в MATLAB
17 min
Tutorial
Введение
Для решения криптографических задач необходимо уметь решать квадратичные сравнения по заданному модулю. Алгоритм решения квадратичного сравнения достаточно прост и не вызывает сложностей в решении при небольших значениях модуля и свободного члена, однако в связи с применением достаточно больших чисел в криптографии, решение квадратичных сравнений вручную является весьма кропотливым и длительным процессом. Конечно, для решения квадратичных сравнений можно воспользоваться онлайн-сервисом. Но так как решение криптографической задачи не заканчивается на решении квадратичного сравнения, то человеку, занимающемуся криптографией, будет удобно иметь функцию, способную решать квадратичные сравнения и свободно взаимодействовать с другими функциями, которые используются ним. Именно поэтому было решено написать функцию для решения квадратичных сравнений вида x^2 ≡ a ( mod p ), где a и p — взаимно простые числа, в MATLAB.
