Мультипликативная группа по модулю p

1. Резюме по теории групп
2. Возведение
3. Порядок элемента
4. Циклические группы и генераторы
5. Теорема Лагранжа
6. Вернуться к $ \ mathbb {Z} _p ^ * $
7. Маленькая теорема Ферма
8. Сокращение показателей
9. Генераторы с $ p = 11 $
10. В поисках генератора
11. Большой главный фактор
12. Дискретный логарифм
13. Проблема дискретного логарифма (DLP)
14. Заметки
15. Рекомендации
16. Связаться с нами

$ \ newcommand {\ ord} {\ mathop {\ rm ord} \ nolimits} $

На этой странице рассматривается мультипликативная группа по модулю p для простого $ p $, $ \ mathbb {Z} _p ^ * $, которая используется в криптография с открытым ключом с использованием дискретных логарифмов , Мы рассмотрим некоторые свойства, относящиеся к его использованию в криптографии, и резюмируем некоторые основные теории групп. Мы предполагаем, что вы понимаете модульную арифметику и конгруэнции и некоторую базовую теорию групп (определение, аксиомы, подгруппы).

Мультипликативная группа по модулю p - это множество $ p-1 $ элементов $ \ {1,2, \ ldots, p-1 \} $ при умножении групповой операции по модулю $ p $, где $ p $ - простое число.

«мультипликативный» = мы заботимся только о умножении элементов
«по модулю р» = мы делаем наши операции умножения по модулю р
«группа» = она имеет свойства группы (см. ниже)

Обратите внимание, что в множестве нет нуля, что все элементы попарно не совпадают друг с другом по модулю $ p $, и что ни один элемент не делится или не имеет общего множителя с $ p $. Мы будем использовать эти свойства позже. Смотрите также примечание 1 ,

Группа обозначается как $ \ mathbb {Z} _p ^ * $, но вы также можете встретить $ \ mathbb {Z} _p ^ {\ times} $, $ \ mathbb {F} _p ^ * $, $ GF ( p) ^ * $, $ (\ mathbb {Z} / p \ mathbb {Z}) ^ * $ и другие подобные варианты.

Он удовлетворяет пяти аксиомам для абелевой группы.

• G1 Закрытие. Любые два элемента в множестве, умноженные вместе по модулю $ p $, дают другой элемент в множестве.
• G2 личность. Число 1 является мультипликативным тождеством и дает $ 1 \ cdot x = x = x \ cdot 1 $ для любого $ x $ в множестве.
• G3 Инверсы. Каждый элемент $ x $ в наборе имеет соответствующий обратный элемент $ x ^ {- 1} $ в наборе такой, что $ xx ^ {- 1} = 1 = x ^ {- 1} x \ pmod {p} $.
• G4 Ассоциативность. Для любых элементов $ a, b, c $ в наборе $ a (bc) = (ab) c \ pmod {p} $.
• G5 Коммутативность. Для любых двух элементов $ a, b $ в наборе $ ab = ba \ pmod {p} $.

Аксиомы G4 и G5 наследуются от мультипликативных свойств целых чисел $ \ mathbb {Z} $, как и аксиома тождества G2. Те же самые правила ассоциативности и коммутативности применяются при модульном умножении, поэтому нам не нужно беспокоиться о порядке, в котором мы пишем термины в наших выражениях, и нам не нужно использовать скобки (если мы не решим). Две аксиомы G1 и G3 требуют дополнительного пояснения.

Чтобы показать, что аксиома замыкания (G1) верна, нам нужно показать, что произведение двух элементов никогда не может быть нулевым. Предположим, что $ xy \ эквивалента 0 \ pmod {p} $ для двух элементов $ x, y $ в наборе. Это означает, что либо $ x $, либо $ y $ делится на $ p $, что неверно: противоречие.

Чтобы показать, что инверсия существует для каждого элемента (аксиома G3), мы видим, что ни один элемент не имеет общего множителя с $ p $ или не делится на него. Таким образом, для любого элемента $ x $ в наборе $ \ gcd (x, p) = 1 $. От Личность Безу это означает, что существуют целые числа $ r $ и $ s $ такие, что $ xr + ps = 1 $. Мы можем переписать это как $ xr = 1 - ps $ или $ xr \ эквивалента 1 \ pmod {p} $. Мы заключаем, что $ r $ (или $ r \ mod p $) является мультипликативным обратным к $ x $.

