теория-чисел - Квадратичные сравнения. Алгоритм Шенкса-Тонелли

Question

Доброго времени суток!
Решаю квадратичные сравнения по описанному тут (стр 35) алгоритму Шенкса-Тонелли.

Но, для p=113, a=9112093 ≡ 112(mod 113) этот алгоритм выдает неправильное значение 48.

мои значения переменных:

p= 113 = 7* 2^4 +1
r = 4;  s = 7
Исходные значения:
lambda0 = -1  
w0 = 1

Порядок элемента lambda0:  
ord(lambda0) = 2^1 =>
m = 1

Произвольный квадратный невычет:
z = 3
y=z^s(mod p)=3^7(mod 113)=40
d=2^(r-m)=2^(4-1)=8
y^d = -1
y^(d-1) = 48

lambda = lambda0*y^d = 1
w = w0*y^(d-1) = 48

в итоге ответ 48, хотя, вольфрам говорит другое
возможно, в этом алгоритме какие-то пропуски?
подскажите, почему так получается? алгоритм, вроде не сложный, я, вроде как, нигде не ошибся.
Заранее спасибо!

falcao 291k●9●38●53 · Accepted Answer

1

Там, судя по всему, опечатка в тексте. Когда говорится о том, что $%y$% в степени $%2^r$% равно 1 по модулю $%p$%, то дальше должно быть сказано, что $%y$% в степени $%2^{r-1}$% будет равно $%-1$%. Так должно быть, чтобы после возведения в квадрат число $%-1$% перешло в 1. В тексте же указан показатель $%2^r-1$%, что не соответствует действительности.

Соответственно, у Вас получилось, что $%y^8$% равно $%-1$%, поэтому для нахождения квадратного корня надо брать $%y^4$%. Получится остаток $%98$%, то есть $%\pm15$%.

ссылка

отвечен 9 Авг '13 12:48

falcao
291k●9●38●53

Спасибо! Опять очень помогли.
Правда, не понятно, как неправильный алгоритм работал на некоторых числах

(9 Авг '13 13:42) miramentis

world-sudya 1 · Answer 2

0	чтобы найти корень из -1 для чисел P=4k+1 достаточно любой квадратичный невычет возвести в степень (p-1)/4. Здесь 3^28(mod113) дает искомый ответ. ссылка отвечен 14 Янв '20 21:21 world-sudya 1 10\|600 символов нужно символов осталось

теория-чисел - Квадратичные сравнения. Алгоритм Шенкса-Тонелли

2 ответа

Здравствуйте

Связанные исследования

Связанные вопросы

Отслеживать вопрос