Показатель числа по модулю. Число по модулю


Показатель числа по модулю - это... Что такое Показатель числа по модулю?

Показателем, или мультипликативным порядком, целого числа a по модулю m называется наименьшее положительное целое число , такое, что

Показатель определен только для чисел a, взаимно простых с модулем m, то есть для элементов группы обратимых элементов кольца вычетов по модулю m. При этом, если показатель числа a по модулю определен, то он является делителем значения функции Эйлера (следствие теоремы Лагранжа).

Чтобы показать зависимость показателя от a и m, его также обозначают , а если m фиксировано, то просто .

Свойства

  • , поэтому можно считать, что показатель задан на классе вычетов по модулю m.
  • . В частности, и , где — функция Кармайкла, а — функция Эйлера.
  • ; если , то
  • Если p — простое число и , то — все решения сравнения .
  • Если p — простое число, то — образующая группы .
  • Если — количество классов вычетов с показателем , то . А для простых модулей даже .
  • Если p — простое число, то группа вычетов циклична и потому, если , где g — образующая, , а k взаимно просто с , то . В общем случае для произвольного модуля m можно вывести аналогичную формулу, пользуясь теоремой о структуре мультипликативной группы вычетов.

Пример

Так как , но , , , то порядок числа 2 по модулю 15 равен 4.

Вычисление

Если известно разложение модуля m на простые множители и известно разложение чисел на простые множители, то показатель заданного числа a может быть найден за полиномиальное время от . Для вычисления достаточно найти разложение на множители функции Кармайкла и вычислить все для всех . Поскольку число делителей ограничено многочленом от , а возведение в степень по модулю происходит за полиномиальное время, то алгоритм поиска будет полиномиальным.

См. также

Литература

  • Бухштаб Теория чисел
  • Виноградов Теория чисел

dic.academic.ru

Показатель числа по модулю — WiKi

Показателем, или мультипликативным порядком, целого числа a{\displaystyle a} по модулю m{\displaystyle m} называется наименьшее положительное целое число ℓ{\displaystyle \ell }, такое, что[1][2]

aℓ≡1(modm).{\displaystyle a^{\ell }\equiv 1{\pmod {m}}.}

Показатель определен только для чисел a{\displaystyle a}, взаимно простых с модулем m{\displaystyle m}, то есть для элементов группы обратимых элементов кольца вычетов по модулю m{\displaystyle m}. При этом, если показатель числа a{\displaystyle a} по модулю m{\displaystyle m} определен, то он является делителем значения функции Эйлера φ(m){\displaystyle \varphi (m)} (следствие теоремы Лагранжа) и значения функции Кармайкла λ(m){\displaystyle \lambda (m)}.

Чтобы показать зависимость показателя ℓ{\displaystyle \ell } от a{\displaystyle a} и m{\displaystyle m}, его также обозначают Pm(a){\displaystyle P_{m}(a)}, а если m{\displaystyle m} фиксировано, то просто P(a){\displaystyle P(a)}.

Свойства

  • a≡b(modm)⇒P(a)=P(b){\displaystyle a\equiv b{\pmod {m}}\Rightarrow P(a)=P(b)} , поэтому можно считать, что показатель задан на классе вычетов a¯{\displaystyle {\bar {a}}}  по модулю m{\displaystyle m} .
  • an≡1(modm)⇒P(a)∣n{\displaystyle a^{n}\equiv 1{\pmod {m}}\Rightarrow P(a)\mid n} . В частности, P(a)∣λ(m){\displaystyle P(a)\mid \lambda (m)}  и P(a)∣φ(m){\displaystyle P(a)\mid \varphi (m)} , где λ(m){\displaystyle \lambda (m)}  — функция Кармайкла, а φ(m){\displaystyle \varphi (m)}  — функция Эйлера.
  • at≡as(modm)⇔t≡s(modP(a)).{\displaystyle a^{t}\equiv a^{s}{\pmod {m}}\Leftrightarrow t\equiv s{\pmod {P(a)}}.} 
  • P(as)∣P(a){\displaystyle P(a^{s})\mid P(a)} ; если gcd(s,P(a))=1{\displaystyle \gcd(s,P(a))=1} , то P(as)=P(a).{\displaystyle P(a^{s})=P(a).} 
  • Если p{\displaystyle p}  — простое число и P(a)=k{\displaystyle P(a)=k} , то a,…,ak{\displaystyle a,\;\ldots ,\;a^{k}}  — все решения сравнения xk≡1(modp){\displaystyle x^{k}\equiv 1{\pmod {p}}} .
  • Если p{\displaystyle p}  — простое число, то P(a)=p−1⇔a{\displaystyle P(a)=p-1\Leftrightarrow a}  — образующая группы Zp{\displaystyle \mathbb {Z} _{p}} .
  • Если ψ(k){\displaystyle \psi (k)}  — количество классов вычетов с показателем k{\displaystyle k} , то ∑k∣φ(m)ψ(k)=φ(m){\displaystyle \sum \limits _{k\,\mid \,\varphi (m)}\psi (k)=\varphi (m)} . А для простых модулей даже ψ(k)=φ(k){\displaystyle \psi (k)=\varphi (k)} .
  • Если p{\displaystyle p}  — простое число, то группа вычетов Zp×{\displaystyle \mathbb {Z} _{p}^{\times }}  циклична и потому, если a=gdk{\displaystyle a=g^{dk}} , где g{\displaystyle g}  — образующая, d∣p−1{\displaystyle d\mid p-1} , а k{\displaystyle k}  — взаимно просто с p−1{\displaystyle p-1} , то P(a)=p−1d{\displaystyle P(a)={\frac {p-1}{d}}} . В общем случае для произвольного модуля m{\displaystyle m}  можно вывести аналогичную формулу, пользуясь теоремой о структуре мультипликативной группы вычетов Zm×{\displaystyle \mathbb {Z} _{m}^{\times }} .