Резюме по теории групп

Группа $ (G, \ ast) $ - это набор $ G $ элементов (или членов) в групповой операции $ \ ast $, которые вместе удовлетворяют первым четырем групповым аксиомам G1-G4.

Исходя из этих четырех аксиом, мы можем доказать, что элемент идентичности уникален и что каждый элемент имеет уникальную обратную сторону. Элемент идентичности иногда обозначается как $ e $.

Если групповая операция коммутативна (и, следовательно, аксиома G5 выполняется), мы называем $ G $ абелевой группой, названной в честь норвежского математика Нильса Абеля. Примером группы, которая не является коммутативной, является множество матриц $ 2 \ times 2 $ при умножении матриц. Обратите внимание, что группа $ \ mathbb {Z} _p ^ * $ абелева.

Подгруппа $ H $ группы $ G $ - это подмножество элементов $ H \ subseteq G $, которое включает в себя единичный элемент и подчиняется замыканию и инвертирует аксиомы. Свойства ассоциативности и коммутативности предоставляются бесплатно.

Порядок группы - это количество элементов в множестве $ G $, обозначаемое как | | G | $.

Если множество $ G $ конечно (т. Е. $ | G | \ lt \ infty $), мы называем группу конечной группой. Группа $ \ mathbb {Z} _p ^ * $ конечна и имеет порядок $ p-1 $.

Возведение

Для элемента $ a \ in G $ мы определяем $ a ^ n $ (читаем «$ a $ в степени $ n $») как $ a ^ n = a \ ast a \ ast \ cdots \ ast a $ [$ n $ раз].

Для группы $ \ mathbb {Z} _p ^ * $ нотация $ a ^ n $ соответствует обычному значению модульного возведения в степень, где $ a ^ n $ - это элемент $ a $, умноженный на себя $ n $ раз ($ мод р $, конечно).

Из этого определения легко можно показать, что применяются обычные законы экспоненты:

$ a ^ mb ^ m = (ab) ^ m $
$ a ^ ma ^ n = a ^ {m + n} $
$ \ left (a ^ m \ right) ^ n = a ^ {mn} $

Обратите внимание, что индексы $ m $ и $ n $ являются целыми числами, а не элементами группы, поэтому вы можете добавлять и умножать их обычным способом. Например, мы можем написать $ \ left (a ^ m \ right) ^ n = a ^ {mn} = a ^ {nm} = \ left (a ^ n \ right) ^ m $. Они работают и с отрицательными значениями, если мы определим $ a ^ {- m} = \ left (a ^ {- 1} \ right) ^ m $. Для нулевого показателя $ a ^ 0 = 1 $ - единичный элемент.

Порядок элемента

Порядок элемента $ a \ in G $ определяется как наименьшее целое число $ m $ такое, что $ a ^ m = 1 $. Обозначим это как $ \ ord (a) = m $. (Обратите внимание, что это не то же самое, что порядок в группе.)

Циклические группы и генераторы

Если существует элемент $ g \ in G $ с порядком, равным $ | G | $, то мы говорим, что группа циклическая. Мы говорим, что элемент $ g $ порождает группу, а $ g $ является генератором или примитивным элементом группы.

Все циклические группы абелевы, но не все абелевы группы циклические. Все подгруппы циклической группы также являются циклическими.

Не все элементы циклической группы $ G $ порождают группу. Элемент $ a $ порядка $ m \ lt | G | $ сгенерирует подгруппу порядка $ m $, поскольку по определению $ a ^ m = 1 $ и поэтому элементы начнут повторяться после $ a ^ m $, поскольку $ a ^ {m + 1} = a ^ 1 $.

Обозначим множество элементов, порожденных элементом $ a $, через $ \ langle a \ rangle $. Поэтому, если $ \ ord (a) = m $, то $ \ langle a \ rangle = \ {a ^ 1, a ^ 2, \ ldots, a ^ m \} $.

Теорема Лагранжа

Теорема Лагранжа - одна из первых «интересных» теорем о группах.

