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

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

0 голосов
/ 29 апреля 2018

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

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

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

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

1 Ответ

0 голосов
/ 29 апреля 2018

Как вы говорите, модули не попарно просты. Вы можете проверить каждую пару (три пары для ваших трех модулей), и единственная пара с 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)

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

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

...