Модульная арифметика

Question

Я новичок в криптографии и модульной арифметике. Итак, я уверен, что это глупый вопрос, но я не могу с этим поделать.

Как рассчитать из
        мощн (, д) = 1 (по модулю р)
где р и д известны? Я не получаю «1 (mod p)», он равен 1, не так ли? Если да, то что такое «mod p« about?
Это то же самое, как
        мощн (, -q) (мод р) = 1?

Answer 1

Часть (mod p) относится не к правой стороне, а к знаку равенства: он говорит, что modulo p, pow (a, q) и 1 равны. Например, «по модулю 10, 246126 и 7868726 равны» (и они оба равны 6 по модулю 10): два числа x и y равны по модулю p, если они имеют одинаковый остаток при делении на p или, что то же самое, если p делит xy.

Поскольку вы, кажется, исходите из перспективы программирования, другой способ сказать, что это pow (a, q)% p = 1, где «%» - это оператор «остатка», реализованный на нескольких языках (предполагая, что p> 1).

Вы должны прочитать статью в Википедии по адресу Modular arithmetic или любую книгу по теории элементарных чисел (или даже книгу криптографии, поскольку она, вероятно, представит модульную арифметику).

Чтобы ответить на другой вопрос, нет общей формулы для нахождения такого a (насколько мне известно). Предполагая, что p является простым, и используя Fermat's little theorem, чтобы уменьшить q по модулю p-1 и считая, что q делит p-1 (или нет такого a), вы можете создать такой a, взяв primitive root p и поднимая его до мощности (p-1)/q. [И в более общем случае, когда p не является простым, вы можете уменьшить q по модулю φ (p), затем предположив, что он делит φ (p), и вы знаете примитивный корень (скажем r) mod p, вы можете взять r в силу φ (p)/q, где φ - the totient function - это исходит от Euler's theorem.]

Answer 2

Не глупо вообще, как Это основа шифрования с открытым ключом. Вы можете найти отличную дискуссию по этому вопросу на http://home.scarlet.be/~ping1339/congr.htm#The-equation-a%3Csup%3Ex.

ИПК работ, выбирая p и q, которые являются большими и relatively prime. Один (скажем p) становится вашим личным ключом, а другой (q) является вашим открытым ключом. Шифрование «ломается», если злоумышленник догадывается p, данный aq (зашифрованное сообщение) и q (ваш открытый ключ).

Таким образом, чтобы ответить на ваш вопрос:

aq = 1 мод p

Это означает, что aq это число, которое оставляет остаток 1 при делении на p , Мы не заботимся о целой части частного, так что мы можем написать:

aq/p = n + 1/p

для любых целого значения n ,Если мы умножим обе части уравнения на p, мы имеем:

aq = np + 1

Решение для a мы имеем:

a = (np +1) ^1/q

Последний шаг должен найти значение n, которое генерирует исходное значение a. Я не знаю, как это сделать, кроме проб и ошибок, что эквивалентно попытке «грубой силы» разбить шифрование.