Онлайн калькулятор: Обратный элемент в кольце по модулю

В теории криптографических преобразований достаточно часто приходится сталкиваться с трудоемкой задачей вычисления обратных величин по модулю. Во многих криптографических задачах для заданных чисел «а» и «Р» требуется нахождение числа «d» меньшего «Р» ( d < P ), чтобы выполнялось единичное сравнение a * d mod P ≡ 1.

Необходимо отметить , что такое число «d» существует, если числа «а» и «Р» взаимно простые, при этом число «d» называют инверсией числа «а» по модулю «Р» и обозначают как: а-1 mod P. Например, требуется определить инверсию 6-1 mod 17; необходимо найти такое число, которое при умножении на число 6 и делении этого произведения на число 17 в остатке образует число 1.

В рассматриваемом примере таким числом будет являться число 3, т.к. 6 * 3 mod 17 ≡ 1, следовательно, число 3 является инверсией числа 6 по модулю 17.

Для вычисления обратных величин при условии, что если Р — простое число, что практически справедливо для всех криптографических задач асимметричной криптографии, можно воспользоваться малой теоремой Ферма.

Малая теорема Ферма интерпретируется следующим образом: если «Р» — простое число, «а» — целое число, то инверсию числа «а» по модулю «Р» можно определить как:

а-1 (mod Р) = аφ(P) – 1 mod P

где: φ (Р) – функция Эйлера;

для простых чисел φ (Р) = Р – 1.

Функция Эйлера указывает сколько во множестве чисел от 0 до Р, есть чисел взаимно простых с Р.

Например, если Р = 17, то φ (Р) = Р-1 = 17-1 = 16. Требуется вычислить инверсию числа 2 по модулю 17, т.е. вычислить 2-1 mod 17.

2-1mod 17 = 2φ(P) – 1mod Р = 215mod 17 = 32768 mod 17 = 9 mod 17 → 9.

Следовательно, число 9 является инверсией числа 2 по модулю 17, т.к.

2 * 9 mod 17 = 18 mod 17 = 1 mod 17 → 1.


⇐ Предыдущая12345678910Следующая ⇒


Дата публикования: 2014-10-25; Прочитано: 2533 | Нарушение авторского права страницы



studopedia.org — Студопедия.Орг — 2014-2018 год.(0.001 с)…

Модули

В этой лекции мы рассмотрим:

  • Модули
  • неравенства с участием модулей
  • Теорема 1.2.2 (√a2=|a|)
  • Теорема неравенства

1.2.1 Определение

Абсолютное значение или модуль действительного числа a (обозначается как |a|) определяется как


      Пример
|5|=5     Так как 5>0
|-4/7|= -(-4/7) = 4/7   Так как -4/7 |0|=0     Так как 0≥0


      Замечание
|a| есть не отрицательным числом для всех значений a и
-|a|≤ a ≤ |a|

Если a является негативным тогда -a позитивно и +a отрицательное!!!


      Пример
Solve       |x-3|=4
Решение

x-3= 4
    x= 7
    -(x-3)= 4
    x-3= -4
       x= -1

      Пример
Решите уравнение |3x-2|=|5x+4|

3x-2   = 5x+4
3x-5x = 4+2
    -2x = 6
       x = -3
    3x-2 = -(5x+4)
    .
    .
    .
       x = -1/4

      КВАДРАТНЫЕ КОРНИ И МОДУЛИ
            b2 = a

          (3)2 = 9
          so b = 3
но!!!
  (-3)2 = 9 то есть b = -3


Позитивный корень квадрата числа равен этому числу.


      ТЕОРЕМА 1.2.2
Для любого действительного числа a
            √a2 = |a|
e.g.
      √(-4)2 = √16 = 4 = |-4|


      ТЕОРЕМА 1.2.3
Если a и b действительные числа, тогда

  1. |-a| = |a|    число a и его отрицательное значение имеет одинаковые модули.
  2. |ab| = |a||b|    Модуль произведения двух чисел есть произведение их модулей.
  3. |a/b| = |a|/|b|    Модуль отношения двух чисел есть отношение их модулей.

      Доказательство
Из теоремы 1.2.2

(a)  |-a| = √(-a)2 = √a2 = |a|