Пример

Так как 24≡1(mod15){\displaystyle 2^{4}\equiv 1{\pmod {15}}} , но 21≢1(mod15){\displaystyle 2^{1}\not \equiv 1{\pmod {15}}} , 22≢1(mod15){\displaystyle 2^{2}\not \equiv 1{\pmod {15}}} , 23≢1(mod15){\displaystyle 2^{3}\not \equiv 1{\pmod {15}}} , то порядок числа 2 по модулю 15 равен 4.

Вычисление

Приложения

См. также

Примечания

Литература

ru-wiki.org

Показатель числа по модулю — Википедия с видео // WIKI 2

Показателем, или мультипликативным порядком, целого числа a{\displaystyle a} по модулю m{\displaystyle m} называется наименьшее положительное целое число ℓ{\displaystyle \ell }, такое, что[1][2]

aℓ≡1(modm).{\displaystyle a^{\ell }\equiv 1{\pmod {m}}.}

Показатель определен только для чисел a{\displaystyle a}, взаимно простых с модулем m{\displaystyle m}, то есть для элементов группы обратимых элементов кольца вычетов по модулю m{\displaystyle m}. При этом, если показатель числа a{\displaystyle a} по модулю m{\displaystyle m} определен, то он является делителем значения функции Эйлера φ(m){\displaystyle \varphi (m)} (следствие теоремы Лагранжа) и значения функции Кармайкла λ(m){\displaystyle \lambda (m)}.

Чтобы показать зависимость показателя ℓ{\displaystyle \ell } от a{\displaystyle a} и m{\displaystyle m}, его также обозначают Pm(a){\displaystyle P_{m}(a)}, а если m{\displaystyle m} фиксировано, то просто P(a){\displaystyle P(a)}.

Энциклопедичный YouTube

  • 1/5

    Просмотров:

    1 971

    1 439

    800

    2 046

    3 456

  • Теория чисел. 7. Решаем сравнения 1 й степени

  • Свойства чисел и модуль

  • Лекция 67: Быстрое возведение в степень

  • Быстрое возведение в степень

  • Как устно и быстро возводить в квадрат

Содержание

Свойства

  • a≡b(modm)⇒P(a)=P(b){\displaystyle a\equiv b{\pmod {m}}\Rightarrow P(a)=P(b)}, поэтому можно считать, что показатель задан на классе вычетов a¯{\displaystyle {\bar {a}}} по модулю m{\displaystyle m}.
  • an≡1(modm)⇒P(a)∣n{\displaystyle a^{n}\equiv 1{\pmod {m}}\Rightarrow P(a)\mid n}. В частности, P(a)∣λ(m){\displaystyle P(a)\mid \lambda (m)} и P(a)∣φ(m){\displaystyle P(a)\mid \varphi (m)}, где λ(m){\displaystyle \lambda (m)} — функция Кармайкла, а φ(m){\displaystyle \varphi (m)} — функция Эйлера.
  • at≡as(modm)⇔t≡s(modP(a)).{\displaystyle a^{t}\equiv a^{s}{\pmod {m}}\Leftrightarrow t\equiv s{\pmod {P(a)}}.}
  • P(as)∣P(a){\displaystyle P(a^{s})\mid P(a)}; если gcd(s,P(a))=1{\displaystyle \gcd(s,P(a))=1}, то P(as)=P(a).{\displaystyle P(a^{s})=P(a).}
  • Если p{\displaystyle p} — простое число и P(a)=k{\displaystyle P(a)=k}, то a,…,ak{\displaystyle a,\;\ldots ,\;a^{k}} — все решения сравнения xk≡1(modp){\displaystyle x^{k}\equiv 1{\pmod {p}}}.
  • Если p{\displaystyle p} — простое число, то P(a)=p−1⇔a{\displaystyle P(a)=p-1\Leftrightarrow a} — образующая группы Zp{\displaystyle \mathbb {Z} _{p}}.
  • Если ψ(k){\displaystyle \psi (k)} — количество классов вычетов с показателем k{\displaystyle k}, то ∑k∣φ(m)ψ(k)=φ(m){\displaystyle \sum \limits _{k\,\mid \,\varphi (m)}\psi (k)=\varphi (m)}. А для простых модулей даже ψ(k)=φ(k){\displaystyle \psi (k)=\varphi (k)}.
  • Если p{\displaystyle p} — простое число, то группа вычетов Zp×{\displaystyle \mathbb {Z} _{p}^{\times }} циклична и потому, если a=gdk{\displaystyle a=g^{dk}}, где g{\displaystyle g} — образующая, d∣p−1{\displaystyle d\mid p-1}, а k{\displaystyle k} — взаимно просто с p−1{\displaystyle p-1}, то P(a)=p−1d{\displaystyle P(a)={\frac {p-1}{d}}}. В общем случае для произвольного модуля m{\displaystyle m} можно вывести аналогичную формулу, пользуясь теоремой о структуре мультипликативной группы вычетов Zm×{\displaystyle \mathbb {Z} _{m}^{\times }}.

Пример

