Криптографические протоколы - Доказательство принадлежности числа множеству квадратичных вычетов

Понедельник, 29.04.2024, 01:14

Криптографические протоколы

Главная

Регистрация

Вход

Приветствую Вас, Гость · RSS

Меню сайта

Форма входа

Поиск

Счетчики

Доказательство принадлежности числа множеству квадратичных вычетов

ДОКАЗАТЕЛЬСТВО ПРИНАДЛЕЖНОСТИ ЧИСЛА МНОЖЕСТВУ КВАДРАТИЧНЫХ ВЫЧЕТОВ		Протокол QR
Протокол интерактивного доказательства	Протокол доказательства с нулевым разглашением

Постановка задачи

Пусть - множество натуральных чисел, $n \in N$ и $Z_n^* = \{x\vert 1\leq x < n, (n,x)=1\}$ множество натуральных чисел, меньших чем и взаимно простых с . $x \in Z_n^*$ называется квадратичным вычетом по модулю , если существует такой , что $y^2 \equiv x\pmod n$ . В противном случае, $x \in Z_n^*$ называется квадратичным невычетом по модулю .