Здавалка
Главная | Обратная связь

Китайская теорема об остатках.



Исторически формулируется следующим образом [11]: Любое число от 0 до 9 может быть однозначно представлено в виде пары остатков от деления его на 2 и 5. Историческую формулировку теоремы хорошо характеризует приведенная ниже таблица.

Таблица 2.

x x mod 2 x mod 5

Соответственно все действия над парами остатков однозначно ассоциированы с исходными числами. Например 7 – 3 = 4, или же в остатках (1, 2) – (1, 3) = (0, -1 mod 5) = (0, 4). Данное свойство позволяет организовывать в криптографических приложениях вычисления по типу «разделяй и властвуй». Восстановление же исходных значений по остаткам от деления на два простых числа p и q (частный случай) реализуется при помощи современной формулировки теоремы [10]:

Система сравнений

При НОД(p, q) = 1 имеет единственное решение по модулю p ∙ q, которое определяется по формулам:

Задача 2.1. Восстановить значение x при помощи китайской теоремы об остатках по двум его остаткам от деления a и b, на простые числа p и q соответственно.

 

Пример решения.

Дано: p = 113 q = 127 a = 65 b = 104 Решение:
Найти: T, u, x  

 

Возведение в квадрат

Рассмотрим приведенную ниже таблицу модульного возведения в квадрат ненулевых элементов простого конечного поля F7.

Таблица 3

P = 7
x x2 mod P

Как видно из таблицы, если возвести в квадрат можно любой элемент поля, то квадратный корень может быль извлечен только ровно из половины значений. Такие значения называют квадратичными вычетами. Если квадратный корень из значения извлечь нельзя, то такой элемент поля называют квадратичным невычетом. Также видно, что корни попарно в сумме образуют модуль: x1 + x2 = P. Возможность извлечения квадратного корня по модулю простого и составного числа оценивают при помощи вычисления соответственно символов Лежандра и Якоби.







©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.