Так как 24≡1(mod15){\displaystyle 2^{4}\equiv 1{\pmod {15}}}, но 21≢1(mod15){\displaystyle 2^{1}\not \equiv 1{\pmod {15}}}, 22≢1(mod15){\displaystyle 2^{2}\not \equiv 1{\pmod {15}}}, 23≢1(mod15){\displaystyle 2^{3}\not \equiv 1{\pmod {15}}}, то порядок числа 2 по модулю 15 равен 4.

Вычисление

Если известно разложение модуля m{\displaystyle m} на простые множители pj{\displaystyle p_{j}} и известно разложение чисел pj−1{\displaystyle p_{j}-1} на простые множители, то показатель заданного числа a{\displaystyle a} может быть найден за полиномиальное время от ln⁡m{\displaystyle \ln m}. Для вычисления достаточно найти разложение на множители функции Кармайкла λ(m){\displaystyle \lambda (m)} и вычислить все admodm{\displaystyle a^{d}\mod m} для всех d∣λ(m){\displaystyle d\mid \lambda (m)}. Поскольку число делителей ограничено многочленом от ln⁡m{\displaystyle \ln m}, а возведение в степень по модулю происходит за полиномиальное время, то алгоритм поиска будет полиномиальным.

Приложения

Характеры Дирихле

Характер Дирихле χ{\displaystyle \chi } по модулю m{\displaystyle m} определяется обязательными соотношениями χ(ab)=χ(a)χ(b){\displaystyle \chi (ab)=\chi (a)\chi (b)} и χ(a)=χ(a+m){\displaystyle \chi (a)=\chi (a+m)}. Чтобы эти соотношения выполнялись, необходимо, чтобы χ(a){\displaystyle \chi (a)} был равен какому-либо комплексному корню из единицы степени Pm(a){\displaystyle P_{m}(a)}.

См. также

Примечания

Литература

Эта страница в последний раз была отредактирована 14 декабря 2017 в 17:24.

wiki2.org

Показатель числа по модулю другого числа — Национальная библиотека им. Н. Э. Баумана

Материал из Национальной библиотеки им. Н. Э. БауманаПоследнее изменение этой страницы: 08:12, 9 июня 2016.

Определение

Определение «Определение»

Показателем a{\displaystyle a} по модулю m{\displaystyle m} называется наименьший положительный показатель степени a{\displaystyle a}, сравнимой с единицей по модулю m{\displaystyle m}:

aρ≡1 mod m{\displaystyle a^{\rho} \equiv 1\ mod\ m},

где ρ{\displaystyle \rho } - показатель.

Пример

Найти показатель числа 3 по модулю 11.31, 32, 33, 34, 35≢1 mod 11, 36≡mod 11 ⇒ ρ=6{\displaystyle 3^1,\ 3^2,\ 3^3,\ 3^4,\ 3^5 \not\equiv 1\ mod\ 11,\ 3^6 \equiv mod\ 11\ \Rightarrow\ \rho = 6}

Свойства

Везде далее (a, m)=1{\displaystyle (a,\ m) = 1}

Теорема Теорема

Доказательство

Если b≡a mod m{\displaystyle b \equiv a\ mod\ m}, то ρa=ρb{\displaystyle \rho_a = \rho_b}

Для доказательства теоремы сперва вспомним[1], что если b≡a mod m{\displaystyle b \equiv a\ mod\ m}, то и bn ≡an mod m, ∀n≥0{\displaystyle b^n\ \equiv a^n\ mod\ m,\ \forall n \geq 0}. Из aρa≡1 mod m{\displaystyle a^{\rho_a} \equiv 1\ mod\ m} следует, что bρa≡1 mod m{\displaystyle b^{\rho_a} \equiv 1\ mod\ m}, а из ar≢1 mod m, 1≤r<ρa{\displaystyle a^r \not \equiv 1\ mod\ m,\ 1 \leq r < \rho_a} следует ar≢1 mod m, 1≤r<ρa{\displaystyle a^r \not \equiv 1\ mod\ m,\ 1 \leq r < \rho_a}, т.е. ρa=ρb{\displaystyle \rho_a = \rho_b}.

Теорема Теорема

Доказательство

Если an≡1 mod m{\displaystyle a^n \equiv 1\ mod\ m}, то ρa|n{\displaystyle \rho_a\, |\, n}
Представим n{\displaystyle n} в виде n=ρaq+r{\displaystyle n = \rho_a \, q + r}, где 1≤r<ρa{\displaystyle 1\leq r < \rho_a}. Так как an≡1 mod m и aρa≡1 mod m{\displaystyle a^n \equiv 1\ mod\ m\ \text{и}\ a^{\rho_a} \equiv 1\ mod\ m}, то 1≡an=aqρa+r=(aρa)q⋅ar=ar mod m{\displaystyle 1 \equiv a^n = a^{q \rho_a + r} = (a^{\rho_a})^q \cdot a^r = a^r\ mod\ m}.

Таким образом, r=0{\displaystyle r = 0 }, ч.т.д.

Теорема Теорема

Доказательство

ρa|φ(m){\displaystyle \rho_a\, |\, \varphi(m)}

Доказательство следует из предыдущей теоремы.

Теорема Теорема

Доказательство

as≡at mod m ⇔ s≡t mod ρa{\displaystyle a^s \equiv a^t\ mod\ m\ \Leftrightarrow\ s \equiv t\ mod\ \rho_a}

