Извлечение квадратного корня из а по модулю 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;}

Целая часть квадратного корня из CLINT-объекта

void irootj (CLINT nJ, CLINT floorj);

nj (операнд > О)

floor_l (целое число - квадратный корень из nj)

Является ли число n типа CLINT полным квадратом

unsigned int issqrj (CLINT nj, CLINT rj);

nj (операнд)

r_l (квадратный корень из n_1 или 0, если n_1 не является полным квад­ратом)

1, если n_1 - полный квадрат, 0, в противном случае

Расширенный алгоритм Евклида вычисления линейного представ­ления НОД(а, b) = u • а + v • b для натуральных чисел a, b

void xgcdj (CLINT aj, CLINT b_l, CLINT g_l, CLINT u_l, int *sign_u, CLINT v_l, int *sign_v);

a l, bj (операнды)

gj (наибольший общий делитель чисел а_1 и bj)

u_l, vj (коэффициенты при а_1 и b__l в линейном представлении числа gj)

*sign_u (знак коэффициента u_l)

*sign_v (знак коэффициента v_l)

Таблица 1

№ варианта	Верхняя граница поиска	Инициализация переменных	Теоретико-числовые функции
1	83	ULONG	НОД, мультипликативное обратное, извлечение квадратного корня из а по модулю p*q
2	615	Строкой 16-х цифр	НОК, мультипликативное обратное, извлечение квадратного корня из а по модулю М
3	364	Вектором байт длиной 16	НОД, извлечение квадратного корня из а по модулю М, извлечение квадратного корня из а по модулю p*q
4	452	Строкой 8-х цифр	НОК, мультипликативное обратное, извлечение квадратного корня из а по модулю М
5	512	ULONG	НОД, мультипликативное обратное, извлечение квадратного корня из а по модулю М
6	128	Вектором байт длиной 8	НОК, извлечение квадратного корня из а по модулю М, извлечение квадратного корня из а по модулю p*q
7	280	Строкой 10-х цифр	НОД, НОК, мультипликативное обратное
8	754	ULONG	НОД, НОК, извлечение квадратного корня из а по модулю М
9	511	Вектором байт длиной 4	НОД, НОК, извлечение квадратного корня из а по модулю М, извлечение квадратного корня из а по модулю p*q
10	462	Строкой 2-х цифр	Мультипликативное обратное, извлечение квадратного корня из а по модулю М, извлечение квадратного корня из а по модулю p*q
11	375	ULONG	НОД, мультипликативное обратное, извлечение квадратного корня из а по модулю М
12	769	Вектором байт длиной 10	НОК, мультипликативное обратное, извлечение квадратного корня из а по модулю М
13	256	Строкой 10-х цифр	НОД, мультипликативное обратное, извлечение квадратного корня из а по модулю p*q
14	193	ULONG	НОД, НОК, извлечение квадратного корня из а по модулю М
15	222	Строкой 8-х цифр	НОК, извлечение квадратного корня из а по модулю М, извлечение квадратного корня из а по модулю p*q
16	77	ULONG	НОД, извлечение квадратного корня из а по модулю М, извлечение квадратного корня из а по модулю p*q
17	100	Вектором байт длиной 12	Мультипликативное обратное, извлечение квадратного корня из а по модулю М, извлечение квадратного корня из а по модулю p*q
18	404	Строкой 16-х цифр	НОД, НОК, извлечение квадратного корня из а по модулю М, извлечение квадратного корня из а по модулю p*q
19	623	Вектором байт длиной 6	НОД, НОК, мультипликативное обратное
20	95	ULONG	НОД, извлечение квадратного корня из а по модулю М, извлечение квадратного корня из а по модулю p*q

Отчет должен содержать содержать:

1. Наименование и номер лабораторной работы;

2. Условие задачи;

3. Распечатка листинга программы;

4. Распечатка результатов выполнения задачи;

5. Выводы о результатах выполнения задач.