Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Решение. Найти все мультипликативные обратные пары в Z11


Пример

Найти все мультипликативные обратные пары в Z11.

Мы имеем семь пар: (1, 1), (2, 6), (3, 4), (5, 9), (7, 8), (9, 9) и (10, 10). При переходе от Z10 к Z11 число пар увеличивается. При Z11 НОД (11, a) = 1 (взаимно простые) для всех значений a, кроме 0. Это означает, что все целые числа от 1 до 10 имеют мультипликативные инверсии.

Целое число a в Zn имеет мультипликативную инверсию тогда и только тогда, если НОД (n, a) = 1(mod n)

Расширенный алгоритм Евклида, который мы обсуждали ранее в этой лекции, может найти мультипликативную инверсию b в Zn, когда даны n и b и инверсия существует. Для этого нам надо заменить первое целое число a на n (модуль). Далее мы можем утверждать, что алгоритм может найти s и t, такие, что . Однако если мультипликативная инверсия b существует, НОД (n, b) должен быть 1. Так что уравнение будет иметь вид

(s × n) + (b × t) = 1

Теперь мы применяем операции по модулю к обеим сторонам уравнения. Другими словами, мы отображаем каждую сторону к Zn. Тогда мы будем иметь

(s × n + b × t) mod n =1 mod n

[(s × n) mod n] + [(b × t) mod n] = 1 mod n

0 + [(b × t) mod n ] = 1

(b × t) mod n =1 Это означает, что t – это мультипликативная инверсия b в Zn

Обратите внимание, что на третьей строке — 0, потому что, если мы делим , частное — s, а остаток — 0.

Расширенный алгоритм Евклида находит мультипликативные инверсии b в Zn, когда даны n и b и НОД (n, b) = 1. Мультипликативная инверсия b — это значениеt, отображенное в Zn.

Рисунок показывает, как мы находим мультипликативную инверсию числа, используя расширенный алгоритм Евклида.


Пример

Найти мультипликативную инверсию 11 в Z26.

<== предыдущая лекция | следующая лекция ==>
Решение. Найти мультипликативную инверсию 8 в Z10 | Решение. Мы используем таблицу, аналогичную одной из тех, которые мы уже применяли прежде при данных r1 = 26 и r2 = 11

Дата добавления: 2014-01-03; Просмотров: 776; Нарушение авторских прав?


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:

  1. АНАЛИЗ ОСНОВНЫХ ФУНКЦИЙ УПРАВЛЕНИЯ ПЕРСОНАЛОМ. РЕШЕНИЕ ПРОБЛЕМ ОПЛАТЫ ТРУДА
  2. В течение какого срока налоговый орган может принять решение о привлечении к ответственности за неуплату налога по ст. 122 НК РФ?
  3. Взаимосвязь нормирования труда с решением производственных вопросов.
  4. Градостроительное решение реконструкции объекта
  5. Декодирование с мягким решением.
  6. Дополнительное решение
  7. Какие этапы включает в себя решение задач с помощью компьютера?
  8. Какие этапы включает в себя решение задач с помощью компьютера?
  9. Маркетинговое решение оптовых и розничных торговцев.
  10. Оптимальное решение двойственной задачи
  11. Освоение политологической проблематики предполагает решение целого ряда задач.
  12. Основанием для заключения договора коммерческого найма является решение уполномоченного исполнительного органа государственной или муниципальной власти.

studopedia.su - Студопедия (2013 - 2020) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.002 сек.