Решаю сравнение $%x^2=3022(\mod 7001)$%. В данном примере $% p=3022$%, а $%p=7001$%
Получаю следующие значения переменных:
Раскладываю $%р-1$%, по следующей формуле: $%p-1=q \cdot 2^r$%;
$%7001 - 1 = 875 \cdot 2^3$%
Следовательно $%r=3$%; $%q=875$%;
Найду $% b $% по формуле $% b=a^q(\mod 7001) $%
Ищу наименьший квадратичный невычет:
$%L(2;7001)=1$%,
$%L(3;7001)=-1$%, следовательно $%f=3$%;
$%g=f^q=3477$%;
Ищу наименьшее неотрицательное $%m$% при котором остаток от $%b^{2^m}$% будет равен 1 по модулю 7001. Такое значение получается при $%m=2$%. Рассчитаю значение $%k$%: $%k=2^{r-m}=2^{3-2}=2$%;
По формуле Шенкса $%x = a^{(q-1)/2}g^{k/2} (\mod 7001)$% получаю ответ $%3664$%, что не есть верно. wolfram дает ответ $%+(-)155$%, что является правильным ответом.
Подскажите, пожалуйста, где допущена ошибка, для большинства других значений, написанная программа работает, при расчете вручную получаю то же самое неверное решение.

задан 29 Дек '14 0:38

изменен 2 Янв '15 1:03

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

(29 Дек '14 1:29) falcao

Расписал метод решения более подробно.

(30 Дек '14 13:40) sany

@sany: в таком виде уже намного понятнее, но пока не ясно, что такое b и a.

(30 Дек '14 17:19) falcao
10|600 символов нужно символов осталось
0

@sany: здесь вычисления не доведены до конца. Алгоритм Тонелли - Шенкса требует в общем случае нескольких шагов. То число, которое Вы получили, в квадрате равно $%-3022$%, то есть оно пока отличается от того, что нужно. После второго шага цикла должно получиться $%155$%.

Вот ссылка на одно из описаний алгоритма. В Вашем случае, если проделать ещё один шаг итерации и домножить 3664 на $%f^2$%, получится как раз 155.

Верные ответы в ряде случаев получаются за счёт того, что у итерации нужен только один шаг, но в общей ситуации их может быть несколько.

ссылка

отвечен 2 Янв '15 1:56

изменен 2 Янв '15 2:07

Большое, Вам, спасибо! Разобрался. С Новым Годом!!!

(4 Янв '15 21:31) sany
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×930
×97
×57

задан
29 Дек '14 0:38

показан
1012 раз

обновлен
4 Янв '15 21:58

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

по почте:

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

по RSS:

Ответы

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

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