(b)  |ab| = √(ab)2 = √a2b2 = √a2√b2 = |a||b|


      Примеры

(a)  |-4| = |4|

(b)  |2.-3| = |-6| = 6 = |2|.|3| = 6

(c)  |5/4| = 5/4 = |5|/|4| = 5/4


     Результат (b) вышеизложенной теоремы может быть применено к трем или более членам.

Для n действительных чисел
a1, a2, a3,…an

(a) |a1 a2 …an| = |a1| |a2| …|an|
(b) |an| = |a|n


      Геометрическое представление модуля

Где A и B есть точки с координатами a и b. Расстояние между A и B есть


      Теорема 1.2.4 (Формула расстояния)
    Если A и B — точки на координатной прямой с координатами a и b соответственно, тогда расстояние d между A и B
        d = |b — a|


      ТАБЛИЦА 1.2.2 (a)
                    |x-a| < k (k>0)

          Альтернативная форма     -k < x-a < k
          Искомые значения находятся           (a-k, a+k)


      Пример
Неравенство
  |x-3| < 4
можно выразить как
  -4 < x-3 < 4
добавление 3 к обеим частям приводит к
  -1 < x < 7
Искомые значения находятся (-1,7)

                        On real line


      Пример
Решите |x+4| ≥ 2

x+4 ≤ -2
x ≤ -6
    x+4 ≥ 2
x≥ -2

Объединение двух неравенств дает
                (-∞ , -6] ∪ [-2 , +∞ )

                          На численной прямой


      НЕРАВЕНСТВО ТРЕУГОЛЬНИКА

Не всегда верно, что
|a+b| = |a| + |b|
например
если a = 2 и b = -3, тогда a+b = -1 и поэтому |a+b| = |-1| = 1
в то время как
|a|+|b| = |2|+|-3| = 2+3 = 5 поэтому |a+b| = |a|+|b|


      1.2.5 ТЕОРЕМА — (Неравенство треугольника)
Если   a  b  тогда |a+b| ≤ |a|+|b|
      Доказательство
Так как для любого действительного числа a и b, мы знаем, что
-|a| ≤ a ≤ |a|   and   -|b| ≤ b ≤ |b|
          -|a| ≤ a ≤ |a|
                   +
          -|b| ≤ b ≤ |b|
      ______________
= -|a| + -|b| ≤ a+b ≤ |a|+|b|
______________________________________________
Сейчай мы имеем два случая:

Первый случай, где a+b ≥ 0
определенно: a+b=|a+b|
Отсюда
        |a+b| ≤ |a|+|b|

И

Второй случай где a+b < 0
        |a+b| = -(a+b)
                или
        (a+b) = -|a+b|

По сравнению с начальной неравенство
-(|a|+|b|) ≤ -|a+b|
  Следует результат
_______________________________

У меня есть инструкции по созданию контрольной суммы сообщения, описанного следующим образом:

Контрольная сумма состоит из одного байта, равного сумме двоичных сумм всех байтов, начиная с слова «тип сообщения» до конца блока сообщений (за исключением переданной контрольной суммы). Перенос с самого значимого бита игнорируется.

Другое описание, которое я нашел, было: Значение контрольной суммы содержит два дополнения к сумме по модулю 256 других слов в сообщении данных (то есть тип сообщения, длина сообщения и слова данных).

Приемное оборудование может рассчитывать по модулю 256 сумм полученных слов и добавлять эту сумму к полученному слову контрольной суммы. Результат нуля обычно указывает, что сообщение было правильно получено.

Я понимаю, это означает, что я суммирую значение всех байтов в сообщении (исключая контрольную сумму), получая по модулю 256 этого числа. получить двойной набор этого числа, и это моя контрольная сумма.

Но у меня возникают проблемы с примером примера примера (из конструктора doc, поэтому я должен предположить, что он был закодирован правильно).

Таким образом, последний байт, 0xE, является контрольной суммой. Мой код для расчета контрольной суммы выглядит следующим образом:

Спектр здесь: = http://www.sinet.bt.com/227v3p5.pdf

Я предполагаю, что я неправильно понял требуемый алгоритм. Любая идея создания этой контрольной суммы?

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

c++algorithmchecksum

задан Angus Comber 02 сент. '12 в 21:18

источникподелиться

Добавить комментарий

Закрыть меню