1) Пусть as≡at mod m, s≥t{\displaystyle a^s \equiv a^t\ mod\ m,\ s \geq t}. Тогда обе части этого сравнения можно (т.к. (a,m)=1{\displaystyle (a,\, m)=1}) сократить на at{\displaystyle a^t}, так что as−t≡1 mod m{\displaystyle a^{s-t} \equiv 1\ mod\ m}. Таким образом, ρa | s−t, s≡t mod ρa{\displaystyle \rho_a\ |\ s-t,\ s \equiv t\ mod\ \rho_a}.2) Пусть s≡t mod ρa, s≥t≥0{\displaystyle s \equiv t\ mod\ \rho_a,\ s \geq t \geq 0}. Тогда s=t+ρay{\displaystyle s = t + \rho_a y}, где y{\displaystyle y} целое неотрицательное.

as=at+ρay=at(aρa)y≡at mod m{\displaystyle a^s = a^{t + \rho_a y} = a^t (a^{\rho_a})^y \equiv a^t\ mod\ m}
Теорема Теорема

Доказательство

В последовательности a, a2, a3, …{\displaystyle a,\ a^2,\ a^3,\ \dots} все числа принадлежат ρa{\displaystyle \rho_a} классам, вычетами которых являются числа a, a2, a3, …, aρa{\displaystyle a,\ a^2,\ a^3,\ \dots,\ a^{\rho_a}}

По предыдущей теореме числа в последовательности a, a2, a3, …, aρa{\displaystyle a,\ a^2,\ a^3,\ \dots,\ a^{\rho_a}} попарно несравнимы. С другой стороны, в последовательности a, a2, a3, …{\displaystyle a,\ a^2,\ a^3,\ \dots} не больше чем ρa{\displaystyle \rho_a} несравнимых по модулю m{\displaystyle m} чисел. Следовательно, каждое из чисел вида aN (1≤N<∞){\displaystyle a^N\ (1 \leq N < \infty)} сравнимо с одним из чисел последовательности a, a2, a3, …, aρa{\displaystyle a,\ a^2,\ a^3,\ \dots,\ a^{\rho_a}}.

Теорема Теорема

Доказательство

ρas≡ρa⇔(s, ρa)=1{\displaystyle \rho_{a^s} \equiv \rho_a \Leftrightarrow (s,\ \rho_a) = 1}

1) Пусть (s, ρa)=1{\displaystyle (s,\ \rho_a) = 1}. Найдем наименьшее положительное y{\displaystyle y} такое, что (as)y≡1 mod m{\displaystyle (a^s)^y \equiv 1\ mod\ m}. Из этого следует, что asy≡1 mod m{\displaystyle a^{sy} \equiv 1\ mod\ m}, то есть ρa | sy{\displaystyle \rho_a\ |\ sy}, но (s, ρa)=1{\displaystyle (s,\ \rho_a)=1}, значит, ρa | y{\displaystyle \rho_a\ |\ y}, а так как y{\displaystyle y} было выбрано как наименьшее положительное, то оно в точности равно ρa{\displaystyle \rho_a}.2) Пусть (s, ρa)=d>1{\displaystyle (s,\ \rho_a) = d > 1}. Тогда ρad{\displaystyle \frac{\rho_a}{d}} и sd{\displaystyle \frac{s}{d}} - целые числа и (as)ρad=(aρa)sd≡1 mod m{\displaystyle (a^s)^{\frac{\rho_a}{d}} = (a^{\rho_a})^{\frac{s}{d}}\equiv 1\ mod\ m}, т.е. ρas≤ρad<ρa{\displaystyle \rho_{a^s} \leq \frac{\rho_a}{d} < \rho_a }.

Теорема Теорема

Доказательство

Если по модулю m ρa=k{\displaystyle m\ \rho_a=k}, то классы

a¯, a¯2, …, a¯k{\displaystyle \bar{a},\ \bar{a}^2,\ \dots,\ \bar{a}^k}

представляют собой различные решения сравнения:

xk≡1 mod m{\displaystyle x^k \equiv 1\ mod\ m}

Доказательство следует из предыдущих теорем.

Примечание

Статья на Википедии

  1. ↑ Бухштаб, 1966, с.75

Литература

ru.bmstu.wiki

Индекс числа по модулю - это... Что такое Индекс числа по модулю?

Дискретное логарифмирование (DLOG) – задача обращения функции gx в некоторой конечной мультипликативной группе G.

Наиболее часто задачу дискетного логарифмирования рассматривают в группе обратимых элементов кольца вычетов, в мультипликативной группе конечного поля, или в группе точек на эллиптической кривой над конечным полем. Эффективные алгоритмы для решения задачи дискетного логарифмирования в общем случае неизвестны.

Для заданных g и a решение x уравнения gx = a называется дискретным логарифмом элемента a по основанию g. В случае, когда G является группой обратимых элементов кольца вычетов по модулю m, решение называют также индексом числа a по основанию g. Индекс числа a по основанию g гарантированно существует, если g является первообразным корнем по модулю m.

Постановка задачи

Пусть в некоторой конечной мультипликативной абелевой группе G задано уравнение

Решение задачи дискретного логарифмирования состоит в нахождении некоторого целого неотрицательного числа x, удовлетворяющего уравнению (1).

Если оно разрешимо, у него должно быть хотя бы одно натуральное решение, не превышающее порядок группы. Это сразу даёт грубую оценку сложности алгоритма поиска решений сверху — алгоритм полного перебора нашел бы решение за число шагов, не выше порядка данной группы.

