Сравнение квадратного уравнения по модулю (6 видео)

Квадратичные сравнения по составному модулю.

Рассмотрим сравнение вида x 2 ≡a(mod p α ), где p – простое нечетное число. Как было показано в п.4 §4, решение этого сравнения можно отыскать, решив сравнение x 2 ≡a(mod p). Причем сравнение x 2 ≡a(mod p α ) будет иметь два решения, если a является квадратичным вычетом по модулю p.

Решить квадратичное сравнение x 2 ≡86(mod 125).

125 = 5 3 , 5 – простое число. Проверим, является ли 86 квадратом по модулю 5.

. Исходное сравнение имеет 2 решения.

Найдем решение сравнения x 2 ≡86(mod 5).

Это сравнение можно было бы решить способом, указанным в предыдущем пункте, но мы воспользуемся тем, что квадратный корень из 1 по любому модулю есть ±1, а сравнение имеет ровно два решения. Таким образом, решение сравнения по модулю 5 есть

Подставим получившееся решение в сравнение по модулю 5 2 =25:

Тогда решение сравнения по модулю 25 есть x=±(1+5(1+5t₂))=±(6+25t₂). Подставим получившееся решение в сравнение по модулю 5 3 =125:

Тогда решение сравнения по модулю 125 есть x=±(6+25(1+5t₃))=±(31+125t₃).

Рассмотрим теперь сравнение вида x 2 ≡a(mod 2 α ). Такое сравнение не всегда имеет два решения. Для такого модуля возможны случаи:

1) α=1. Тогда сравнение имеет решение только тогда, когда a≡1(mod 2), и решением будет x≡1(mod 2) (одно решение).

2) α=2. Сравнение имеет решения только тогда, когда a≡1(mod 4), и решением будет x≡±1(mod 4) (два решения).

3) α≥3. Сравнение имеет решения только тогда, когда a≡1(mod 8), и таких решений будет четыре. Сравнение x 2 ≡a(mod 2 α ) при α≥3 решается так же, как сравнения вида x 2 ≡a(mod p α ), только в качестве начального решения выступают решения по модулю 8: x≡±1(mod 8) и x≡±3(mod 8). Их следует подставить в сравнение по модулю 16, затем по модулю 32 и т. д. вплоть до модуля 2 α .

Решить сравнение x 2 ≡33(mod 64)

64=2 6 . Проверим, имеет ли исходное сравнение решения. 33≡1(mod 8), значит сравнение имеет 4 решения.

По модулю 8 эти решения будут: x≡±1(mod 8) и x≡±3(mod 8), что можно представить как x=±(1+4t₁). Подставим это выражение в сравнение по модулю 16

Тогда решение примет вид x=±(1+4t₁)=±(1+4(0+2t₂))=±(1+8t₂). Подставим получившееся решение в сравнение по модулю 32:

Тогда решение примет вид x=±(1+8t₂) =±(1+8(0+2t₃)) =±(1+16t₃). Подставим получившееся решение в сравнение по модулю 64:

Тогда решение примет вид x=±(1+16t₃) =±(1+16(1+2t₄)) =±(17+32t₄). Итак, по модулю 64 исходное сравнение имеет четыре решения: x≡±17(mod 64)и x≡±49(mod 64).

Теперь рассмотрим сравнение общего вида: x 2 ≡a(mod m), (a,m)=1, — каноническое разложение модуля m. Согласно Теореме из п.4 §4, данному сравнению равносильна система

Если каждое сравнение этой системы разрешимо, то разрешима и вся система. Найдя решение каждого сравнения этой системы, мы получим систему сравнений первой степени, решив которую по китайской теореме об остатках, получим решение исходного сравнения. При этом количество различных решений исходного сравнения (если оно разрешимо) есть 2 k , если α=1, 2 k +1 , если α=2, 2 k +2 , если α≥3.

Решить сравнение x 2 ≡4(mod 21).

21 – составное число. Факторизуем его: 21=3·7. Проверим разрешимость исходного сравнения:

, . Сравнение разрешимо и имеет 2 2 =4 решения.

Составим систему: . Решим каждое из уравнений этой системы. Получим . Итак, имеем 4 системы:

1) 2) 3) 4)

Решая каждую из этих систем по китайской теореме об остатках, получим четыре решения: x≡±2(mod 21), x≡±5(mod 21).

Содержание

Функции для решения квадратичных сравнений. Реализация в MATLAB
Введение
Функция для решения сравнений по сложному модулю
Функция для решения квадратичного сравнения по простому модулю
Разложение числа на множители
Вычисление значения символа Лежандра
Возведение числа в степень по методу квадрирования
Решение линейных сравнений
Онлайн НОД и НОК, разложение на множители, сравнения по модулю
🌟 Видео