Теорема Лагранжа. Если $ G $ - конечная группа и $ H $ - подгруппа в $ G $, то порядок в $ H $ делит порядок в $ G $.

Следствием этого, иногда определяемым как сама теорема Лагранжа, является

Если $ G $ - конечная группа порядка $ n $ и $ g \ in G $, то порядок $ g $ делит $ n $.

Другое следствие состоит в том, что группа с порядком $ | G | $, равным простому числу, всегда циклическая.

Вернуться к $ \ mathbb {Z} _p ^ * $

Интересно, что группа $ \ mathbb {Z} _p ^ * $ всегда циклическая, хотя ее порядок $ p-1 $ не является простым числом (ну, для $ p \ gt 3 $). Кит Конрад [ CONRAD ] дает шесть разных доказательств этого.

Это означает, что для некоторого $ g \ in \ mathbb {Z} _p ^ * $ мы имеем

$ \ {g ^ 1, g ^ 2, \ ldots, g ^ {p-1} \} = \ mathbb {Z} _p ^ * $

Маленькая теорема Ферма

Также обратите внимание, что для любого элемента $ a \ in \ mathbb {Z} _p ^ * $ у нас всегда есть $ a ^ {p-1} = 1 $. Это является следствием теоремы Лагранжа и фактически приводит к очень короткому доказательству маленькой теоремы Ферма, которую можно сформулировать как

Теорема (Ферма). Для любого простого $ p $ и любого целого числа $ a $, не кратного $ p $, $ a ^ {p-1} \ экв. 1 \ pmod {p} $.

Сокращение показателей

В любой циклической группе с порядком $ m $ мы можем уменьшить показатели по модулю $ m $, поэтому $ a ^ i \ cdot a ^ j = a ^ {i + j \ pmod {m}} $. Это следует из свойства $ a ^ m = 1 $.

Следовательно, в $ \ mathbb {Z} _p ^ * $ мы можем уменьшить показатели по модулю $ p-1 $, поэтому $ a ^ i \ cdot a ^ j = a ^ {i + j \ pmod {p-1}} $. Например:

Пусть $ p = 11 $ и вычислим $ a ^ i \ cdot a ^ j $ для $ a = 9 $ с $ i = 6 $ и $ j = 8 $. Долгий путь у нас есть $ a ^ 6 = 9 $ и $ a ^ 8 = 3 $, поэтому $ a ^ 6 \ cdot a ^ 8 = 9 \ times 3 = 27 \ эквивалента 5 $, или, проще говоря, $ a ^ 6 \ cdot a ^ 8 = a ^ {14 \ pmod {10}} = a ^ 4 = 5 $.

Это может ввести в заблуждение, поскольку мы умножаем по модулю $ p $, но уменьшаем показатели по модулю $ p-1 $. Это, однако, полезный прием для упрощения вычислений вручную.

Генераторы с $ p = 11 $

Рассмотрим случай, когда $ p = 11 $, поэтому группа $ \ mathbb {Z} _ {11} ^ * = \ {1,2, \ ldots, 10 \} $ с порядком $ p-1 = 10 $.

Рассмотрим элемент $ g = 2 $ и генерируемые им элементы (все вычисляются по модулю $ p $).

$ Г ^ 1 = 2; g ^ 2 = 2 \ cdot 2 = 4; g ^ 3 = 4 \ cdot 2 = 8; g ^ 4 = 8 \ cdot 2 = 16 \ эквивалент 5; g ^ 5 = 5 \ cdot 2 = 10; g ^ 6 = 10 \ cdot 2 = 20 \ эквивалент 9; g ^ 7 = 9 \ cdot 2 = 18 \ экв. 7; g ^ 8 = 7 \ cdot 2 = 14 \ экв. 3; g ^ 9 = 3 \ cdot 2 = 6; g ^ {10} = 6 \ cdot 2 = 12 \ эквивалент 1. $
То есть $ \ langle 2 \ rangle = \ {2,4,8,5,10,9,7,3,6,1 \} = \ mathbb {Z} _ {11} ^ * $ и $ \ Ord (2) = 10 $.

Но элемент $ g = 3 $ порождает только подгруппу порядка 5.

