Доброго времени суток!
Решаю квадратичные сравнения по описанному тут (стр 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, хотя, вольфрам говорит другое
возможно, в этом алгоритме какие-то пропуски?
подскажите, почему так получается? алгоритм, вроде не сложный, я, вроде как, нигде не ошибся.
Заранее спасибо!

задан 8 Авг '13 23:42

изменен 9 Авг '13 0:44

10|600 символов нужно символов осталось
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

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

(9 Авг '13 13:42) miramentis
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

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

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×529

задан
8 Авг '13 23:42

показан
1315 раз

обновлен
9 Авг '13 13:48

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

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru