Система конгруэнций с непарными взаимно простыми модулями

Question

У меня есть набор сравнений

x = a1 (mod n)
...
x = ak (mod nk)

И я хочу найти xэто можно решить с помощью китайской теоремы об остатках и связанных с ней алгоритмов: https://en.wikipedia.org/wiki/Chinese_remainder_theorem

Некоторые примеры: https://rosettacode.org/wiki/Chinese_remainder_theorem

Для этого конкретного примера:

x = 1031 (mod 1473)
x = 1141 (mod 1234)
x = 50   (mod 1827)

Все алгоритмы, которые я попробовал, не будут работать, так как модули не являются попарно взаимно простыми. Тем не мение, 1024360583 является правильным решением:

1024360583 % 1473 == 1031
1024360583 % 1234 == 1141
1024360583 % 1827 == 50

Какой алгоритм мог бы найти такое решение?

Я также реализовал алгоритм Гарнера из Руководства по криптографии: он не решил этот пример.

Answer 1

Как вы говорите, модули не попарно просты. Вы можете проверить каждую пару (три пары для ваших трех модулей), и единственная пара с GCD (наибольший общий делитель) больше 1 равна 1473 а также 1827с GCD из 3, Затем мы ищем все простые числа, которые делят более одного из заданных модулей. (Есть несколько способов сделать это.) Мы находим, что 3 это единственное простое число, которое делит более одного модуля, и наибольшая сила этого простого числа, которое делит более одного модуля 3**1 = 3 (Я использую нотацию для возведения в степень, используемую в Python и Fortran для ясности, поскольку каретка также используется в компьютерах.)

Это может помешать вашей системе уравнений вообще иметь какое-либо решение. Мы можем проверить это, заменив эти модули на их GCD в своих уравнениях и посмотрим, получим ли мы противоречие.

x = 1031 = 2 (mod 3)
x =   50 = 2 (mod 3)

Полученные уравнения являются согласованными, поэтому ваша исходная система может иметь решения. (Если более высокая сила 3 также разделил более одного модуля, который нам также понадобился бы для проверки этих более высоких степеней.) Для каждого обнаруженного нами простого числа и каждого модуля мы находим наибольшую степень этого простого числа, которое делит модуль. В нашем случае мы видим, что 3 водоразделы 1473 но нет 3**2 и это 3**2 водоразделы 1827 но нет 3**3, Итак, наша высшая сила 3**2 = 9 и мы увидели, что уравнения для этой мощности и ниже согласованы.

Теперь мы заменим два соответствующих уравнения новыми уравнениями, заменив модули этими модулями после деления на наибольшую степень простого числа в последнем абзаце. Это означает замену 1473 с 1473 / 3 = 491 а также 1827 с 1827 / 9 = 203, Мы также добавляем новые уравнения, которые мы получаем для каждой степени простого числа, которая делит более одного модуля. Итак, теперь у нас есть четыре одновременных модульных уравнения:

x = 1031 (mod  491)
x = 1141 (mod 1234)
x =   50 (mod  203)
x =   50 (mod    9)  [from your original equation #1, 3]

Мы можем уменьшить правую часть некоторых из этих уравнений, и мы получаем

x =   49 (mod  491)
x = 1141 (mod 1234)
x =   50 (mod  203)
x =    5 (mod    9)

Решения для этой системы также будут работать в вашей оригинальной системе.

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