$ Г ^ 1 = 3; г ^ 2 = 9; г ^ 3 = 27 \ экв 5; г ^ 4 = 15 \ экв 4; г ^ 5 = 12 \ эквивалент 1. $
То есть $ \ langle 3 \ rangle = \ {3,9,5,4,1 \} $, поэтому $ \ ord (3) = 5 $.

А элемент $ g = 10 $ порождает только подгруппу порядка 2.

$ Г ^ 1 = 10; г ^ 2 = 100 \ эквивалент 1. $
То есть $ \ langle 10 \ rangle = \ {10,1 \} $, поэтому $ \ ord (10) = 2 $.

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

$ a $ $ \ langle a \ rangle $ $ \ ord (a) $ 1 $ \ {1 \} $ 1 2 {2,4,8,5,10,9,7,3,6,1} 10 3 {3,9,5,4,1} 5 4 {4,5,9,3,1} 5 5 {5,3,4,9,1} 5 6 {6,3,7,9,10, 5,8,4,2,1} 10 7 {7,5,2,3,10,4,6,9,8,1} 10 8 {8,9,6,4,10,3,2, 5,7,1} 10 9 {9,4,3,5,1} 5 10 {10,1} 2

Обратите внимание, что порядок любого элемента $ \ ord (a) \ in \ {1,2,5,10 \} $ делит порядок группы $ (10) $.

Фактически, для любого простого $ p $ мы имеем следующее:

• Порядок $ 1 $ всегда равен 1.
• Порядок $ p-1 $ всегда равен $ 2 $, так как $ (p-1) ^ 2 = p ^ 2 - 2p + 1 \ эквивалента 1 \ pmod {p} $.
• Существует ровно $ \ phi (p-1) $ порождающих группы, где $ \ phi (n) $ - это функция Эйлера, число натуральных чисел которых меньше $ n $, взаимно простых с $ n $.

В нашем случае при $ p = 11 $ $ \ phi (p-1) = \ phi (10) = \ phi (2) \ phi (5) = (2-1) \ cdot (5-1) = 4 $, и мы видим, что у нас действительно есть ровно 4 генератора группы, а именно $ (2,6,7,8) $.

Фактически, если $ d $ является делителем $ p-1 $, то существуют $ \ phi (d) $ генераторы порядка $ d $.

В поисках генератора

Есть два способа найти генератор для $ \ mathbb {Z} _p ^ * $, оба неосуществимы для больших простых чисел с 1000 битами, которые мы используем в криптографии.

Первый способ - выбрать подходящее целое число $ a \ in \ mathbb {Z} _p ^ * $ и показать, что $ a ^ i \ neq 1 $ для $ i = 1, \ ldots, p-2 $. Это становится большой работой для больших простых чисел $ p $.

Второй метод состоит в том, чтобы факторизовать $ p-1 $ и использовать свойство, что $ a $ является генератором тогда и только тогда, когда $ a ^ {(p-1) / q} \ not \ эквивалента 1 \ pmod {p} $ для все простые числа $ q $, которые делят $ p-1 $. Таким образом, нам нужно только проверить нашего кандидата $ a $ против всех основных факторов $ p-1 $. Но факторизация $ p-1 $ для большого $ p $ также является сложной проблемой.

Большой главный фактор

В методах криптографии, которые используют дискретные логарифмы в $ \ mathbb {Z} _p ^ * $, важно использовать генератор $ g $, который не генерирует небольшую подгруппу. В идеале мы хотели бы, чтобы $ g $ генерировал всю группу, но это трудно найти для большого $ p $. Вместо этого мы удостоверимся, что $ p-1 $ имеет большой простой множитель, $ q $, и убедимся, что $ g $ является генератором этой подгруппы.

То есть мы выбираем простое $ p $ так, чтобы $ p = jq + 1 $, где $ j $ - большое четное число, иногда называемое кофактором. Затем мы выбираем генератор $ g $, который порождает эту большую подгруппу порядка $ q $ по модулю $ p $. Мы знаем, что есть $ \ phi (q) = q-1 $ таких генераторов, поэтому их легко найти.

Чтобы найти подходящий генератор, мы выбираем случайное число $ h $ в диапазоне $ 1 \ lt h \ lt p-1 $ и вычисляем $ g = h ^ j \ pmod {p} $. Если $ g \ gt 1 $, используйте $ g $. В противном случае, если $ g = 1 $, выберите другой $ h $.

