Модульная инверсия, включающая деление двух чисел

Я знаю, что (a/b)mod M = ab^-1 mod M

а также, что когда M простое число, тогда b^-1 = b^(M-2)

Мне нужно вычислить (121/2)mod M, где M = 1000000007 (1e9 + 7)

Простым делением: (121/2)modM = (60)mod M = 60%M = 60

Использование модульной инверсии: (121/2)mod M = ( (121 mod M ) * ( 2 ^(M-2) mod M)) ) mod M.

2 ^(M-2) mod M здесь 500000004 (ссылка: http://www.cs.princeton.edu/~dsri/modular-inversion-answer.php?n=2&p=1000000007)

поэтому приведенное выше выражение принимает вид (121 mod M * 500000004)mod M = 60500000484 mod M = 500000064

Что я, возможно, делаю неправильно?


algorithm combinatorics modular-arithmetic
person lassaendie    schedule 03.10.2015    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Вы не можете выполнить целочисленное деление и ожидать того же результата. Ваш расчет действительно должен быть:

121/2 (mod M) = 60 + 1/2 (mod M) = 60 + 50000004 = (mod M) = 50000064

и не

121/2 (mod M) = 60 (mod M)

Поскольку нет определения функции floor из рациональных чисел Q в группу Z_n (определена только для рациональные числа в натуральные числа, floor: Q -> N) вы должны обращаться с делениями в Z_n так же, как с рациональными числами, что использует остатки.

person sve    schedule 03.10.2015
comment
Я делаю целочисленное деление, потому что именно так должно быть получено решение проблемы, которую я решаю. Я должен вывести ответ по модулю M. Окончательный ответ имеет форму этажа (A/2). Числитель формируется после серии шагов сложения и умножения, поэтому я беру мод M на каждом шаге с числителем. В конце у меня есть только A%M, а не фактическое A - person lassaendie; 04.10.2015
comment
@lassaendie, не могли бы вы связать проблему - person sve; 04.10.2015
comment
Боюсь, я не могу, потому что я должен решить это сам. С моей стороны было бы мошенничеством загрузить его - person lassaendie; 04.10.2015
comment
@lassaendie, так в чем именно твоя проблема? вы спрашиваете, почему ваши расчеты дают разные результаты? ответ для 121/2 (mod M) действительно 500000064 - person sve; 04.10.2015
comment
Нет. ответ для 121/2 должен быть 60. Но, как вы сказали, 121/2 mod M действительно 500000064, тогда я полагаю, что застрял. Я на 100% уверен, что ответ правильный. :/ Или, может быть, есть другой способ решить ту же проблему. Есть ли способ сообщить вам о проблеме, не раскрывая ее публично? - person lassaendie; 04.10.2015
comment
@lassaendie answer for 121/2 should be 60 почему ты так думаешь? кто так говорит? - person sve; 04.10.2015
comment
Потому что ответ пол(121/2) - person lassaendie; 04.10.2015
comment
@lassaendie floor(121/2) = 60, но не младше mod M. Вы не можете применить функцию floor при использовании mod M. Функция пола определена для натуральных чисел как floor: N -> N, но при использовании mod M вы работаете с набором Z_M, который полностью отличается от набора N. - person sve; 04.10.2015
comment
Это именно то, что я требую. - person lassaendie; 04.10.2015
comment
@lassaendie That is exactly what i require.. И что это? Придумываем функцию floor для Z_M - person sve; 04.10.2015
comment
Мне потребовалось некоторое время, чтобы понять ответ. Думаю, стоит сказать, что точные деления ведут себя точно так же, как и целочисленные. Проблема всегда в остатке. - person Juan Lopes; 04.10.2015