Видео:✓ Сравнение по модулю. Арифметика остатков | Ботай со мной #034 | Борис ТрушинСкачать

Функции для решения квадратичных сравнений. Реализация в MATLAB

Введение

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

Сразу замечу, так написание функций для решения квадратичных сравнений носило обучающий характер, некоторые пользовательские функции, используемые при вычислении, дублируют функции, уже имеющиеся в среде MATLAB.

Сначала предлагаю рассмотреть код двух главных функций, одна из которых предназначена для решения квадратичных сравнений по составному модулю, а вторая – для решения квадратичных сравнений по простому модулю. При этом мы ознакомимся, в первую очередь с алгоритмом решения квадратичных сравнений, а уже во вторую очередь с функциями, которые необходимы для выполнения самих вычислений.

Функция для решения сравнений по сложному модулю

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

Следующим шагом в решении квадратичного сравнения будет определение типа модуля р. Для этого будет использоваться пользовательская функция factorization, предназначенная для разложения числа на простые множители. Кроме вектора-строки с простыми множителями функция возвращает количество простых множителей. По сути функция factorization дублирует стандартную функцию MATLAB factor.

После того как модуль был разложен на множители с помощью условного оператора осуществляется проверка количества множителей. Если количество множителей превышает 1, то есть модуль р – составное число, то тогда нам необходимо решить систему из sp квадратичных сравнений ( в каждом из сравнений модулем будет служить один из множителей составного модуля р ). Перед тем как браться за решение полученной системы квадратичных сравнений, необходимо убедиться в том, что каждое из квадратичных сравнений этой системы имеет решение. Для этого воспользуемся циклом for, который будет осуществлять переход между элементами вектора с множителями mp. В теле цикла будет вызываться функция, выполняющая вычисление значения символа Лежандра для каждой пары чисел.

Если значения символа Лежандра будет равно 1, то переменная count будет увеличена на 1. Это нужно для того, чтобы после выполнения всех итераций цикла мы могли проверить, все ли уравнения системы имеют решение, ведь от этого зависит, будем ли мы решать квадратичные сравнения из которых состоит система, или выведем сообщения о том, что исходное квадратичное сравнение не имеет решений.

Если количество уравнений системы равняется количеству уравнений, имеющих решения, то создаются векторы-строки для хранения промежуточных результатов вычисления.

С помощью цикла for, осуществляется переход между множителями модуля р. В вектор-строку answer1 записываются результаты решения квадратичного сравнения по простому модулю, который получен с помощью функции sqcom, в которую были переданы значение переменной а, а также значение i-ого множителя модуля p. В вектор-строку modul записывается частное от деления составного модуля р на i-ый множитель модуля p. В вектор-строку answer2 будет сохраняться результат решения линейного неравенства ( p / p( I ) ) * y ≡ 1 ( p ( i) ), которое будет необходимо для расчета окончательного ответа по формуле полученной из Китайской теоремы.

