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

⇐ Предыдущая 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 оперирует с двумя категориями...

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

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

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при которых тело находится под действием заданной системы сил...

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

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

Тактические действия нарядов полиции по предупреждению и пресечению групповых нарушений общественного порядка и массовых беспорядков В целях предупреждения разрастания групповых нарушений общественного порядка (далееГНОП) в массовые беспорядки подразделения (наряды) полиции осуществляют следующие мероприятия...

Определение трудоемкости работ и затрат машинного времени На основании ведомости объемов работ по объекту и норм времени ГЭСН составляется ведомость подсчёта трудоёмкости, затрат машинного времени, потребности в конструкциях, изделиях и материалах (табл...

Гидравлический расчёт трубопроводов Пример 3.4. Вентиляционная труба d=0,1м (100 мм) имеет длину l=100 м. Определить давление, которое должен развивать вентилятор, если расход воздуха, подаваемый по трубе, . Давление на выходе . Местных сопротивлений по пути не имеется. Температура...

Огоньки» в основной период В основной период смены могут проводиться три вида «огоньков»: «огонек-анализ», тематический «огонек» и «конфликтный» огонек...

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