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

Синтаксис: 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 – простые разные числа.

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

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.

#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,M,x,q,p;

int Test;

 

ULONG a1,M1; // Переменная типа ULONG

{

a1=5; M1=3;

 

u2clint_l(a,a1);

u2clint_l(M,M1);

 

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

printf(" M= %s", ClintToStr(M,10,1));

 

Test= prime_l (M, 1000, 1000); // тест

if(Test==1) //Если тест на простоту пройден

{

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

int Err= proot_l (a, M, x);

if(Err==0) printf(" Yes x= %s\n", ClintToStr(x,10,1));

if(Err==-1) printf(" No \n");

}

else printf(" Error Test M\n ");

}

ULONG q1=7; u2clint_l(q,q1);

 

//Извлечение квадратного корня из а по модулю pq=3*7

 

int Err= root_l (a, M, q, x);

if(Err==0) printf(" Yes x= %s\n", ClintToStr(x,10,1));

if(Err==-1) printf(" No \n");

getch(); return 0;}