Формальное описание

⇐ Предыдущая 1 2 345 6 7 8 9 10 Следующая ⇒

Входные данные: a — целое число, b — натуральное, нечётное, больше единицы.

Выходные данные: — символ Якоби

1 (проверка взаимной простоты). Если НОД (a, b)≠1, выход из алгоритма с ответом 0. 2 (инициализация). r:=1 3 (переход к положительным числам). Если a<0 то a:=-a Если b mod 4 = 3 то r:=-r Конец если 4 (избавление от чётности). t:=0 Цикл ПОКА a – чётное t:=t+1 a:=a/2 Конец цикла Если t – нечётное, то Если b mod 8 = 3 или 5, то r:=- r. Конец если 5 (квадратичный закон взаимности). Если a mod 4 = b mod 4 = 3, то r:=- r. c:=a; a:=b mod c; b:=c. 6 (выход из алгоритма?). Если a ≠0, то идти на шаг 4, иначе выйти из алгоритма с ответом r.

Комментарии к алгоритму.

В алгоритме везде берётся наименьший положительный вычет (то есть остаток от деления).

На четвёртом шаге используется мультипликативность символа Якоби, а затем вычисляется символ Якоби . Чтобы избежать лишнего возведения в степень, проверяется только остаток от деления b на 8.

На пятом шаге тоже вместо возведения в степень используется проверка остатков от деления.

Сложность алгоритма равна битовых операций.

⇐ Предыдущая 1 2 345 6 7 8 9 10 Следующая ⇒

Дата добавления: 2015-04-19; просмотров: 394. Нарушение авторских прав; Мы поможем в написании вашей работы!

Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...

Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...

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

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

Закон Гука при растяжении и сжатии Напряжения и деформации при растяжении и сжатии связаны между собой зависимостью, которая называется законом Гука, по имени установившего этот закон английского физика Роберта Гука в 1678 году...

Характерные черты официально-делового стиля Наиболее характерными чертами официально-делового стиля являются: • лаконичность...

Расчет концентрации титрованных растворов с помощью поправочного коэффициента При выполнении серийных анализов ГОСТ или ведомственная инструкция обычно предусматривают применение раствора заданной концентрации или заданного титра...

Психолого-педагогическая характеристика студенческой группы Характеристика группы составляется по 407 группе очного отделения зооинженерного факультета, бакалавриата по направлению «Биология» РГАУ-МСХА имени К...

Общая и профессиональная культура педагога: сущность, специфика, взаимосвязь Педагогическая культура- часть общечеловеческих культуры, в которой запечатлил духовные и материальные ценности образования и воспитания, осуществляя образовательно-воспитательный процесс...

Studopedia.info - Студопедия - 2014-2026 год . (0.012 сек.) русская версия | украинская версия