Алгоритм нахождения равнораспределенного решения линейной конгруэнтной системы - PullRequest
Новая
       16

Алгоритм нахождения равнораспределенного решения линейной конгруэнтной системы

2 голосов
/ 14 декабря 2011

В криптографическом приложении я сталкиваюсь со следующей проблемой: я дал набор линейных конгруэнций 

a[1]*x[1]+a[2]*x[2]+a[3]*x[3] == d[1] (mod p)
b[1]*x[1]+b[2]*x[2]+b[3]*x[3] == d[2] (mod p)
c[1]*x[1]+c[2]*x[2]+c[3]*x[3] == d[3] (mod p)

Здесь x неизвестно a, b, c, d даны

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

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

Мой текущий «безопасный» алгоритм работает следующим образом: Найти все переменные, которые встречаются только в одном уравнении, и назначить случайное значение. Теперь, если в каждой строке не назначена только одна переменная, присвойте значение в соответствии с конгруэнтностью. Иначе не получится.

Может кто-нибудь подсказать, как вообще решить эту проблему?

1 Ответ

2 голосов
/ 14 декабря 2011

Вы можете использовать исключения Гаусса и аналогичные алгоритмы, как вы учили в курсах линейной алгебры, но вся арифметика выполняется по модулю p (p - простое число). Одно важное отличие заключается в определении «деления»: для вычисления a / b вместо этого вы вычисляете a * (1 / b) (на словах «a times b inverse»). Рассмотрим следующие изменения в математических операциях, которые обычно используются

  • дополнение: a + b становится a + b mod p
  • вычитание: a-b становится a-b модом p
  • умножение: a * b становится a * b mod p
  • деление: a / b становится: если p делит b, то «ошибка: деление на ноль», иначе a * (1 / b) mod p

Чтобы вычислить обратную величину b mod p, вы можете использовать расширенный евклидов алгоритм или альтернативно вычислить b ** (p-2) mod p.

Вместо того, чтобы пытаться свернуть это самостоятельно, найдите существующую библиотеку или пакет. Я думаю, что, возможно, Sage сможет это сделать, и, конечно, Mathematica, Maple и другие подобные математические инструменты могут это сделать.

...