Чаще всего рассматривается случай, когда , то есть группа является циклической, порождённой элементом g. В этом случае уравнение всегда имеет решение. В случае же произвольной группы, вопрос о разрешимости задачи дискретного логарифмирования, то есть вопрос о существовании решений уравнения (1), требует отдельного рассмотрения.

Пример

Проще всего рассмотреть задачу дискретного логарифмирования в кольце вычетов по модулю простого числа.

Пусть задано сравнение

Будем решать задачу методом перебора. Выпишем таблицу всех степеней числа 3. Каждый раз мы вычисляем остаток от деления на 17 (например, 33≡27 — остаток от деления на 17 равен 10).

31 ≡ 3 32 ≡ 9 33 ≡ 10 34 ≡ 13 35 ≡ 5 36 ≡ 15 37 ≡ 11 38 ≡ 16
39 ≡ 14 310 ≡ 8 311 ≡ 7 312 ≡ 4 313 ≡ 12 314 ≡ 2 315 ≡ 6 316 ≡ 1

Теперь легко увидеть, что решением рассматриваемого сравнения является x=4, поскольку 34≡13.

На практике модуль обычно является достаточно большим числом, и метод перебора является слишком медленным, поэтому возникает потребность в более быстрых алгоритмах.

Алгоритмы решения

В произвольной мультипликативной группе

Разрешимости и решению задачи дискретного логарифмирования в произвольной конечной абелевой группе посвящена статья BuchmannJ., Jacobson M.J., Teske E. On some computational problems in finite abelian groups[1]. В алгоритме используется таблица, состоящая из пар элементов и выполняется умножений. Данный алгоритм медленный и не пригоден для практического использования. Для конкретных групп существуют свои, более эффективные, алгоритмы.

В кольце вычетов по простому модулю

Рассмотрим уравнение

(2)

где p - простое, b не делится на p. Если a является образующим элементом группы , то уравнение (2) имеет решение при любых b. Такие числа a называются ещё первообразными корнями, и их количество равно φ(p − 1), где φ — функция Эйлера. Решение уравнения (2) можно находить по формуле:

Однако, сложность вычисления по этой формуле хуже, чем сложность перебора.

Следующий алгоритм имеет сложность

Алгоритм

  1. Присвоить
  2. Найти
  3. Составить таблицу значений и упорядочить её.
  4. Составить таблицу значений и упорядочить её.
  5. Найти совпавшие элементы из первой и второй таблиц. Для нихоткуда
  6. Выдать .

Конец алгоритма

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

Алгоритмы с экспоненциальной сложностью
  1. Алгоритм Шенкса (алгоритм больших и малых шагов, baby-step giant-step)
  2. Алгоритм Полига-Хеллмана — работает, если известно разложение числа на простые множители. Сложность: . Если множители, на которые раскладывается p − 1, достаточно маленькие, то алгоритм очень эффективен.
  3. ρ-метод Полларда имеет эвристическую оценку сложности .
Субэкспоненциальные алгоритмы

Данные алгоритмы имеют сложность арифметических операций, где и — некоторые константы. Эффективность алгоритма во многом зависит от близости c к 1 и d — к 0.

  1. Алгоритм Адлемана появился в 1979 году. Это был первый субэкспоненциалный алгоритм дискретного логарифмирования. На практике он всё же недостаточно эффективен. В этом алгоритме .
  2. Алгоритм COS был предложен в 1986 году математиками Копперсмитом (Don Coppersmith), Одлыжко (Andrew Odlyzko) и Шреппелем (Richard Schroeppel). В этом алгоритме константа , . В 1991 году с помощью Этого метода было проведено логарифмирование по модулю . В 1997 году Вебер провел дискретное логарифмирование по модулю с помощью некоторой версии данного алгоритма. Экспериментально показано, что при алгоритм COS лучше решета числового поля.
  3. Решето числового поля было применено к дискретному логарифмированию позднее, чем к факторизации чисел. Первые идеи появились в 1990-х годах. Алгоритм, предложенный Д. Гордоном в 1993 году, имел эвристическую сложность , но оказался достаточно непрактичным. Позднее было предложено множество различных улучшений данного алгоритма. Было показано, что при решето числового поля быстрее, чем COS. Современные рекорды в дискретном логарифмировании получены именно с помощью этого метода.

Наилучшими параметрами в оценке сложности на данный момент является , .

Для чисел специального вида результат можно улучшить. В некоторых случаях можно построить алгоритм, для которого константы будут , . За счёт того, что константа c достаточно близка к 1, подобные алгоритмы могут обогнать алгоритм с .

В произвольном конечном поле

Задача рассматривается в поле GF(q), где q = pn, p — простое.

  1. Алгоритм исчисления индексов (index-calculus) эффективен, если p невелико. В этом случае он имеет эвристическую оценку сложности .
  2. Алгоритм Эль-Гамаля, появившийся в 1985 году, применим при n = 2 и имеет сложность арифметических операций.
  3. Алгоритм Копперсмита дискретного логарифмирования в конечном поле характеристики 2 стал первым субэкспоненциальным алгоритмом дискретного логарифмирования с константой в оценки сложности. Данный алгоритм появился в 1984 году — до изобретения решета числового поля.

В группе точек на эллиптической кривой

Рассматривается группа точек эллиптической кривой над конечным полем. В данной группе определена операция сложения двух точек. Тогда mP — это . Решением задачи дискретного логарифмирования на эллиптической кривой является нахождение такого натурального числа m, что

