Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
ах = l(modn).
риодом 6).
188
Часть II. Математические основы
Обозначим через ord^a) порядок элемента по положительному модулю п. Любой элемент a G Z* имеет порядок ordn(a), который связан с числами ordp(a) и ord9(a) соотношением
ordn(a) = lcm(ordp(a), ord9(a)). (5.2.2)
Поскольку группы Z* и Z* являются циклическими, максимальный порядок их элементов равен р — 1 и q — 1 соответственно. Следовательно, максимальный порядок элементов в группе Z* равен lcm(p — l,q — 1). С другой стороны, некий элемент a € Z*, имеющий максимальный порядок, может удовлетворять условиям ordp(a) < р — 1 и/или ordg(a) < q — 1. Например, поскольку 1ст(4,3) = 1сга(4,6), а группа Щ содержит элемент, имеющий порядок 3, максимальный порядок элементов в группе Z|5 равен 12. Этот порядок можно представить с помощью двух сцепленных шестеренок, имеющих четыре и три зубца.
В следующей главе мы введем взаимно-однозначное соответствие между элементами группы Z* и парами элементов, принадлежащих множеству Z* х Z*. Это отображение является вычислимым и позволяет сконструировать элементы группы Z*, не входящие в циклические группы Z* и Z*. Благодаря некоторым особенностям циклических групп Z* и Z* это задание оказывается довольно легким. Например, из-за того, что квадратные корни в группах Z* и Z* вычисляются просто, это отображение можно применять для создания квадратных корней в группе Z*.
5.3 Кольца и поля
В один прекрасный день наш древний пастух перестал кочевать и стал земледельцем. Теперь ему понадобилось размежевать свои и соседские участки земли. И тут бывший пастух понял, что одной операцией он не обойдется: придется выполнять не только сложение, но и умножение. С этого момента появилась необходимость выполнять две операции над множеством объектов.
Определение 5.12 (Кольцо). Кольцом R называется множество с двумя операциями: (сложение) + и (умножение) -, обладающими следующими свойствами.
1. Относительно операции сложения + кольцо R является абелевой группой. Нейтральный элемент относительно сложения (нуль) обозначается символом О.
2. Относительно операции умножения - кольцо R удовлетворяет аксиомам замкнутости, ассоциативности и аксиоме тождества. Нейтральный элемент относительно умножения (единица) обозначается символом 1, причем 1^0.
Глава 5. Алгебраические основы
189
3. \/а, b€. R: а ¦ b = b ¦ а
4. Va,b,c€R: a-(b + c) = a- b + a- c
(аксиома коммутативности). (аксиома дистрибутивности).
Следует иметь в виду, что нуль и единица — абстрактные элементы, и не обязательно являются числами (см. пример 5.11.3).
Кольца, описанные в определении 5.12, называются коммутативными (сош-"mutative ring). Именно такие кольца рассматриваются в книге. Следует иметь виду, что операции + и • являются абстрактными: они не обязательно означают сложение и умножение целых чисел. Если это не вызывает недоразумений, операцию а - b мы будем записывать как ab. Обозначение - используется только в тех ситуациях, когда операнды не указаны.
Пример 5.11 (Кольца).
1. Множества Z, Q, М и С являются кольцами относительно обычных операций сложения и умножения, причем О = 0 и 1 = 1.
2. Для любых п > О группа Ъп является кольцом относительно сложения и умножения по модулю п, причем О = 0 и 1 = 1.
3. Пусть В — аддитивная группа, определенная в примере 5.1.6 с нулевым элементом F. Введем операцию умножения Л (логическая операция "И"): F AF = F, FAT = TAF = F,TAT = T. Тогда группа В становится кольцом с единицей Т. ?
На первый взгляд определение 5.12 вводит умножение только для ненулевых элементов. Однако правило умножения нулевого элемента на ненулевой элемент следует из аксиомы дистрибутивности. Например, Оа = (b + (—Ь))а = Ъа + + (—b)a = Ьа — Ьа = О. Более того, кольцо может содержать нулевой делитель (zero-divisor), т.е. могут существовать элементы а и Ъ, удовлетворяющие условию аЪ = ОсафОнЪфО. Например, для нетривиальной факторизации числа п = = Ш числа к и ?. являются ненулевыми элементами кольца Ъп, а произведение к? = п = 0(mod ri) — нулем.
Определение 5.13 (Поле). Если ненулевые элементы кольца образуют группу относительно умножения, то кольцо называется полем.
Из аксиомы замкнутости для мультипликативной группы (т.е. ненулевых элементов) следует, что поле F не может содержать нулевой делитель, т.е. для любых a, b G F из условия ab = О следует, что либо а = О, либо b = О.
Пример 5.12 (Поля).
1. Множества Q, М и С являются полями относительно обычных операций сложения и умножения, причем О = 0 и 1 = 1.
2. Кольцо В, определенное в примере 5.11.3, является полем.
3. Для простого числа р группа Zp является полем относительно сложения и умножения по модулю р, причем О = 0 и 1 = 1. ?
В свое время мы рассмотрим и другие примеры полей.
Следует отметить, что группа Z относительно целочисленного сложения и умножения не является полем, поскольку в группе Z не для каждого ненулевого элемента существует обратный элемент относительно умножения (нарушается акси-1 ома инверсии). Кроме того, если число п является составным, то группа Zn также' не является полем, поскольку, как показано выше, группа Zn может содержать нулевые делители (нарушается аксиома замкнутости).
