1-ый вариант.
Общий вход: - квадратная матрица большого порядка, вещественное число .
1) Первый шаг проверяющего: преобразовывает так, чтобы не изменился, применяя соответствующие свойства определителей достаточное количество раз (предполагается, что на такие преобразования у него достаточно ресурсов). Получает матрицу такую, что . Затем преобразовывает так, чтобы изменился, т.е. получает такую, что . отправляет и доказывающему и просит его вычислить их определители.
2) Первый шаг доказывающего: вычисляет определители полученных матриц и отправляет их значения проверяющему.
3) Второй шаг проверяющего: проверяет, если или , то останавливает проверку и отвергает доказательство.
и повторяют шаги 1) и 3) раз.
Проверяющий принимает доказательство, если он завершит итераций шагов 1) - 3). В противном случае, отвергает.
2-ой вариант.
Общий вход: - квадратная матрица большого порядка, вещественное число .
1) Первый шаг проверяющего: наугад выбирает бит . Если , то преобразовывает так, чтобы не изменился, применяя соответствующие свойства определителей достаточное количество раз (предполагается, что на такие преобразования у него достаточно ресурсов). Получает матрицу такую, что . Если , то преобразовывает так, чтобы изменился, т.е. получает такую, что . отправляет доказывающему и просит его вычислить определитель матрицы .
2) Первый шаг доказывающего: вычисляет определитель полученной матрицы и отправляет его значение проверяющему.
3) Второй шаг проверяющего: проверяет, если или , то останавливает проверку и отвергает доказательство.
и повторяют шаги 1) и 3) раз.
Проверяющий принимает доказательство, если он завершит итераций шагов 1) - 3). В противном случае, отвергает.
|