После того как цикл закончил свое выполнение, необходимо рассчитать окончательный ответ по формуле: x=( ( p / p( 1)) * b( 1 ) * y( 1 ) + ( ( p / p( 2) ) * b( 2 ) * y( 2 ) + ( ( p / p( i ) ) * b( i ) * y( i ). Для этого воспользуемся поэлементным умножением. В результате будет получена вектор-строка, сумму элементов которой найдем с помощью команды sum. Найдем остаток от деления суммы на составной модуль р – это будет одним из решений квадратичного сравнения по составному модулю. Второй ответ получим, записав первый ответ с противоположным знаком.

В том случае, если изначально модуль р оказался простым числом, то решение квадратичного сравнения будет получено, путем одноразового вызова функции для решения квадратичного сравнения — sqcom. Второе решение будет получено путем взятия первого ответа с противоположным знаком.

Ниже привожу код функции sqcomdif полностью.

Функция для решения квадратичного сравнения по простому модулю

Эта функция неоднократно вызывалась в функции sqcomdif, и как уже говорилось, функция sqcom применяется для решения квадратичного сравнения по простому модулю и может вызываться независимо от функции sqcomdif, то есть ее можно без проблем вызвать и получить верный ответ в том случае, когда вы уверенны, что модуль – простое число. Так как рассматривается лишь лишение квадратичных сравнений вида x^2 ≡ a ( mod p ), то в функцию необходимо передать числовые значения переменных а и р. В результате работы функции будет получено одно решение квадратичного сравнения.

Так как функция sqcom может использоваться отдельно от функции sqcomdif, то необходимо убедиться в том, что число, записанное в переменную а, является квадратичным вычетом модуля р. Для этого воспользуемся функцией symvol, которая позволяет вычислить значение символа Лежандра для указанной пары чисел.

Если значение переменной Symvol_Lejandra равно 1, то а является квадратичным вычетом по модулю р и будут выполнены дальнейшие действия для нахождения решения квадратичного сравнения. Нам нужно записать число ( р – 1 ) в виде 2^r * q. Начальные значения переменным r, q задаются из расчета, что ( р – 1 ) – нечетное число. Однако если это не так, то они будут изменяться в процессе выполнения цикла ( до тех пор, пока q не станет нечетным числом ).

Теперь необходимо найти значение переменной b, которая равняется b = a^q ( mod p ). Так как а и q, обычно выражены достаточно большими числами, то возвести число а в степень q обычным способом не удастся, так как в большинстве случаев возникнет переполнение. Поэтому возведение в степень необходимо выполнять по методу квадрирования. Для того чтобы выполнить это необходимо вызвать функцию kvadrirovanie и передать в нее значение основания, показателя степени, а также модуля по которому будут выполняться вычисления.

Для продолжения вычислений нужно найти наименьшее неотрицательное число f, которое будет квадратичным невычетом по модулю р. Для этого переменной f, присваивается значение 1, и с помощью функции symvol, определяется значение символа Лежандра для пары чисел f и р. Если символ Лежандра для 1 и р равен 1, то переменная f, с помощью цикла while, увеличивается, до тех пор, пока не будет достигнуто значение, являющееся квадратичным невычетом по модулю р.

Теперь значение f, являющееся квадратичным невычетом по модулю p, необходимо возвести в степень q. Для этого также придется прибегнуть к функции kvadrirovanie, переменной k не обходимо присвоить значение 0.

После вышеперечисленных действий необходимо проверить значение переменной b. Если b сравнимо с 1 по модулю p, то необходимо перейти к расчету ответа, в противном случае найти наименьшее неотрицательное число m, такое что b^( 2^m ) ≡ 1 ( mod p ). Когда такое значение m будет найдено, необходимо пересчитать значения переменных k, g, b, после чего переменной r присвоить значение m. Но это еще не все, необходимо проверить, чтобы новое значение переменной b, также было сравнимо с 1 по модулю р. Если это не так, то необходимо вернуться к подбору числа m. Переменная pok нужна для того, чтобы избежать выполнения определенных математических действий дважды.

После того как было найдено m, удовлетворяющее перечисленным выше условиям, можно переходить к непосредственному вычислению ответа. Ответ вычисляется по формуле x = a^( ( q+1) / 2 ) * g^( k / 2 ) ( mod p ). Для вычисления обеих множителей воспользуемся функцией квадрирования, полученный результат возьмем по модулю p.

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

Ниже приведен полный код функции sqcom:

А теперь предлагаю ознакомиться с вспомогательными функциями, которые используются как при решении квадратичного сравнения, так могут использоваться и отдельно.

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

При решении квадратичного сравнения во многих случаях необходимо прибегать к разложению числа на множители, также к этой операции придется прибегать в тех случаях, когда будет необходимо проверить: является число простым или составным.
В функцию factorization передается число, которое необходимо разложить на множители. В результате функция возвращает вектор — строку с множителями и количество этих множителей.

Функция состоит из оператора switch, который выполняет различные действия в зависимости от значения входной переменной delimoe. Так если delimoe = 1, то в вектор, хранящий результат разложения на множители, mnojitel записывается 1, в переменную ind, хранящую число множителей, также записывается 1. Аналогичные действия выполняются и в том случае, если delimoe равно -1.

Если эти условия не выполнились, то выполняем проверку знака числа, раскладываемого на множители. Если delimoe меньше 0, то в первый множитель записывается -1, в ind записывается 2, и дальнейшая работа функции будет осуществляться с модулем переменной delimoe.Если же число больше 0, то переменной ind присваивается значение 1.

Цикл while работает до тех пор, пока delimoe не равняется delitel, причем изначально переменной delitel присвоено значение 2. При каждой итерации цикла, в переменную ostatok записывается остаток от деления delimoe на delitel. Если остаток равен 0, то есть delitel является множителем delimoe, то это значение записывается в вектор, в котором хранятся множители, а счетчик этого вектора увеличивается на 1. При этом переменной delimoe присваивается частное от выполненного деления. Если же остаток от деления не равен 0, то delitel увеличивается на 1. Когда же происходит выход из цикла, то значение, оставшееся в переменной delimoe, записывается в вектор с множителями, как один из множителей.

Ниже приведу полный код функции factorization.

Вычисление значения символа Лежандра

Для того чтобы проверить является ли число квадратичным вычетом по заданному модулю ( в таком случае квадратичное сравнение имеет решение ) или квадратичным невычетом ( тогда такое квадратичное сравнение не имеет решения ) применяется символ Лежандра, который в отечественной литературе обозначается как L ( a; p ), в зарубежной литературе как L (a / p ).
Символ Лежандра может принимать следующие значения:
L ( a; p ) = 1, в таком случае а принадлежит QR, квадратичное сравнение имеет решение
L ( a; p ) = -1, в таком случае а принадлежит QNR, квадратичное сравнение не имеет решения
Если L ( a; p ) = 0, то а и р не являются взаимно простыми числами, то есть НОД ( а; р ) не равен 1
Для вычисления значения символа Лежандра применяются следующие свойства:

L ( 1; p ) = 1
L ( -1; p ) = ( -1 ) ^ ( ( p — 1 ) / 2 )
L ( 2; p ) = ( -1 ) ^ ( ( p^2 — 1) / 8 )
Если а≡ b*с ( mod p ), то L ( b*с; p ) = L ( b; p ) * L (с; p )
Если а≡ b ( mod p ), то L ( а; p ) = L ( b; p )
Если а и р – простые числа, то L ( а; p ) = (-1) ^( (( p — 1 ) *(a-1)) / 4 ) * L( p; a ). Последнее свойство получило название закона взаимности Гаусса.

Вычисление символа Лежандра выполняется на основе вышеперечисленных свойств. Как только одно из условий выполнилось, начинаем проверять свойства для полученной пары а и р, до тех пор, пока не будет найдено окончательное значение символа Лежандра.
Теперь рассмотрим, как можно реализовать вычисление значения символа Лежандра программно.
Функция будет возвращать значение символа Лежандра для пары чисел а и р, которые были переданы в нее. Это видно из заголовка функции:

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

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

Если а не являлось простым числом, то будем действовать по свойству 4. То есть значение символа Лежандра для пары чисел L ( а; p ), найдем как произведение значений символов Лежандра для чисел, являющихся простыми множителями числа а. Для хранения промежуточных результатов создадим вектор-строку, заполненную нулями с размерностью, равной количеству множителей числа а. Если а – простое, то эта строка будет состоять из одного элемента.

Для вычисления символа Лежандра для каждого множителя поочередно воспользуюсь циклом for, который будет изменять свои значения от 1 до номера последнего множителя. В теле данного цикла происходит непосредственный процесс вычисления значения символа Лежандра с помощью свойств, перечисленных выше.
Код для проверки свойства 1 имеет следующий вид:

Так как при проверке значения символа при его виде L(-1,p), по свойству 2, необходимо вычислить значение ( -1 ) ^ ( ( p — 1 ) / 2 ), то необходимо воспользоваться еще одним условным оператором, в котором будет проверяться, является показатель -1 четным или нечетным числом. В зависимости от этого будет варьироваться значение символа Лежандра. Если показатель четный – то символ Лежандра будет равен 1, в противном случае -1. Применение этого условного оператора позволяет избежать возведение -1 в степень ( р — 1)/2, что является весьма затратной операцией.

Аналогичные действия выполняются и в том случае, когда необходимо вычислить значение символа Лежандра при его виде L ( 2; p ). В таком случае оно будет равняться ( -1 ) ^ ( ( p^2 — 1) / 8 ).

После проверки этого условия число а, передается в функцию, для того, чтобы проверить, простое оно или нет. В случае если число а – составное ( число его множителей ind1 больше 1 ), то происходит рекурсия и число а передается в эту же функцию для выполнения дальнейших вычислений.

В противном случае число а – простое. Если при этом оно не равно -1, 1, 2, то приходится воспользоваться свойством 6 – законом взаимности Гаусса. Знак перед символом Лежандра определяется путем определения четности множителей его показателя. Он обращается в плюс, если хотя бы один из множителей – четный. После чего происходит рекурсивный вызов функции symvol, а аргументы в нее передаются в другом порядке.

В результате проверки вышеперечисленных условий были охвачены все возможные варианты значений числа а.
Если изначально число а было составным, то в переменную sl записывается произведение всех элементов строки — вектора sl, после чего полученное значение возвращается в программу, вызвавшую данную функцию.

Полный код функции symvol:

Возведение числа в степень по методу квадрирования

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

Показатель степени записывается в двоичной системе счисления.
Если он состоит из двух или более бит, под первой 1 записываем число m=a.
Смотрим на следующий справа бит:
- Если это единица то возводим m в квадрат и берем его по модулю р, а полученный результат домножаем на а и берем его по модулю р, окончательный результат записывается в переменную m.
- Если это нуль, то возводим число m в квадрат, берем результат по модулю р, окончательный результат записывается в переменную m.
Переходим к следующему справа биту и повторяем действия описанные в пункте 3, пока не будут выполнены расчеты для последнего бита.

А теперь рассмотрим, как работает функция kvadrirovanie. В функцию передаются значения основания, показателя и модуля, а возвращает функция одно число – конечный результат.

Показатель степени q переведем в двоичный вид, и так как полученный результат будет состоять из отдельных символов, то воспользуемся командой size, для определения количества бит, необходимых для записи показателя степени.

Если для записи показателя степени необходимо два или более битов, то программа выполнит следующие действия: запишет в переменную m типа uint64 число а. После чего с помощью цикла for, который будет изменять значения переменной i от 2 с шагом 1 до количества бит, необходимых для записи показателя степени q, для того, чтобы иметь возможность осуществлять перебор битов.

В теле цикла имеется условный оператор, который, в зависимости от значения i-го бита, будет определять действия, которые необходимо произвести с переменной m. Как писалось выше, если бит равен 1, то необходимо возвести m^2 и взять по модулю р, после чего умножить полученное число на а, и результат взять по модулю р.

Иначе, q(1,i)==’0′, необходимо возвести m^2 и взять его по модулю р.

После выполнения всех повторов цикла, окончательное значение переменной m записывается в переменную result.

В показатель степени в двоичной форме равен 1, то в переменную result записывается само же исходное число, которое требовалось возвести в степень.

Если же и это условие не выполнилось, то следовательно показатель степени равняется 0. В таком случае в переменную result будет записана 1.

Полный код функции для возведения в степень по методу квадрирования:

Решение линейных сравнений

При решении квадратичных сравнений по сложному модулю будет применяться формула, полученная из Китайской теоремы. Для того чтобы рассчитать ответ по этой формуле появляется необходимость решить линейное сравнение k * x ≡ b ( mod p ). Данная функция предназначается для их решения с помощью обратного элемента, то есть такого числа k1 которое при умножении на k, даст результат сравнимый с 1 по заданному модулю р.
В функцию lincom передаются значения коэффициента при неизвестном k, число b, с которым сравнима левая часть, а также модуль p, а возвращает функция соответственно решение линейного сравнения с заданными параметрами.

Как указывалось выше, неравенство будем решать с помощью обратного элемента. Для того чтобы найти обратный элемент воспользуемся расширенным алгоритмом Эвклида для нахождения НОДа. Напомню, что расширенный алгоритм Эвклида позволяет найти НОД с помощью коэффициентов, которые рассчитываются при выполнении каждой операции деления. Для нахождения НОДа по данному алгоритму необходима рассчитать два ( a, b ) коэффициента, но при нахождении обратного элемента нам потребуется только один – b коэффициент, который как раз и будет обратным элементом для k.
В функции необходимо указать начальные значения коэффициентов b0 и b1, которые будут изменяться по мере выполнения расчетов. Если модуль p, который был записан в переменную pr, делится нацело на коэффициент k, то обратный элемент будет равен 1. Иначе b1 будет рассчитываться с помощью цикла while. В цикле будет пересчитываться значения переменной b0. После того как найдено новое значение b0, с помощью функции swap будет осуществляться обмен значений между переменными b0 и b1. Также при каждой итерации цикла будет происходить присвоение новых значений ряду других переменных.

После того, как цикл прекратит свое выполнение будет необходимо рассчитать значение решения линейного сравнения. Оно будет равно произведению переменных b1 и b, взятое по модулю p ( именно для этой операции в начале функции значение модуля было продублировано с помощью переменной pr ).

Видео:Как решать уравнения с модулем или Математический торт с кремом (часть 1) | МатематикаСкачать

Онлайн НОД и НОК, разложение на множители, сравнения по модулю

С помощью данного онлайн-калькулятора можно вычислить НОД и НОК нескольких чисел, разложить число на простые множители, решить линейные и нелинейные сравнения, системы сравнений.

Наибольший общий делитель (НОД, англ. GCD) нескольких целых чисел есть наибольшее из натуральных чисел, которое делит каждое из данных чисел.

Наименьшее общее кратное (НОК, англ. LCM) нескольких целых чисел есть наименьшее из натуральных чисел, которое делится на каждое из данных чисел.

Запишите свои числа через запятую и/или пробел и нажмите кнопку.