Дискретный логарифм

Дискретный логарифм целого числа $ x $ к основанию $ g $ по модулю $ p $ определяется как целое число $ n $ такое, что $ g ^ n \ pmod {p} $. То есть

$ \ log_g x \ экв. n \ pmod {p} \ quad \ Leftrightarrow \ quad x \ экв. g ^ n \ pmod {p} $

Проблема дискретного логарифма (DLP)

Задача дискретного логарифма (DLP) для $ \ mathbb {Z} _p ^ * $

Учитывая $ g, x \ in \ mathbb {Z} _p ^ * $, найдите $ n $ такой, что $ x \ эквивалент g ^ n \ pmod {p} $.

В настоящее время это неразрешимая проблема для больших $ p $ порядка $ 2 ^ {1024} $.

Аналогично, если $ p-1 $ имеет большой простой множитель $ q $ и $ g $ является генератором порядка $ q $, то трудно найти $ n \ in [2, q-2] $ при заданном $ g $ и $ g ^ n \ pmod {p} $. Для простого $ p $, равного 1024 битам, простой коэффициент $ q $ должен быть не менее 160 бит.

Заметки

1. Конгруэнтные классы и представители. Строго говоря, элементы группы являются классами конгруэнции. Класс конгруэнции по модулю $ p $ целого числа $ r $ - это множество всех целых чисел, конгруэнтных $ r $ по модулю $ p $, обычно обозначаемое как $ [r] _p $. Таким образом, $ [r] _p $ - это множество всех целых чисел вида $ r + kp $. Если мы строгие, мы должны написать

   $ \ mathbb {Z} _p ^ * = \ {[1] _p, [2] _p, \ ldots, [p-1] _p \} $.

   Любой элемент $ x $ класса конгруэнции по модулю $ p $ называется представителем класса, а класс конгруэнции может быть помечен любым элементом в классе. Например, для $ p = 5 $ мы могли бы написать, если пожелаем, $ \ mathbb {Z} _5 ^ * = \ {1, 2, 3, 4 \} $ или
   $ \ mathbb {Z} _5 ^ * = \ {6, 7, 8, 9 \} $ или
   $ \ mathbb {Z} _5 ^ * = \ {11, 17, 23, 29 \} $.
   Мы можем даже использовать числа Клингона,
   $ \ mathbb {Z} _5 ^ * = $ { , , , }

   Наиболее удобной маркировкой для $ \ mathbb {Z} _p ^ * $ является использование наименьших положительных вычетов по модулю p, $ \ {1,2, \ ldots, p-1 \} $. Что возвращает нас туда, откуда мы начали. Использование каких-либо других представителей редко дает какие-либо преимущества (кроме математиков-клингонов), поэтому вам не нужно слишком беспокоиться о классах и представителях конгруэнтности. Представление с наименьшим положительным вычетом имеет преимущество в том, что выражение «$ a = b \ bmod p $» можно использовать взаимозаменяемо с отношением конгруэнции «$ a \ экв. B \ pmod {p} $». Однако в доказательствах может быть удобно иметь возможность записать элемент группы $ r $ в виде целого числа $ r + kp $.

Рекомендации

• [CHIL09] Чайлдс, Линдсей Н. Конкретное введение в высшую алгебру , Springer Science + Business Media LLC, 2009.
• [КОНРАД] Конрад, Кит. Цикличность (Z / (p)), < cyclicFp.pdf >.
• [SMIT00] Смит, Джефф и Ольга Табачникова. Темы в теории групп Springer-Verlag, Лондон, 2000.
• [STIN02] Стинсон, Дуглас Р. Теория и практика криптографии , 2-е изд, Chapman & Hall / CRC, 2002.

Подтверждения

Спасибо Тому Верхоффу за его предложения по уменьшению показателей.

Связаться с нами

Чтобы прокомментировать эту страницу или связаться с нами, пожалуйста, отправьте нам сообщение ,

Эта страница впервые опубликована 3 сентября 2013 года. Последнее обновление 14 мая 2019 года.

Похожие

Комментарии