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

⇐ Предыдущая 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. Нарушение авторских прав; Мы поможем в написании вашей работы!

Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...

Вычисление основной дактилоскопической формулы Вычислением основной дактоформулы обычно занимается следователь. Для этого все десять пальцев разбиваются на пять пар...

Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...

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

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

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

Типовые ситуационные задачи. Задача 1.У больного А., 20 лет, с детства отмечается повышенное АД, уровень которого в настоящее время составляет 180-200/110-120 мм рт Задача 1.У больного А., 20 лет, с детства отмечается повышенное АД, уровень которого в настоящее время составляет 180-200/110-120 мм рт. ст. Влияние психоэмоциональных факторов отсутствует. Колебаний АД практически нет. Головной боли нет. Нормализовать...

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

Йодометрия. Характеристика метода Метод йодометрии основан на ОВ-реакциях, связанных с превращением I2 в ионы I- и обратно...

Броматометрия и бромометрия Броматометрический метод основан на окислении восстановителей броматом калия в кислой среде...

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