Решаю сравнение $%x^2=3022(\mod 7001)$%. В данном примере $% p=3022$%, а $%p=7001$% задан 29 Дек '14 0:38 sany |
@sany: здесь вычисления не доведены до конца. Алгоритм Тонелли - Шенкса требует в общем случае нескольких шагов. То число, которое Вы получили, в квадрате равно $%-3022$%, то есть оно пока отличается от того, что нужно. После второго шага цикла должно получиться $%155$%. Вот ссылка на одно из описаний алгоритма. В Вашем случае, если проделать ещё один шаг итерации и домножить 3664 на $%f^2$%, получится как раз 155. Верные ответы в ряде случаев получаются за счёт того, что у итерации нужен только один шаг, но в общей ситуации их может быть несколько. отвечен 2 Янв '15 1:56 falcao Большое, Вам, спасибо! Разобрался. С Новым Годом!!!
(4 Янв '15 21:31)
sany
|
Надо в общем виде описать используемый метод. Тогда можно будет сказать, что и почему не работает.
Расписал метод решения более подробно.
@sany: в таком виде уже намного понятнее, но пока не ясно, что такое b и a.