для заданных точек P и A.

До 1990 года не существовало алгоритмов дискретного логарифмирования, учитывающих особенностей строения группы точек элиптической кривой. Впоследствии, Менезес (Alfred J. Menezes), Окамото (Tatsuaki Okamoto) и Венстон (Scott A. Vanstone) предложили алгоритм, использующий спаривание Вейля. Для эллиптической кривой, определённой над полем GF(q), данный алгоритм сводит задачу дискретного логарифмирования к аналогичной задаче в поле GF(qk). Однако, данное сведение полезно, только если степень k мала. Это условие выполняется, в основном, для суперсингулярных эллиптических кривых. В остальных случаях подобное сведение практически никогда не приводит к субэкспоненциальным алгоритмам.

Вычислительная сложность и приложения в криптографии

Задача дискретного логарифмирования является одной из основных задач, на которых базируется криптография с открытым ключом. Идея, лежащая в основе подобных систем, опирается на высокую вычислительную сложность обращения некоторых числовых функций. В данном случае, операция дискретного логарифмирования является обратной к показательной функции. Последняя вычисляется достаточно просто, в то время как даже самые современные алгоритмы вычисления дискретного логарифма имеют очень высокую сложность, которая сравнима со сложностью наиболее быстрых алгоритмов разложения чисел на множители.

Другая возможность эффективного решения задачи вычисления дискретного логарифма связана с квантовыми вычислениями. Теоретически доказано, что, используя их, дискретный логарифм может быть вычислен за полиномиальное время[2]. В любом случае, если полиномиальный алгоритм вычисления дискретного логарифма будет реализован, это будет означать практическую непригодность криптосистем на его основе.

Классическими криптографическими схемами, базирующимися на сложности задачи дискретного логарифмирования, являются схема выработки общего ключа Диффи-Хеллмана, схема электронной подписи Эль-Гамаля, криптосистема Мэсси-Омуры для передачи сообщений.

Ссылки

  1. ↑ Электронную версию см. на http://citeseer.ist.psu.edu/716900.html
  2. ↑ http://cs.mipt.ru/docs/comp/rus/develop/other/quantum_comp

Wikimedia Foundation. 2010.

dic.academic.ru

Показатель числа по модулю — Википедия (с комментариями)

Материал из Википедии — свободной энциклопедии

Показателем, или мультипликативным порядком, целого числа <math>a</math> по модулю <math>m</math> называется наименьшее положительное целое число <math>\ell</math>, такое, что[1][2]

<math>a^\ell\equiv 1\pmod m.</math>

Показатель определен только для чисел <math>a</math>, взаимно простых с модулем <math>m</math>, то есть для элементов группы обратимых элементов кольца вычетов по модулю <math>m</math>. При этом, если показатель числа <math>a</math> по модулю <math>m</math> определен, то он является делителем значения функции Эйлера <math>\varphi(m)</math> (следствие теоремы Лагранжа) и значения функции Кармайкла <math>\lambda(m)</math>.

Чтобы показать зависимость показателя <math>\ell</math> от <math>a</math> и <math>m</math>, его также обозначают <math>P_m(a)</math>, а если <math>m</math> фиксировано, то просто <math>P(a)</math>.

Свойства

  • <math>a\equiv b\pmod m\Rightarrow P(a)=P(b)</math>, поэтому можно считать, что показатель задан на классе вычетов <math>\bar{a}</math> по модулю <math>m</math>.
  • <math>a^n\equiv 1\pmod m\Rightarrow P(a)\mid n</math>. В частности, <math>P(a)\mid\lambda(m)</math> и <math>P(a)\mid\varphi(m)</math>, где <math>\lambda(m)</math> — функция Кармайкла, а <math>\varphi(m)</math> — функция Эйлера.
  • <math>a^t\equiv a^s\pmod m \Leftrightarrow t\equiv s\pmod{P(a)}.</math>
  • <math>P(a^s)\mid P(a)</math>; если <math>\gcd(s,P(a))=1</math>, то <math>P(a^s)=P(a).</math>
  • Если <math>p</math> — простое число и <math>P(a)=k</math>, то <math>a,\;\ldots,\;a^k</math> — все решения сравнения <math>x^k\equiv 1\pmod p</math>.
  • Если <math>p</math> — простое число, то <math>P(a)=p-1\Leftrightarrow a</math> — образующая группы <math>\mathbb{Z}_p</math>.
  • Если <math>\psi(k)</math> — количество классов вычетов с показателем <math>k</math>, то <math>\sum\limits_{k\,\mid\,\varphi(m)}\psi(k)=\varphi(m)</math>. А для простых модулей даже <math>\psi(k)=\varphi(k)</math>.
  • Если <math>p</math> — простое число, то группа вычетов <math>\mathbb{Z}_p^{\times}</math> циклична и потому, если <math>a=g^{dk}</math>, где <math>g</math> — образующая, <math>d\mid p-1</math>, а <math>k</math> — взаимно просто с <math>p-1</math>, то <math>P(a)=\frac{p-1}{d}</math>. В общем случае для произвольного модуля <math>m</math> можно вывести аналогичную формулу, пользуясь теоремой о структуре мультипликативной группы вычетов <math>\mathbb{Z}_m^{\times}</math>.

Пример

Так как <math>2^4\equiv 1\pmod{15}</math>, но <math>2^1\not\equiv 1\pmod{15}</math>, <math>2^2\not\equiv 1\pmod{15}</math>, <math>2^3\not\equiv 1\pmod{15}</math>, то порядок числа 2 по модулю 15 равен 4.

