Вычисление мультипликативного обратного

Синтаксис: void inv_l (CLINT a, CLINT M, CLINT g ,CLINT a_1);

Вход: a, M (операнды)

Выход: g (наибольший общий делитель чисел а и M)

a_1 (обратный элемент к a mod M, если он существует)

Листинг программы, реализующей вычисление мультипликативного обратного

#include <FLINT.h>

#include <stdio.h>

#include <conio.h>

#include <math.h>

#define ClintToStr xclint2str_l // Переопределение функции xclint2str_l

int main(int argc, char* argv[])

{

CLINT a,b,c,ed;

CLINT g , a_1 ;

char *s1 =new char;s1="7"; // Строка 10-х цифр

str2clint_l (a,s1,10);//Инициализация строкой

char *s2 =new char;s2="13"; // Строка 10-х цифр

str2clint_l (b,s2,10);//Инициализация строкой

char *s3 =new char;s3="1"; // Строка 10-х цифр

str2clint_l (ed,s3,10);//Инициализация 1

printf("a=%s\n",ClintToStr(a,10,1));

printf("b=%s\n",ClintToStr(b,10,1));

// Наибольший общий делитель (НОД)

gcd_l ( a, b, c);

printf("HOD(a,b)=%s\n",ClintToStr(c,10,1));

// Вычисление мультипликативного обратного

inv_l (a, b, g , a_1);

if( cmp_l( g, ed)==0) printf("x_1= %s\n",ClintToStr(a_1,10,1));

getch(); return 0;

}

Извлечение квадратного корня из а по модулю M

Извлечением квадратного корня из числа апо модулю Mявляется процедура нахождения такого x, для которого справедливо сравнение

x ² ≡ a (mod M)

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

Если НОД(а,M) =1 и существует одно решение b такое, что b ≡ a mod M, то числоа называется квадратичным вычетом по модулю M.

Если сравнение неразрешимо, то число а называется квадратичным невычетом по модулю M.

Если число M простое, то найти квадратные корни по модулю Mдовольно просто.

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

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

В FLINT/C описана следующая функция, позволяющая совместно с функцией проверки числа на простоту, выполнить извлечение квадратного корня из апо модулю M .

Извлечение квадратного корня из а по модулю M

Синтаксис: int proot_l (CLINT a, CLINT M, CLINT x);

Вход: a (операнд, a ≠ M)

M (операнд, M > 2 – простое, M≠ a)

Выход: x (квадратный корень из а по модулю р)

Возврат: 0, если а - квадратичный вычет по модулю р,

-1 в противном случае

Извлечение квадратного корня из а по модулю p*q

Извлечением квадратного корня из числа апо модулю p*q является процедура нахождения такого x, для которого справедливо сравнение

x ² ≡ a (mod p*q)

НОД(а, p*q)=1, p и q – простые разные числа.

Поскольку известно разложение модуля на сомножители, то данное сравнение эквивалентно системе сравнений:

Вычисление мультипликативного обратного - student2.ru x ² ≡ a (mod p)

x ² ≡ a (mod q)

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

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

Извлечение квадратного корня из а по модулю p*q

(числа pиq нечетные и взаимно простые )

Синтаксис: int root_l (CLINT a, CLINT p, CLINT q,CLINT x);

Вход: a (операнд, a ≠ M)

p (операнд, p> 2 , p≠ q)

q (операнд, q> 2 , p≠ q)

Выход: x (квадратный корень из а по модулю р)

Возврат: 0, если а - квадратичный вычет по модулю р,

-1 в противном случае

Ниже приведен листинг программы реализующей функции:

извлечения квадратного корня из числа а по модулю М;

извлечения квадратного корня из числа а по модулюp*q.