Мы ограничим наше обсуждение только квадратичными уравнениями, в которых a2 = 1 и a1 = 0. Тогда рассмотрение будет касаться уравнений следующей формы:
Мы сначала рассматриваем случай, в котором модуль является простым числом. Другими словами, мы хотим найти решения уравнения формы $${x^2} \equiv ({\text{mod }}p)$$, в котором p является простым числом и a — целое число, такое, что p и a — взаимно простые. Может быть доказано, что этот тип уравнения либо не имеет никакого решения, либо имеет только два неконгруэнтных решения.
Пример 13.1
Уравнение $${x^2} \equiv 3{\text{ }}({\text{mod }}11)$$ имеет два решения: $$x \equiv 5{\text{ }}({\text{mod 11}})$$ и $$x \equiv -5{\text{ }}({\text{mod 11}})$$. Но заметим, что $$-5 \equiv 6{\text{ }}({\text{mod 11}})$$, так что фактически эти два решения 5 и 6. Также обратите внимание, что эти два решения неконгруэнтны (несравнимы).
Пример 13.2
Уравнение $${x^2} \equiv 2{\text{ }}({\text{mod }}11)$$ не имеет решения. Не может быть найдено ни одного целого числа x, такого, что квадрат равен 2 mod 11.
В уравнении $${x^2} \equiv a{\text{ }}({\text{mod }}p)$$. a называется квадратичным вычетом (QR), если уравнение имеет два решения; a называется квадратичным невычетом (QNR), если уравнение не имеет решений. Может быть доказано, что в ZP* с p – 1 элементами (p – 1)/2 элементов — квадратичные вычеты и (p – 1)/2 являются квадратичными невычетами.
Пример 13.3
Есть 10 элементов в Z11*. Пять из них – квадратичные вычеты, и пять — невычеты. Другими словами, Z11* может быть разделен на два отдельных множества, QR и QNR, как это показано на рис. 13.1.
Как мы можем проверить, является ли целое число QR по модулю p? Критерий Эйлера дает признаки:
a. Если $${a^{(p - 1)/2}} \equiv 1(\bmod p)$$ — квадратичный вычет по модулю p.
b. Если $${a^{(p - 1)/2}} \equiv -1(\bmod p)$$ — квадратичный невычет по модулю p.
(рис 13.1) Разделение Z11* на QR и QNR Пример 13.4
Для того чтобы узнать, является ли 14 или 16 QR в Z11*, сделаем следующие вычисления:
14(23-1)/2 mod 23 1411 mod 23 -> 22 mod 23 -> –1 mod 23 невычет 16(23-1)/2 mod 23 1611 mod 23 -> 1 mod 23 вычет
Хотя критерий Эйлера позволяет нам определить, является ли целое число a QR или QNR в Zp*, он не может найти решение $${x^2} \equiv ({\text{mod }}p)$$. Чтобы найти решение этого квадратного уравнения, мы заметим, что простое число может быть представлено либо как p = 4k + 1, либо как p = 4 к + 3, в котором k является положительным целым числом. Решение квадратного уравнения — очень сложное в первом случае и более простое во втором. Мы обсудим только второй случай, который мы будем использовать в лекциях 14-15, когда будем рассматривать криптографическую систему Рабина.
Специальный случай: p = 4 К + 3, если p находится в форме 4 К + 3 (то есть p = 3 mod 4 ) и a есть QR в Zp*, то
Пример 13.5
Решите следующие квадратные уравнения:
a. $${x^2} \equiv 3{\text{ }}({\text{mod }}23)$$
b. $${x^2} \equiv 2{\text{ }}({\text{mod }}11)$$
c. $${x^2} \equiv 7{\text{ }}({\text{mod }}19)$$
Решения
a. В первом уравнении 3 - QR в Z23, решение - $$x \equiv \pm 16\left( {\bmod {\text{ }}23} \right)$$. Другими словами, $$\sqrt 3 \equiv \pm 16(\bmod 23)$$.
b.Во втором уравнении 2 - QNR в Z11. Нет решения для $$\sqrt 2 $$ в Z11.
c. В третьем уравнении 7 - QR в Z19, решение - $$x \equiv \pm 11\left( {\bmod {\text{ 19}}} \right)$$. Другими словами $$\sqrt 7 \equiv \pm 11\left( {\bmod {\text{ 19}}} \right)$$.
Квадратичное сравнение по составному модулю может быть приведено к решению системы сравнений по модулю в виде простого числа. Другими словами, мы можем анализировать $${x^2} \equiv a(\bmod n)$$, если имеем разложение n на множители. Теперь мы можем решить каждое анализируемое уравнение (если оно k пар ответов для x, как показано на рис. 13.2.
(рис 13.2) Декомпозиция сравнения по составному модулю Из k пар ответов мы можем составить 2 системы уравнений, которые могут быть решены с использованием китайской теоремы об остатках, чтобы найти 2 значения для x. В криптографии обычно n выбирают так, чтобы $$n = p \times q$$, — это означает k = 2, и мы имеем в целом только четыре ответа.
Пример 13.6
Предположим, что $${x^2} \equiv 36\left( {\bmod 77} \right)$$. Мы знаем, что $$77 = 7 \times 11$$. Мы можем написать
$$x^{2} = 36 (mod \ 7) \equiv 1 (mod \ 7) и x^{2} \equiv 36 (mod \ 11)$$Обратите внимание, что мы выбрали 3 и 7, чтобы иметь форму 4k + 3 — так, чтобы мы могли решить уравнения, основываясь на предыдущих рассуждениях. Из этих уравнений мы имеем квадратичные вычеты в собственном множестве. Ответы $$x \equiv +1\left( {\bmod {\text{ }}7} \right)$$, $$x \equiv -1\left( {\bmod {\text{ }}7} \right)$$, $$x \equiv +5\left( {\bmod {\text{ }}11} \right)$$ и $$x \equiv -5\left( {\bmod {\text{ }}11} \right)$$. Теперь мы можем из них составить четыре системы уравнений:
Ответы : $$x = \pm 6$$ и $$\pm 27$$.
Как сложно решить квадратичное сравнение по составному модулю? Главная задача — это
разложение модуля на множители. Другими словами, сложность решения квадратичного сравнения по составному модулю — такая же, как и разложения на множители составного целого числа. Как мы видели раньше, если n очень большое, то разложение на множители неосуществимо.
Возведение в степень и логарифм инверсны друг другу. Следующие разделы показывают отношения между ними, в которых a называется основой возведения в степень или логарифма.
Возведение в степень: y = ax -> логарифм: x = logay
В криптографии общая модульная операция — возведение в степень. Мы часто должны вычислять
y = ax mod n
Быстрое возведение в степень возможно при использовании специальных методов возведения в квадрат и умножения. В традиционных алгоритмах, чтобы возводить в степень, применяется только умножение, но быстрый алгоритм возведения в степень использует и возведение в квадрат, и умножение. Главная идея этого метода — выполнение возведения в степень с помощью обработки двоичного числа с nb битами ( $${x_0}$$ до $${x_{{n_b}}}_{ - 1}$$ ). Например, x = 22 = (10110) 2. Вообще, число x может быть записано как
Теперь мы можем написать y = ax, как это показано на рис. 13.3.
(рис 13.3) Идея метода "возведения в квадрат и умножения"Обратите внимание, что y — произведение элементов числа n. Каждый элемент — либо 1 (если соответствующий бит — 0 ), либо a2i (если соответствующий бит — 1 ). Другими словами, элемент a2i участвует в умножении, если бит — 1, или не участвует, если бит — 0 (умножение на 1 не меняет числа). Рисунок 13.3 дает общую идею, как написать алгоритм. Мы можем непрерывно взводить в квадрат $$a,{a^2},{a^4} \ldots {a^{{2^{{n_b}}} - 1}}$$ Если соответствующий бит — 0, элемент не участвует в процессе умножения; если бит — 1, то участвует. Алгоритм 13.1 отражает эти два свойства.
Возведение_в_ квадрат_и_умножение (a,x,n)
{
y <- 1
for (i <- 0 to nb - 1) //nb — число бит в x
{
if (xi = 1) y <- a x y mod n //умножение, только если бит 1
a <- a2 mod n
} //в последней итерации возведение в степень не нужно
return y
}
Алгоритм 13.1 использует nb итерации. В каждой итерации он проверяет значение соответствующего бита. Если значение бита равно 1, он умножает текущее значение на предыдущее значение результата. Затем полученный результат является базой для следующей итерации. Обратите внимание, что возведение в квадрат в последнем шаге не нужно (результат не используется).
Пример 13.7
Рисунок 13.4 показывает процесс для подсчета y = ax с использованием алгоритма 13.1 (для простоты изображения модули не показаны). В этом случае x = 22 = (10110) 2. Это число имеет 5 бит.
(рис 13.4) Демонстрация вычисления a22 с использованием метода "возведения в квадрат и умножения"Возведение в квадрат делается на каждом шаге за исключением последнего. Умножение делается, если соответствующий бит равен 1. На рисунке 13.4 показано, как постепенно формируется значение y до значения y = a22. Затемненный прямоугольник означает, что умножение не делается и предыдущее значение переносится на следующий шаг. Таблица 13.1 показывает, как вычисляется значение для y = 1722 mod 21. Результат — y = 4.
| i | xi | Умножение (Инициализация y = 1) | Возведение в степень (Инициализация a = 17) |
|---|---|---|---|
| 0 | 0 | a = 172 mod 21 =16 | |
| 1 | 1 | y = 1 x 16 mod 21 =16 $$\to$$ | a = 162 mod 21 = 4 |
| 2 | 1 | y = 16 x 4 mod 21 =1 $$\to$$ | a = 42 mod 21 =16 |
| 3 | 0 | a = 162 mod 21 = 4 | |
| 4 | 1 | y = 1 x 4 mod 21 = 4 $$\to$$ |
Сложность. Алгоритм 13.1 использует максимально 2nb арифметических операций, в которых nb является длиной модуля в битах (nb = log2n). Сложность в O(nb) или полиномиальная сложность.
Альтернативный алгоритм. Заметим, что алгоритм 13.1 проверяет значение битов в x справа налево (от самого младшего до самого старшего). Может быть написан другой алгоритм, чтобы использовать обратный порядок. Мы выбрали вышеупомянутый алгоритм, потому что операция возведения в квадрат полностью независима от операции умножения; они могут быть сделаны параллельно, чтобы увеличить скорость обработки. Альтернативные алгоритмы оставляем как упражнение.
Мы также должны обсудить модульный логарифм, который используется в криптографии. Если мы применяем возведение в степень для того, чтобы зашифровать или расшифровывать сообщение, противник может использовать логарифм для раскрытия этого сообщения Мы должны знать, трудно ли получить операцию, противоположную возведению в степень.
Первое решение, которое могло бы прийти на ум, для решения x = loga y (mod n): мы можем написать алгоритм, который непрерывно вычисляет y = ax mod n, пока не находит заданное значение y. Алгоритм 13.2 показывает этот подход.
$$\tt\parindent0pt
Modular\_Logarithm (a, y, n\}
\{
\ \ for (x = 1 to n — 1) // k число бит в x
\ \ \{
\ \ \ \ if ($y \equiv a^{x} \mod\ n$) return x
\ \ \}
\ \ return failure
\} $$
Алгоритм 13.2 явно очень неэффективен. Сложность разрядной операции — 0 (2n) или показательна.
Второй подход состоит в том, чтобы использовать понятие дискретного логарифма. Рассмотрение этого понятия требует изучения некоторых свойств мультипликативных групп.
Конечная мультипликативная группа. В криптографии мы часто используем мультипликативную конечную группу: $$G = \<{Z_{n*}}, \times \>$$, в которой применяемая операция является умножением. Множество Zn* содержит целые числа от 1 до n–1, которые являются взаимно простыми с n, нейтральный элемент — e = 1. Обратите внимание, что когда модуль группы — простое число, мы имеем $$G = \<{Z_{p*}}, \times \>$$. Эта группа — специальный случай группы первого типа, так что мы концентрируемся на этой группе.
Порядок группы. В лекцииях 5-6 мы обсуждали порядок конечной группы |G| для того, чтобы определить число элементов в группе G. Было доказано, что в группе $$G = \<{Z_{n*}}, \times \>$$ порядок группы (число элементов) — n может быть разложено на множители в виде простых чисел.
Пример 13.8
Найти порядок группы $$G = \<{Z_{21*}}, \times \>,$$ $$|G| = \varphi (21) = \varphi (3) \times \varphi (7) = 2 \times 6 = 12$$. В этой группе 12 элементов: 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19 и 20. Все — взаимно простые с 21.
Порядок элемента. В лекциях 5-6 мы также обсуждали порядок элемента — ord (a).
В $$G = \<{Z_{n*}}, \times \>,$$ мы продолжаем определение. Порядок элемента a есть наименьшее целое число, такое, что $${a^i} \equiv e(\bmod n)$$. В этом случае нейтральный элемент e равен 1.
Пример 13.9
Найдите порядок всех элементов в $$G = \<{Z_{10*}}, \times \>$$.
Решение
Эта группа имеет только $$\varphi (10) = 4$$ элемента: 1, 3, 7, 9. Мы можем найти порядок каждого элемента методом "проб и ошибок". Однако, согласно результатам лекций 5-6, порядок элемента является делителем порядка группы (теорема Лагранжа). Целые числа, которые делят 4, — 1, 2 и 4. Это означает, что в каждом случае мы должны проверить только эти числа и найти порядок элемента,
a. $${1^1} = 1\bmod \left( {10} \right) \to ord\left( {10} \right) = 1$$.
b. $${3^1} = 3\bmod \left( {10} \right);{3^2} \equiv 9\bmod \left( {10} \right);{3^4} \equiv 1\bmod \left( {10} \right) \to ord\left( 3 \right) = 4$$.
c. $${7^1} = 7\bmod \left( {10} \right);{7^2} \equiv 9\bmod \left( {10} \right);{7^4} \equiv 1\bmod \left( {10} \right) \to ord\left( 7 \right) = 4$$
d. $${9^1} = 9\bmod \left( {10} \right);{9^2} \equiv 1\bmod \left( {10} \right) \to ord\left( 9 \right) = 2$$.
Теорема Эйлера. Другая теорема, относящаяся к этому вопросу, — это a является членом $$G = \<{Z_{n^*}}, \times \>$$,
то $${a^{\varphi (n)}} = 1\bmod n$$ ;
Эта теорема очень полезна, потому что показывает, что равенство Ai = 1 mod n сохраняется, если $$i = \varphi (n)$$. Заметим: это не отрицает, что равенство может выполняться и если $$i < \varphi (n)$$. Другими словами, это отношение показывает, что равенство выполняется по меньшей мере однажды.
Пример 13.10
Таблица 13.2 показывает результат ai = x (mod 8) для группы $$G = \<{Z_{8^*}}, \times \>$$. Обратите внимание, что $$\varphi (8) = 4$$. Это элементы — 1, 3, 5 и 7.
| i=1 | i=2 | i=3 | i=4 | i=5 | i=6 | i=7 | |
| a=1 | x:1 | x:1 | x:1 | x:1 | x:1 | x:1 | x:1 |
|---|---|---|---|---|---|---|---|
| a=3 | x:3 | x:1 | x:3 | x:1 | x:3 | x:1 | x:3 |
| a=5 | x:5 | x:1 | x:5 | x:1 | x:5 | x:1 | x:5 |
| a=7 | x:7 | x:1 | x:7 | x:1 | x:7 | x:1 | x:7 |
Таблица 13.2 показывает некоторые моменты вычислений. Первый: затемненная область показывает результат применения x = 1 для каждого a. Второй момент: когда таблица показывает, что значение 1 может быть получено для многих значений i — в первую очередь, значение i, равное порядку элемента (обведено в таблице жирной линией). Порядок элементов: ord (1) = 1, ord (3) = 2, ord (5) = 2 и ord (7) = 2.
Первообразные корни. Очень интересное понятие в мультипликативной группе — группы первообразного корня, которые используются в
Пример 13.11
Таблица 13.2 показывает, что там нет первообразных корней $$G = \<{Z_{8^*}}, \times \>$$, потому что ни один элемент не имеет порядок, равный $$\varphi (8) = 4$$. Порядок всех элементов — меньше, чем 4.
Пример 13.12
Таблица 13.3 показывает результат $${a^i} \equiv x\left( {\bmod {\text{ }}7} \right)$$ для группы $$G = \<{Z_{7^*}}, \times \>$$. В этой группе $$\varphi (7) = 6$$.
| i=1 | i=2 | i=3 | i=4 | i=5 | i=6 | |
| a=1 | x:1 | x:1 | x:1 | x:1 | x:1 | x:1 |
|---|---|---|---|---|---|---|
| a=2 | x:2 | x:4 | x:1 | x:2 | x:4 | x:1 |
| a=3 | x:3 | x:2 | x:6 | x:4 | x:5 | x:1 |
| a=4 | x:4 | x:2 | x:1 | x:4 | x:2 | x:1 |
| a=5 | x:5 | x:4 | x:6 | x:2 | x:3 | x:1 |
| a=6 | x:6 | x:1 | x:6 | x:1 | x:6 | x:1 |
Порядок элементов – $$ord\left( 1 \right) = 1$$, $$ord\left( 2 \right) = 3$$, $$ord\left( 3 \right) = \underline 6 $$, $$ord\left( 4 \right) = 3$$, $$ord\left( 5 \right) = \underline 6 $$ и $$ord\left( 6 \right) = 1$$.
Таблица 13.3 показывает, что только два элемента, 3 и 5, имеют порядок в $$i = \varphi (n) = 6$$. Поэтому эта группа имеет только два примитивных корня: 3 и 5.
Было доказано, что группа $$G = \<{Z_{n^*}}, \times \>$$ имеет примитивный корень, только если n = 2, 4, pt, или 2pt, в которой p является нечетным простым числом (не 2 ) и t — целое число.
Пример 13.13
Для какого значения n группа $$G = \<{Z_{n^*}}, \times \>$$ имеет примитивные корни: 17, 20, 38 и 50?
Решение
a. $$G = \<{Z_{17^*}}, \times \>$$ имеет примитивные корни, потому что 17 — простое число ( pt, где t равно 1 ).
b. $$G = \<{Z_{20^*}}, \times \>$$ не имеет никаких примитивных корней.
c. $$G = \<{Z_{38^*}}, \times \>$$ имеет 19 — простое число.
d. $$G = \<{Z_{50^*}}, \times \>$$ имеет 5 — простое число.
Если группа имеет примитивный корень, то обычно она имеет несколько таких корней. Число примитивных корней может быть вычислено как — $$\varphi (\varphi (n))$$. Например, число примитивных корней $$G = \<{Z_{17^*}}, \times \>$$ — это — $$\varphi (\varphi (n)) = \varphi (16) = 8$$. Обращаем внимание, что нужно сначала проверить, имеет ли группа какой-либо примитивный корень, прежде чем находить число корней.
Рассмотрим три вопроса:
1. Если дан элемент a и группа $$G = \<{Z_{n^*}}, \times \>$$, как можно определить, является ли a примитивным корнем G? Это не такая легкая задача.
а. Мы должны найти $$\varphi (n)$$, — эта задача по сложности подобна задаче разложения на множители числа n.
б. Мы должны найти $$ord(a) = \varphi (n)$$.
2. Если дана группа $$G = \<{Z_{n^*}}, \times \>$$, как найти все примитивные корни $$\varphi $$? Эта задача более трудная, чем первая задача, потому что мы должны повторить вычисления по п.1.б для всей группы.
3. Если дана группа $$G = \<{Z_{n^*}}, \times \>$$, то как выбирать примитивный корень G? В криптографии мы должны найти, по крайней мере, один примитивный корень в группе. Однако в этом случае значение n выбирается пользователем, и пользователь знает $$\varphi (n)$$. Пользователь пробует последовательно несколько элементов, пока не находит первый из них.
Циклическая группа. Циклические группы уже обсуждались в лекциях 5-6. Обратите внимание на то, что, если группа $$G = \<{Z_{n^*}}, \times \>$$ имеет примитивные корни, то они циклически повторяются. Каждый примитивный корень — генератор и может использоваться для создания целого набора. Другими словами, если g — примитивный корень в группе, мы можем генерировать набор Zn* как
Пример 13.14
Группа $$G = \<{Z_{10^*}}, \times \>$$ имеет два примитивных корня, потому что $$\varphi (10) = 4$$ и $$\varphi (\varphi (10)) = 2$$. Можно найти примитивные корни - это 3 и 7. Ниже показано, как можно создать целый набор Z10*, использующий каждый примитивный корень.
g = 3 -> g1 mod 10 = 3 g2 mod 10 = 9 g3 mod 10 = 7 g4 mod 10 = 1 g = 7 -> g1 mod 10 = 7 g2 mod 10 = 9 g3 mod 10 = 3 g4 mod 10 = 1
Обратите внимание, что группа $$G = \<{Z_{p^*}}, \times \>$$ всегда циклическая, потому что p — простое.
Группа G = < Zn*, x > является циклической группой, если она имеет примитивные корни. Группа G = < Zp*, x > всегда является циклической.
Идея дискретного логарифма. Группа $$G = \<{Z_p}^*, \times \>$$ имеет несколько интересных свойств.
1 до p – 1.gx, где x — целое число от 1 до $$\varphi (n) = p - 1$$.k примитивных корней, то вычисления могут быть сделаны для k различных оснований. Данный x = logg y для любого элемента y в данном множестве, но есть другой элемент x, который является логарифмом y по основанию g. Этот тип логарифма называют дискретным логарифмом. Lg, чтобы показать, что основание — g (сравнение по модулю).Теперь рассмотрим, как решаются задачи типа y = ax (mod n), т. е. дано y, а мы должны найти x.
Табулирование дискретных логарифмов. Один из способов решения вышеупомянутой проблемы — использовать таблицу для каждого Zp* и различных оснований. Этот тип таблицы может быть предварительно рассчитан и сохранен. Например, таблица 13.4 показывает значения Z7*. Мы знаем, что мы имеем два примитивных корня или основания в данном множестве.
| y | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| x = L3y | 6 | 2 | 1 | 4 | 5 | 3 |
| x = L5y | 6 | 4 | 5 | 2 | 1 | 3 |
Составив таблицы для других 10.
Пример 13.15
Найдите x в каждом из следующих случаев:
a. $$4 \equiv {3^x}\left( {\bmod {\text{ }}7} \right)$$
b. $$6 \equiv {5^x}\left( {\bmod {\text{ }}7} \right)$$
Решение
Мы можем легко использовать таблицу 13.4
a. $$4 \equiv {3^x}\left( {\bmod {\text{ }}7} \right) \to {L_3}4\left( {\bmod {\text{ }}7} \right) = 4{\text{ }}\bmod {\text{ }}7$$
b. $$6 \equiv {5^x}\left( {\bmod {\text{ }}7} \right) \to {L_5}6\left( {\bmod {\text{ }}7} \right) = 3{\text{ }}\bmod {\text{ }}7$$
Использование свойств дискретных логарифмов. Чтобы показать, что n.
| Традиционные логарифмы | |
|---|---|
| loga 1 = 0 | Lg $$\equiv$$ 0(mod $$\phi$$ (n)) |
| loga (x x y) = logax + logay | Lg(x x y) $$\equiv$$ Lgx + Lgy |
| logaxk = k x logax | Lgx $$\equiv$$ k x Lgx(mod $$\phi$$ (n)) |
Использование алгоритмов, основанных на дискретных логарифмах. Таблицы и свойства y = a x (mod n), когда n является очень большим. Для решения этой проблемы были разработаны несколько алгоритмов, в которых используется основная идея
Нижеследующие книги и сайты дают более детальную информацию о предметах, рассмотренных в этой лекции. Пункты, приведенные в квадратных скобках, содержатся в списке в конце книги.
[Ros06] [Cou99], [BW00] и [Bla03] — для тем, которые обсуждаются в этой лекции.
Нижеследующие сайты дают больше информации о темах, обсужденных в этой лекции.
1, простые числа и 1 и непосредственно само на себя. Составной объект — положительное целое число по крайней мере с двумя делителями.phi -функция $$\varphi (n)$$, которую иногда называют функцией-тотиентом Эйлера, играет очень важную роль в криптографии. Функция указывает число целых чисел, которые меньше чем n и являются взаимно простыми с n.| Ферма | Первая версия : Если НОД(a,p) = 1, то ap-1 $$\equiv$$ 1(mod p) |
| Вторая версия: ap $$\equiv$$ a(mod p) | |
| Эйлер | Первая версия: Если НОД(a,n) = 1, то a $$\phi$$ (n) $$\equiv$$ 1 (mod p) |
| Вторая версия: Если n= p x q и a < n, то a>kx $$\phi$$ (n)+1 $$\equiv$$ a(mod n) |
1, может быть разложено на множители в виде простых чисел. Мы рассмотрели несколько методов разложения на множители, включая проверку делением — Ферма, метод Полларда p – 1, метод РО ( $$\rho $$ ) Полларда, квадратичное решето и решето поля чисел.100 000 и 200 000.100 000 и 200 0001 – 10.100, 1000, 10 000, 100 000 и 1 000 000. Также найти наибольший простой сомножитель 101, 1001, 10 001, 100 001 и 1 000 01.4k + 1, либо 4k + 3, где k — положительное целое число.5k + 1, 5k + 2, 5 k + 3 и 5k + 4, где k: является положительным целым числом.224 – 1 и 216 – 1 – составные числа. Подсказка: используйте выражение (a2 – b2).2, может быть представлено как сумма двух простых чисел. Проверьте это предположение для 10, 24, 28 и 100.n2 + 1. Найдите некоторые из них.515 mod 131518 mod 1745617 mod 17145 mod 1015-1 mod 1315-1 mod 1727-l mod 4170-1 mod 101Обратите внимание, что все модули — простые числа.
12-1 mod 7716-1 mod 32320-1 mod 40344-1 mod 667Обратите внимание, что $$77 = 7 \times 11$$, $$323 = 17 \times 19$$, $$403 = 31 \times 13$$ и $$667 = 23 \times 29$$.
М23, М29 и М31. Подсказка: любой делитель 2kp + 1.2n – 1 — простое число, то n — простое число. Этот факт может использоваться для проверки на простоту? Объясните, как.100, 110, 130, 150, 200, 250, 271, 341, 561. Используйте основание 2.100, 109, 201, 271, 341, 349. Используйте основание 2.271, 3149, 9673.a = 2, x = 3 и несколько простых чисел, чтобы показать, что если p — простое число, то выполняется следующее сравнение: (x – a) p = (xp – a) (mod p).n -ное простое число может быть приближенно вычислено как pn = n ln n. Проверьте это на нескольких простых числах.x для следующих наборов сравнений, используя китайскую теорему об остатках.Z13*, Z17* и Z23*.2124 mod 832023 mod 461173641 mod 2134200135 mod 20001 миллион бит в секунду. Вы хотите затратить только 1 час на испытание простоты чисел. Какое наибольшее число вы можете проверить, используя следующие методы, проверяющие простоту чисел?1 миллион бит в секунду. Вы хотите потратить только 1 час на разложение составного целого числа. Какое наибольшее число вы можете разложить на множители, используя следующие методы разложения на множители?1. Измените алгоритм 13.1, чтобы показать это.Zp*.Zp*.Zp*.Zp*.Мы ограничим наше обсуждение только квадратичными уравнениями, в которых a2 = 1 и a1 = 0. Тогда рассмотрение будет касаться уравнений следующей формы:
Мы сначала рассматриваем случай, в котором модуль является простым числом. Другими словами, мы хотим найти решения уравнения формы $${x^2} \equiv ({\text{mod }}p)$$, в котором p является простым числом и a — целое число, такое, что p и a — взаимно простые. Может быть доказано, что этот тип уравнения либо не имеет никакого решения, либо имеет только два неконгруэнтных решения.
Пример 13.1
Уравнение $${x^2} \equiv 3{\text{ }}({\text{mod }}11)$$ имеет два решения: $$x \equiv 5{\text{ }}({\text{mod 11}})$$ и $$x \equiv -5{\text{ }}({\text{mod 11}})$$. Но заметим, что $$-5 \equiv 6{\text{ }}({\text{mod 11}})$$, так что фактически эти два решения 5 и 6. Также обратите внимание, что эти два решения неконгруэнтны (несравнимы).
Пример 13.2
Уравнение $${x^2} \equiv 2{\text{ }}({\text{mod }}11)$$ не имеет решения. Не может быть найдено ни одного целого числа x, такого, что квадрат равен 2 mod 11.
В уравнении $${x^2} \equiv a{\text{ }}({\text{mod }}p)$$. a называется квадратичным вычетом (QR), если уравнение имеет два решения; a называется квадратичным невычетом (QNR), если уравнение не имеет решений. Может быть доказано, что в ZP* с p – 1 элементами (p – 1)/2 элементов — квадратичные вычеты и (p – 1)/2 являются квадратичными невычетами.
Пример 13.3
Есть 10 элементов в Z11*. Пять из них – квадратичные вычеты, и пять — невычеты. Другими словами, Z11* может быть разделен на два отдельных множества, QR и QNR, как это показано на рис. 13.1.
Как мы можем проверить, является ли целое число QR по модулю p? Критерий Эйлера дает признаки:
a. Если $${a^{(p - 1)/2}} \equiv 1(\bmod p)$$ — квадратичный вычет по модулю p.
b. Если $${a^{(p - 1)/2}} \equiv -1(\bmod p)$$ — квадратичный невычет по модулю p.
(рис 13.1) Разделение Z11* на QR и QNR Пример 13.4
Для того чтобы узнать, является ли 14 или 16 QR в Z11*, сделаем следующие вычисления:
14(23-1)/2 mod 23 1411 mod 23 -> 22 mod 23 -> –1 mod 23 невычет 16(23-1)/2 mod 23 1611 mod 23 -> 1 mod 23 вычет
Хотя критерий Эйлера позволяет нам определить, является ли целое число a QR или QNR в Zp*, он не может найти решение $${x^2} \equiv ({\text{mod }}p)$$. Чтобы найти решение этого квадратного уравнения, мы заметим, что простое число может быть представлено либо как p = 4k + 1, либо как p = 4 к + 3, в котором k является положительным целым числом. Решение квадратного уравнения — очень сложное в первом случае и более простое во втором. Мы обсудим только второй случай, который мы будем использовать в лекциях 14-15, когда будем рассматривать криптографическую систему Рабина.
Специальный случай: p = 4 К + 3, если p находится в форме 4 К + 3 (то есть p = 3 mod 4 ) и a есть QR в Zp*, то
Пример 13.5
Решите следующие квадратные уравнения:
a. $${x^2} \equiv 3{\text{ }}({\text{mod }}23)$$
b. $${x^2} \equiv 2{\text{ }}({\text{mod }}11)$$
c. $${x^2} \equiv 7{\text{ }}({\text{mod }}19)$$
Решения
a. В первом уравнении 3 - QR в Z23, решение - $$x \equiv \pm 16\left( {\bmod {\text{ }}23} \right)$$. Другими словами, $$\sqrt 3 \equiv \pm 16(\bmod 23)$$.
b.Во втором уравнении 2 - QNR в Z11. Нет решения для $$\sqrt 2 $$ в Z11.
c. В третьем уравнении 7 - QR в Z19, решение - $$x \equiv \pm 11\left( {\bmod {\text{ 19}}} \right)$$. Другими словами $$\sqrt 7 \equiv \pm 11\left( {\bmod {\text{ 19}}} \right)$$.
Квадратичное сравнение по составному модулю может быть приведено к решению системы сравнений по модулю в виде простого числа. Другими словами, мы можем анализировать $${x^2} \equiv a(\bmod n)$$, если имеем разложение n на множители. Теперь мы можем решить каждое анализируемое уравнение (если оно k пар ответов для x, как показано на рис. 13.2.
(рис 13.2) Декомпозиция сравнения по составному модулю Из k пар ответов мы можем составить 2 системы уравнений, которые могут быть решены с использованием китайской теоремы об остатках, чтобы найти 2 значения для x. В криптографии обычно n выбирают так, чтобы $$n = p \times q$$, — это означает k = 2, и мы имеем в целом только четыре ответа.
Пример 13.6
Предположим, что $${x^2} \equiv 36\left( {\bmod 77} \right)$$. Мы знаем, что $$77 = 7 \times 11$$. Мы можем написать
$$x^{2} = 36 (mod \ 7) \equiv 1 (mod \ 7) и x^{2} \equiv 36 (mod \ 11)$$Обратите внимание, что мы выбрали 3 и 7, чтобы иметь форму 4k + 3 — так, чтобы мы могли решить уравнения, основываясь на предыдущих рассуждениях. Из этих уравнений мы имеем квадратичные вычеты в собственном множестве. Ответы $$x \equiv +1\left( {\bmod {\text{ }}7} \right)$$, $$x \equiv -1\left( {\bmod {\text{ }}7} \right)$$, $$x \equiv +5\left( {\bmod {\text{ }}11} \right)$$ и $$x \equiv -5\left( {\bmod {\text{ }}11} \right)$$. Теперь мы можем из них составить четыре системы уравнений:
Ответы : $$x = \pm 6$$ и $$\pm 27$$.
Как сложно решить квадратичное сравнение по составному модулю? Главная задача — это
разложение модуля на множители. Другими словами, сложность решения квадратичного сравнения по составному модулю — такая же, как и разложения на множители составного целого числа. Как мы видели раньше, если n очень большое, то разложение на множители неосуществимо.
Возведение в степень и логарифм инверсны друг другу. Следующие разделы показывают отношения между ними, в которых a называется основой возведения в степень или логарифма.
Возведение в степень: y = ax -> логарифм: x = logay
В криптографии общая модульная операция — возведение в степень. Мы часто должны вычислять
y = ax mod n
Быстрое возведение в степень возможно при использовании специальных методов возведения в квадрат и умножения. В традиционных алгоритмах, чтобы возводить в степень, применяется только умножение, но быстрый алгоритм возведения в степень использует и возведение в квадрат, и умножение. Главная идея этого метода — выполнение возведения в степень с помощью обработки двоичного числа с nb битами ( $${x_0}$$ до $${x_{{n_b}}}_{ - 1}$$ ). Например, x = 22 = (10110) 2. Вообще, число x может быть записано как
Теперь мы можем написать y = ax, как это показано на рис. 13.3.
(рис 13.3) Идея метода "возведения в квадрат и умножения"Обратите внимание, что y — произведение элементов числа n. Каждый элемент — либо 1 (если соответствующий бит — 0 ), либо a2i (если соответствующий бит — 1 ). Другими словами, элемент a2i участвует в умножении, если бит — 1, или не участвует, если бит — 0 (умножение на 1 не меняет числа). Рисунок 13.3 дает общую идею, как написать алгоритм. Мы можем непрерывно взводить в квадрат $$a,{a^2},{a^4} \ldots {a^{{2^{{n_b}}} - 1}}$$ Если соответствующий бит — 0, элемент не участвует в процессе умножения; если бит — 1, то участвует. Алгоритм 13.1 отражает эти два свойства.
Возведение_в_ квадрат_и_умножение (a,x,n)
{
y <- 1
for (i <- 0 to nb - 1) //nb — число бит в x
{
if (xi = 1) y <- a x y mod n //умножение, только если бит 1
a <- a2 mod n
} //в последней итерации возведение в степень не нужно
return y
}
Алгоритм 13.1 использует nb итерации. В каждой итерации он проверяет значение соответствующего бита. Если значение бита равно 1, он умножает текущее значение на предыдущее значение результата. Затем полученный результат является базой для следующей итерации. Обратите внимание, что возведение в квадрат в последнем шаге не нужно (результат не используется).
Пример 13.7
Рисунок 13.4 показывает процесс для подсчета y = ax с использованием алгоритма 13.1 (для простоты изображения модули не показаны). В этом случае x = 22 = (10110) 2. Это число имеет 5 бит.
(рис 13.4) Демонстрация вычисления a22 с использованием метода "возведения в квадрат и умножения"Возведение в квадрат делается на каждом шаге за исключением последнего. Умножение делается, если соответствующий бит равен 1. На рисунке 13.4 показано, как постепенно формируется значение y до значения y = a22. Затемненный прямоугольник означает, что умножение не делается и предыдущее значение переносится на следующий шаг. Таблица 13.1 показывает, как вычисляется значение для y = 1722 mod 21. Результат — y = 4.
| i | xi | Умножение (Инициализация y = 1) | Возведение в степень (Инициализация a = 17) |
|---|---|---|---|
| 0 | 0 | a = 172 mod 21 =16 | |
| 1 | 1 | y = 1 x 16 mod 21 =16 $$\to$$ | a = 162 mod 21 = 4 |
| 2 | 1 | y = 16 x 4 mod 21 =1 $$\to$$ | a = 42 mod 21 =16 |
| 3 | 0 | a = 162 mod 21 = 4 | |
| 4 | 1 | y = 1 x 4 mod 21 = 4 $$\to$$ |
Сложность. Алгоритм 13.1 использует максимально 2nb арифметических операций, в которых nb является длиной модуля в битах (nb = log2n). Сложность в O(nb) или полиномиальная сложность.
Альтернативный алгоритм. Заметим, что алгоритм 13.1 проверяет значение битов в x справа налево (от самого младшего до самого старшего). Может быть написан другой алгоритм, чтобы использовать обратный порядок. Мы выбрали вышеупомянутый алгоритм, потому что операция возведения в квадрат полностью независима от операции умножения; они могут быть сделаны параллельно, чтобы увеличить скорость обработки. Альтернативные алгоритмы оставляем как упражнение.
Мы также должны обсудить модульный логарифм, который используется в криптографии. Если мы применяем возведение в степень для того, чтобы зашифровать или расшифровывать сообщение, противник может использовать логарифм для раскрытия этого сообщения Мы должны знать, трудно ли получить операцию, противоположную возведению в степень.
Первое решение, которое могло бы прийти на ум, для решения x = loga y (mod n): мы можем написать алгоритм, который непрерывно вычисляет y = ax mod n, пока не находит заданное значение y. Алгоритм 13.2 показывает этот подход.
$$\tt\parindent0pt
Modular\_Logarithm (a, y, n\}
\{
\ \ for (x = 1 to n — 1) // k число бит в x
\ \ \{
\ \ \ \ if ($y \equiv a^{x} \mod\ n$) return x
\ \ \}
\ \ return failure
\} $$
Алгоритм 13.2 явно очень неэффективен. Сложность разрядной операции — 0 (2n) или показательна.
Второй подход состоит в том, чтобы использовать понятие дискретного логарифма. Рассмотрение этого понятия требует изучения некоторых свойств мультипликативных групп.
Конечная мультипликативная группа. В криптографии мы часто используем мультипликативную конечную группу: $$G = \<{Z_{n*}}, \times \>$$, в которой применяемая операция является умножением. Множество Zn* содержит целые числа от 1 до n–1, которые являются взаимно простыми с n, нейтральный элемент — e = 1. Обратите внимание, что когда модуль группы — простое число, мы имеем $$G = \<{Z_{p*}}, \times \>$$. Эта группа — специальный случай группы первого типа, так что мы концентрируемся на этой группе.
Порядок группы. В лекцииях 5-6 мы обсуждали порядок конечной группы |G| для того, чтобы определить число элементов в группе G. Было доказано, что в группе $$G = \<{Z_{n*}}, \times \>$$ порядок группы (число элементов) — n может быть разложено на множители в виде простых чисел.
Пример 13.8
Найти порядок группы $$G = \<{Z_{21*}}, \times \>,$$ $$|G| = \varphi (21) = \varphi (3) \times \varphi (7) = 2 \times 6 = 12$$. В этой группе 12 элементов: 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19 и 20. Все — взаимно простые с 21.
Порядок элемента. В лекциях 5-6 мы также обсуждали порядок элемента — ord (a).
В $$G = \<{Z_{n*}}, \times \>,$$ мы продолжаем определение. Порядок элемента a есть наименьшее целое число, такое, что $${a^i} \equiv e(\bmod n)$$. В этом случае нейтральный элемент e равен 1.
Пример 13.9
Найдите порядок всех элементов в $$G = \<{Z_{10*}}, \times \>$$.
Решение
Эта группа имеет только $$\varphi (10) = 4$$ элемента: 1, 3, 7, 9. Мы можем найти порядок каждого элемента методом "проб и ошибок". Однако, согласно результатам лекций 5-6, порядок элемента является делителем порядка группы (теорема Лагранжа). Целые числа, которые делят 4, — 1, 2 и 4. Это означает, что в каждом случае мы должны проверить только эти числа и найти порядок элемента,
a. $${1^1} = 1\bmod \left( {10} \right) \to ord\left( {10} \right) = 1$$.
b. $${3^1} = 3\bmod \left( {10} \right);{3^2} \equiv 9\bmod \left( {10} \right);{3^4} \equiv 1\bmod \left( {10} \right) \to ord\left( 3 \right) = 4$$.
c. $${7^1} = 7\bmod \left( {10} \right);{7^2} \equiv 9\bmod \left( {10} \right);{7^4} \equiv 1\bmod \left( {10} \right) \to ord\left( 7 \right) = 4$$
d. $${9^1} = 9\bmod \left( {10} \right);{9^2} \equiv 1\bmod \left( {10} \right) \to ord\left( 9 \right) = 2$$.
Теорема Эйлера. Другая теорема, относящаяся к этому вопросу, — это a является членом $$G = \<{Z_{n^*}}, \times \>$$,
то $${a^{\varphi (n)}} = 1\bmod n$$ ;
Эта теорема очень полезна, потому что показывает, что равенство Ai = 1 mod n сохраняется, если $$i = \varphi (n)$$. Заметим: это не отрицает, что равенство может выполняться и если $$i < \varphi (n)$$. Другими словами, это отношение показывает, что равенство выполняется по меньшей мере однажды.
Пример 13.10
Таблица 13.2 показывает результат ai = x (mod 8) для группы $$G = \<{Z_{8^*}}, \times \>$$. Обратите внимание, что $$\varphi (8) = 4$$. Это элементы — 1, 3, 5 и 7.
| i=1 | i=2 | i=3 | i=4 | i=5 | i=6 | i=7 | |
| a=1 | x:1 | x:1 | x:1 | x:1 | x:1 | x:1 | x:1 |
|---|---|---|---|---|---|---|---|
| a=3 | x:3 | x:1 | x:3 | x:1 | x:3 | x:1 | x:3 |
| a=5 | x:5 | x:1 | x:5 | x:1 | x:5 | x:1 | x:5 |
| a=7 | x:7 | x:1 | x:7 | x:1 | x:7 | x:1 | x:7 |
Таблица 13.2 показывает некоторые моменты вычислений. Первый: затемненная область показывает результат применения x = 1 для каждого a. Второй момент: когда таблица показывает, что значение 1 может быть получено для многих значений i — в первую очередь, значение i, равное порядку элемента (обведено в таблице жирной линией). Порядок элементов: ord (1) = 1, ord (3) = 2, ord (5) = 2 и ord (7) = 2.
Первообразные корни. Очень интересное понятие в мультипликативной группе — группы первообразного корня, которые используются в
Пример 13.11
Таблица 13.2 показывает, что там нет первообразных корней $$G = \<{Z_{8^*}}, \times \>$$, потому что ни один элемент не имеет порядок, равный $$\varphi (8) = 4$$. Порядок всех элементов — меньше, чем 4.
Пример 13.12
Таблица 13.3 показывает результат $${a^i} \equiv x\left( {\bmod {\text{ }}7} \right)$$ для группы $$G = \<{Z_{7^*}}, \times \>$$. В этой группе $$\varphi (7) = 6$$.
| i=1 | i=2 | i=3 | i=4 | i=5 | i=6 | |
| a=1 | x:1 | x:1 | x:1 | x:1 | x:1 | x:1 |
|---|---|---|---|---|---|---|
| a=2 | x:2 | x:4 | x:1 | x:2 | x:4 | x:1 |
| a=3 | x:3 | x:2 | x:6 | x:4 | x:5 | x:1 |
| a=4 | x:4 | x:2 | x:1 | x:4 | x:2 | x:1 |
| a=5 | x:5 | x:4 | x:6 | x:2 | x:3 | x:1 |
| a=6 | x:6 | x:1 | x:6 | x:1 | x:6 | x:1 |
Порядок элементов – $$ord\left( 1 \right) = 1$$, $$ord\left( 2 \right) = 3$$, $$ord\left( 3 \right) = \underline 6 $$, $$ord\left( 4 \right) = 3$$, $$ord\left( 5 \right) = \underline 6 $$ и $$ord\left( 6 \right) = 1$$.
Таблица 13.3 показывает, что только два элемента, 3 и 5, имеют порядок в $$i = \varphi (n) = 6$$. Поэтому эта группа имеет только два примитивных корня: 3 и 5.
Было доказано, что группа $$G = \<{Z_{n^*}}, \times \>$$ имеет примитивный корень, только если n = 2, 4, pt, или 2pt, в которой p является нечетным простым числом (не 2 ) и t — целое число.
Пример 13.13
Для какого значения n группа $$G = \<{Z_{n^*}}, \times \>$$ имеет примитивные корни: 17, 20, 38 и 50?
Решение
a. $$G = \<{Z_{17^*}}, \times \>$$ имеет примитивные корни, потому что 17 — простое число ( pt, где t равно 1 ).
b. $$G = \<{Z_{20^*}}, \times \>$$ не имеет никаких примитивных корней.
c. $$G = \<{Z_{38^*}}, \times \>$$ имеет 19 — простое число.
d. $$G = \<{Z_{50^*}}, \times \>$$ имеет 5 — простое число.
Если группа имеет примитивный корень, то обычно она имеет несколько таких корней. Число примитивных корней может быть вычислено как — $$\varphi (\varphi (n))$$. Например, число примитивных корней $$G = \<{Z_{17^*}}, \times \>$$ — это — $$\varphi (\varphi (n)) = \varphi (16) = 8$$. Обращаем внимание, что нужно сначала проверить, имеет ли группа какой-либо примитивный корень, прежде чем находить число корней.
Рассмотрим три вопроса:
1. Если дан элемент a и группа $$G = \<{Z_{n^*}}, \times \>$$, как можно определить, является ли a примитивным корнем G? Это не такая легкая задача.
а. Мы должны найти $$\varphi (n)$$, — эта задача по сложности подобна задаче разложения на множители числа n.
б. Мы должны найти $$ord(a) = \varphi (n)$$.
2. Если дана группа $$G = \<{Z_{n^*}}, \times \>$$, как найти все примитивные корни $$\varphi $$? Эта задача более трудная, чем первая задача, потому что мы должны повторить вычисления по п.1.б для всей группы.
3. Если дана группа $$G = \<{Z_{n^*}}, \times \>$$, то как выбирать примитивный корень G? В криптографии мы должны найти, по крайней мере, один примитивный корень в группе. Однако в этом случае значение n выбирается пользователем, и пользователь знает $$\varphi (n)$$. Пользователь пробует последовательно несколько элементов, пока не находит первый из них.
Циклическая группа. Циклические группы уже обсуждались в лекциях 5-6. Обратите внимание на то, что, если группа $$G = \<{Z_{n^*}}, \times \>$$ имеет примитивные корни, то они циклически повторяются. Каждый примитивный корень — генератор и может использоваться для создания целого набора. Другими словами, если g — примитивный корень в группе, мы можем генерировать набор Zn* как
Пример 13.14
Группа $$G = \<{Z_{10^*}}, \times \>$$ имеет два примитивных корня, потому что $$\varphi (10) = 4$$ и $$\varphi (\varphi (10)) = 2$$. Можно найти примитивные корни - это 3 и 7. Ниже показано, как можно создать целый набор Z10*, использующий каждый примитивный корень.
g = 3 -> g1 mod 10 = 3 g2 mod 10 = 9 g3 mod 10 = 7 g4 mod 10 = 1 g = 7 -> g1 mod 10 = 7 g2 mod 10 = 9 g3 mod 10 = 3 g4 mod 10 = 1
Обратите внимание, что группа $$G = \<{Z_{p^*}}, \times \>$$ всегда циклическая, потому что p — простое.
Группа G = < Zn*, x > является циклической группой, если она имеет примитивные корни. Группа G = < Zp*, x > всегда является циклической.
Идея дискретного логарифма. Группа $$G = \<{Z_p}^*, \times \>$$ имеет несколько интересных свойств.
1 до p – 1.gx, где x — целое число от 1 до $$\varphi (n) = p - 1$$.k примитивных корней, то вычисления могут быть сделаны для k различных оснований. Данный x = logg y для любого элемента y в данном множестве, но есть другой элемент x, который является логарифмом y по основанию g. Этот тип логарифма называют дискретным логарифмом. Lg, чтобы показать, что основание — g (сравнение по модулю).Теперь рассмотрим, как решаются задачи типа y = ax (mod n), т. е. дано y, а мы должны найти x.
Табулирование дискретных логарифмов. Один из способов решения вышеупомянутой проблемы — использовать таблицу для каждого Zp* и различных оснований. Этот тип таблицы может быть предварительно рассчитан и сохранен. Например, таблица 13.4 показывает значения Z7*. Мы знаем, что мы имеем два примитивных корня или основания в данном множестве.
| y | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| x = L3y | 6 | 2 | 1 | 4 | 5 | 3 |
| x = L5y | 6 | 4 | 5 | 2 | 1 | 3 |
Составив таблицы для других 10.
Пример 13.15
Найдите x в каждом из следующих случаев:
a. $$4 \equiv {3^x}\left( {\bmod {\text{ }}7} \right)$$
b. $$6 \equiv {5^x}\left( {\bmod {\text{ }}7} \right)$$
Решение
Мы можем легко использовать таблицу 13.4
a. $$4 \equiv {3^x}\left( {\bmod {\text{ }}7} \right) \to {L_3}4\left( {\bmod {\text{ }}7} \right) = 4{\text{ }}\bmod {\text{ }}7$$
b. $$6 \equiv {5^x}\left( {\bmod {\text{ }}7} \right) \to {L_5}6\left( {\bmod {\text{ }}7} \right) = 3{\text{ }}\bmod {\text{ }}7$$
Использование свойств дискретных логарифмов. Чтобы показать, что n.
| Традиционные логарифмы | |
|---|---|
| loga 1 = 0 | Lg $$\equiv$$ 0(mod $$\phi$$ (n)) |
| loga (x x y) = logax + logay | Lg(x x y) $$\equiv$$ Lgx + Lgy |
| logaxk = k x logax | Lgx $$\equiv$$ k x Lgx(mod $$\phi$$ (n)) |
Использование алгоритмов, основанных на дискретных логарифмах. Таблицы и свойства y = a x (mod n), когда n является очень большим. Для решения этой проблемы были разработаны несколько алгоритмов, в которых используется основная идея
Нижеследующие книги и сайты дают более детальную информацию о предметах, рассмотренных в этой лекции. Пункты, приведенные в квадратных скобках, содержатся в списке в конце книги.
[Ros06] [Cou99], [BW00] и [Bla03] — для тем, которые обсуждаются в этой лекции.
Нижеследующие сайты дают больше информации о темах, обсужденных в этой лекции.
1, простые числа и 1 и непосредственно само на себя. Составной объект — положительное целое число по крайней мере с двумя делителями.phi -функция $$\varphi (n)$$, которую иногда называют функцией-тотиентом Эйлера, играет очень важную роль в криптографии. Функция указывает число целых чисел, которые меньше чем n и являются взаимно простыми с n.| Ферма | Первая версия : Если НОД(a,p) = 1, то ap-1 $$\equiv$$ 1(mod p) |
| Вторая версия: ap $$\equiv$$ a(mod p) | |
| Эйлер | Первая версия: Если НОД(a,n) = 1, то a $$\phi$$ (n) $$\equiv$$ 1 (mod p) |
| Вторая версия: Если n= p x q и a < n, то a>kx $$\phi$$ (n)+1 $$\equiv$$ a(mod n) |
1, может быть разложено на множители в виде простых чисел. Мы рассмотрели несколько методов разложения на множители, включая проверку делением — Ферма, метод Полларда p – 1, метод РО ( $$\rho $$ ) Полларда, квадратичное решето и решето поля чисел.100 000 и 200 000.100 000 и 200 0001 – 10.100, 1000, 10 000, 100 000 и 1 000 000. Также найти наибольший простой сомножитель 101, 1001, 10 001, 100 001 и 1 000 01.4k + 1, либо 4k + 3, где k — положительное целое число.5k + 1, 5k + 2, 5 k + 3 и 5k + 4, где k: является положительным целым числом.224 – 1 и 216 – 1 – составные числа. Подсказка: используйте выражение (a2 – b2).2, может быть представлено как сумма двух простых чисел. Проверьте это предположение для 10, 24, 28 и 100.n2 + 1. Найдите некоторые из них.515 mod 131518 mod 1745617 mod 17145 mod 1015-1 mod 1315-1 mod 1727-l mod 4170-1 mod 101Обратите внимание, что все модули — простые числа.
12-1 mod 7716-1 mod 32320-1 mod 40344-1 mod 667Обратите внимание, что $$77 = 7 \times 11$$, $$323 = 17 \times 19$$, $$403 = 31 \times 13$$ и $$667 = 23 \times 29$$.
М23, М29 и М31. Подсказка: любой делитель 2kp + 1.2n – 1 — простое число, то n — простое число. Этот факт может использоваться для проверки на простоту? Объясните, как.100, 110, 130, 150, 200, 250, 271, 341, 561. Используйте основание 2.100, 109, 201, 271, 341, 349. Используйте основание 2.271, 3149, 9673.a = 2, x = 3 и несколько простых чисел, чтобы показать, что если p — простое число, то выполняется следующее сравнение: (x – a) p = (xp – a) (mod p).n -ное простое число может быть приближенно вычислено как pn = n ln n. Проверьте это на нескольких простых числах.x для следующих наборов сравнений, используя китайскую теорему об остатках.Z13*, Z17* и Z23*.2124 mod 832023 mod 461173641 mod 2134200135 mod 20001 миллион бит в секунду. Вы хотите затратить только 1 час на испытание простоты чисел. Какое наибольшее число вы можете проверить, используя следующие методы, проверяющие простоту чисел?1 миллион бит в секунду. Вы хотите потратить только 1 час на разложение составного целого числа. Какое наибольшее число вы можете разложить на множители, используя следующие методы разложения на множители?1. Измените алгоритм 13.1, чтобы показать это.Zp*.Zp*.Zp*.Zp*.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.