Вычисление

Если известно разложение модуля <math>m</math> на простые множители <math>p_j</math> и известно разложение чисел <math>p_j-1</math> на простые множители, то показатель заданного числа <math>a</math> может быть найден за полиномиальное время от <math>\ln m</math>. Для вычисления достаточно найти разложение на множители функции Кармайкла <math>\lambda(m)</math> и вычислить все <math>a^d\mod m</math> для всех <math>d\mid\lambda(m)</math>. Поскольку число делителей ограничено многочленом от <math>\ln m</math>, а возведение в степень по модулю происходит за полиномиальное время, то алгоритм поиска будет полиномиальным.

Приложения

Характеры Дирихле

Характер Дирихле <math>\chi</math> по модулю <math>m</math> определяется обязательными соотношениями <math>\chi(ab)=\chi(a)\chi(b)</math> и <math>\chi(a)=\chi(a+m)</math>. Чтобы эти соотношения выполнялись, необходимо, чтобы <math>\chi(a)</math> был равен какому-либо комплексному корню из единицы степени <math>P_{m}(a)</math>.

См. также

Напишите отзыв о статье "Показатель числа по модулю"

Примечания

Литература

Отрывок, характеризующий Показатель числа по модулю

Марья Дмитриевна объявила Наташе о том, что Анатоль был женат. Наташа не хотела верить ей и требовала подтверждения этого от самого Пьера. Соня сообщила это Пьеру в то время, как она через коридор провожала его в комнату Наташи. Наташа, бледная, строгая сидела подле Марьи Дмитриевны и от самой двери встретила Пьера лихорадочно блестящим, вопросительным взглядом. Она не улыбнулась, не кивнула ему головой, она только упорно смотрела на него, и взгляд ее спрашивал его только про то: друг ли он или такой же враг, как и все другие, по отношению к Анатолю. Сам по себе Пьер очевидно не существовал для нее. – Он всё знает, – сказала Марья Дмитриевна, указывая на Пьера и обращаясь к Наташе. – Он пускай тебе скажет, правду ли я говорила. Наташа, как подстреленный, загнанный зверь смотрит на приближающихся собак и охотников, смотрела то на того, то на другого. – Наталья Ильинична, – начал Пьер, опустив глаза и испытывая чувство жалости к ней и отвращения к той операции, которую он должен был делать, – правда это или не правда, это для вас должно быть всё равно, потому что… – Так это не правда, что он женат! – Нет, это правда. – Он женат был и давно? – спросила она, – честное слово? Пьер дал ей честное слово. – Он здесь еще? – спросила она быстро. – Да, я его сейчас видел. Она очевидно была не в силах говорить и делала руками знаки, чтобы оставили ее.

Пьер не остался обедать, а тотчас же вышел из комнаты и уехал. Он поехал отыскивать по городу Анатоля Курагина, при мысли о котором теперь вся кровь у него приливала к сердцу и он испытывал затруднение переводить дыхание. На горах, у цыган, у Comoneno – его не было. Пьер поехал в клуб. В клубе всё шло своим обыкновенным порядком: гости, съехавшиеся обедать, сидели группами и здоровались с Пьером и говорили о городских новостях. Лакей, поздоровавшись с ним, доложил ему, зная его знакомство и привычки, что место ему оставлено в маленькой столовой, что князь Михаил Захарыч в библиотеке, а Павел Тимофеич не приезжали еще. Один из знакомых Пьера между разговором о погоде спросил у него, слышал ли он о похищении Курагиным Ростовой, про которое говорят в городе, правда ли это? Пьер, засмеявшись, сказал, что это вздор, потому что он сейчас только от Ростовых. Он спрашивал у всех про Анатоля; ему сказал один, что не приезжал еще, другой, что он будет обедать нынче. Пьеру странно было смотреть на эту спокойную, равнодушную толпу людей, не знавшую того, что делалось у него в душе. Он прошелся по зале, дождался пока все съехались, и не дождавшись Анатоля, не стал обедать и поехал домой. Анатоль, которого он искал, в этот день обедал у Долохова и совещался с ним о том, как поправить испорченное дело. Ему казалось необходимо увидаться с Ростовой. Вечером он поехал к сестре, чтобы переговорить с ней о средствах устроить это свидание. Когда Пьер, тщетно объездив всю Москву, вернулся домой, камердинер доложил ему, что князь Анатоль Васильич у графини. Гостиная графини была полна гостей. Пьер не здороваясь с женою, которую он не видал после приезда (она больше чем когда нибудь ненавистна была ему в эту минуту), вошел в гостиную и увидав Анатоля подошел к нему. – Ah, Pierre, – сказала графиня, подходя к мужу. – Ты не знаешь в каком положении наш Анатоль… – Она остановилась, увидав в опущенной низко голове мужа, в его блестящих глазах, в его решительной походке то страшное выражение бешенства и силы, которое она знала и испытала на себе после дуэли с Долоховым.

wiki-org.ru

Показатель числа по модулю Википедия

Показателем, или мультипликативным порядком, целого числа

a{\displaystyle a} по модулю m{\displaystyle m} называется наименьшее положительное целое число ℓ{\displaystyle \ell }, такое, что[1][2]aℓ≡1(modm).{\displaystyle a^{\ell }\equiv 1{\pmod {m}}.}

Показатель определен только для чисел a{\displaystyle a}, взаимно простых с модулем m{\displaystyle m}, то есть для элементов группы обратимых элементов кольца вычетов по модулю m{\displaystyle m}. При этом, если показатель числа a{\displaystyle a} по модулю m{\displaystyle m} определен, то он является делителем значения функции Эйлера φ(m){\displaystyle \varphi (m)} (следствие теоремы Лагранжа) и значения функции Кармайкла λ(m){\displaystyle \lambda (m)}.

Чтобы показать зависимость показателя ℓ{\displaystyle \ell } от a{\displaystyle a} и m{\displaystyle m}, его также обозначают Pm(a){\displaystyle P_{m}(a)}, а если m{\displaystyle m} фиксировано, то просто P(a){\displaystyle P(a)}.

Свойства

  • a≡b(modm)⇒P(a)=P(b){\displaystyle a\equiv b{\pmod {m}}\Rightarrow P(a)=P(b)}, поэтому можно считать, что показатель задан на классе вычетов a¯{\displaystyle {\bar {a}}} по модулю m{\displaystyle m}.
  • an≡1(modm)⇒P(a)∣n{\displaystyle a^{n}\equiv 1{\pmod {m}}\Rightarrow P(a)\mid n}. В частности, P(a)∣λ(m){\displaystyle P(a)\mid \lambda (m)} и P(a)∣φ(m){\displaystyle P(a)\mid \varphi (m)}, где λ(m){\displaystyle \lambda (m)} — функция Кармайкла, а φ(m){\displaystyle \varphi (m)} — функция Эйлера.
  • at≡as(modm)⇔t≡s(modP(a)).{\displaystyle a^{t}\equiv a^{s}{\pmod {m}}\Leftrightarrow t\equiv s{\pmod {P(a)}}.}
  • P(as)∣P(a){\displaystyle P(a^{s})\mid P(a)}; если gcd(s,P(a))=1{\displaystyle \gcd(s,P(a))=1}, то P(as)=P(a).{\displaystyle P(a^{s})=P(a).}
  • Если p{\displaystyle p} — простое число и P(a)=k{\displaystyle P(a)=k}, то a,…,ak{\displaystyle a,\;\ldots ,\;a^{k}} — все решения сравнения xk≡1(modp){\displaystyle x^{k}\equiv 1{\pmod {p}}}.
  • Если p{\displaystyle p} — простое число, то P(a)=p−1⇔a{\displaystyle P(a)=p-1\Leftrightarrow a} — образующая группы Zp{\displaystyle \mathbb {Z} _{p}}.
  • Если ψ(k){\displaystyle \psi (k)} — количество классов вычетов с показателем k{\displaystyle k}, то ∑k∣φ(m)ψ(k)=φ(m){\displaystyle \sum \limits _{k\,\mid \,\varphi (m)}\psi (k)=\varphi (m)}. А для простых модулей даже ψ(k)=φ(k){\displaystyle \psi (k)=\varphi (k)}.
  • Если p{\displaystyle p} — простое число, то группа вычетов Zp×{\displaystyle \mathbb {Z} _{p}^{\times }} циклична и потому, если a=gdk{\displaystyle a=g^{dk}}, где g{\displaystyle g} — образующая, d∣p−1{\displaystyle d\mid p-1}, а k{\displaystyle k} — взаимно просто с p−1{\displaystyle p-1}, то P(a)=p−1d{\displaystyle P(a)={\frac {p-1}{d}}}. В общем случае для произвольного модуля m{\displaystyle m} можно вывести аналогичную формулу, пользуясь теоремой о структуре мультипликативной группы вычетов Zm×{\displaystyle \mathbb {Z} _{m}^{\times }}.

Пример

Так как 24≡1(mod15){\displaystyle 2^{4}\equiv 1{\pmod {15}}}, но 21≢1(mod15){\displaystyle 2^{1}\not \equiv 1{\pmod {15}}}, 22≢1(mod15){\displaystyle 2^{2}\not \equiv 1{\pmod {15}}}, 23≢1(mod15){\displaystyle 2^{3}\not \equiv 1{\pmod {15}}}, то порядок числа 2 по модулю 15 равен 4.

Вычисление

Если известно разложение модуля m{\displaystyle m} на простые множители pj{\displaystyle p_{j}} и известно разложение чисел pj−1{\displaystyle p_{j}-1} на простые множители, то показатель заданного числа a{\displaystyle a} может быть найден за полиномиальное время от ln⁡m{\displaystyle \ln m}. Для вычисления достаточно найти разложение на множители функции Кармайкла λ(m){\displaystyle \lambda (m)} и вычислить все admodm{\displaystyle a^{d}\mod m} для всех d∣λ(m){\displaystyle d\mid \lambda (m)}. Поскольку число делителей ограничено многочленом от ln⁡m{\displaystyle \ln m}, а возведение в степень по модулю происходит за полиномиальное время, то алгоритм поиска будет полиномиальным.

Приложения

Характеры Дирихле

Характер Дирихле χ{\displaystyle \chi } по модулю m{\displaystyle m} определяется обязательными соотношениями χ(ab)=χ(a)χ(b){\displaystyle \chi (ab)=\chi (a)\chi (b)} и χ(a)=χ(a+m){\displaystyle \chi (a)=\chi (a+m)}. Чтобы эти соотношения выполнялись, необходимо, чтобы χ(a){\displaystyle \chi (a)} был равен какому-либо комплексному корню из единицы степени Pm(a){\displaystyle P_{m}(a)}.

См. также

Примечания

Литература

wikiredia.ru