Как найти индекс числа по модулю - Сайт, где вы сможете решить свои вопросы

Индексы по простому модулю.

Опр.
Пусть m
– модуль, а, в – взаимно простые с
модулем числа. Число S
принадлежащее a,
такое что a^s≡b(mod
m)
называется индексом по основанию а.
ind
_ab.

Пр.
Пусть
m=13, a = 2.

2³≡8(mod
13) 2⁴≡16(mod
13), 2⁴≡3(mod
13) ind₂3=4

2⁶≡12(mod
6), ind12=6.

Теорема:
Пусть m
– модуль, g
– первообразный корень по модулю m,
тогда для любого b,
такого что НОД(b,m)=1,
существует такое S,
что g^s
≡b(mod
m)
и все такие индексы S
явл. Неотрицательными числами некоторого
класса по модулю m.

Д-во:
пользуясь теоремой, что g
– первообразный корень g,
g²,…,g^r⁽^m⁾…
все степени различные и образуют
приведенную систему вычетов по модулю
m.

Т.к.
НОД(b,m)=1,
то b
попадет в какой-то класс, значит существует
S
принадлежащий N,
такой что g^s≡b(mod
m).
Возьмем какой-нибудь S₁,
такой что g^S¹
≡ b(mod
m),
g^S
≡ b(mod
m),

Тогда
эти модули сравнимы по модулю порядка
P(g)=

(m).

S
≡ S₁(mod

(m)).

Докажем,
что если взять два вычета из одного
класса они являются индексами

S
≡ k(mod

(m)),
g^S
≡ g^k
(mod
m),
но g≡b(mod
m),
тогда и g^k≡b(mod
m),
значит k
– тоже индекс. k=ind_gb.
Доказанно.

Теорема:
Пусть НОД(b,m)=1
и НОД(с,m)=1
g
первообразный корень по модулю m,
b≡c(mod
m)
<=> ind_gb≡ind_gс(mod

(m)).

Д-во:
необходимость. Пусть b≡c(mod
m).
Теперь

значит ind
_gb
≡ ind
_gb(mod

(m)).

Т.к.
степень сравнения по модулю m,
то показатель сравнения по модулю

(m).

Достаточность:
Пусть ind_gb≡ind_gс(mod

(m)),
тогда имеем

,
т.е. b≡c(mod
m).

Теорема о свойствах индексов и следствие из нее.

Опр.
Пусть m
– модуль, а, в – взаимно простые с
модулем числа. Число S
принадлежащее a,
такое что a^s≡b(mod
m)
называется
индексом по основанию а. ind
_ab.

Свойства
индексирования: 1) Пусть НОД(b,m)=1
и НОД(a,m)=1,
g
– первообразный корень по модулю m,
тогда ind_gab
≡ ind_ga
+

+
ind_gb
(mod

(m)).
Д-во:
g^ind^g^ab
≡
ab(mod
m),
в то же время

ab≡g^ind

g^a
*
g^ind

g^b
= g^ind

g^a+^{ind g}^b(mod
m). теперь

ind_gab
≡ ind_ga
+ ind_gb
(mod

(m)). Д-но.

Пусть
НОД(a,m)=1,
g
– первообразный корень по модулю m,
тогда

Ind_sa^k=k
ind_ga(mod
m). Д-во:
K=0,
ind_ga⁰≡
0

ind_ga(mod
m)

Ind_ga⁰
= Ind_g1=0
левая
часть верно. k=1,
ind_ga¹≡1

ind_ga(mod
m) –
верно.
k>1,
ind_ga^k≡
ind_ga
тогда
по замечанию

ind_ga^k=
_. Д-НО.

Опр.

Пусть

Пусть
НОД(b,m)=1
и НОД(a,m)=1,
g
– первообразный корень по модулю m,
тогда

.

Д-во:

по
предыдущему свойству

Но
по опр.

=
,
т.е.

.
Д-но.

Формула перехода от системы индексов с основанием к системе индексов с основанием (пример 1).

g,
g₁
– первообразные корни по модулю m.

НОД(a,m)=1
a=g^α(mod
m)

a=g₁^α1(mod
m) α =ind_ga
=
ind_gg₁^α1(mod
ᵠ(m))

ind_ga
=
α₁
ind_gg1(mod
ᵠ(m))

ind_ga
=
ind_g1a
ind_gg1(mod
ᵠ(m))

Пример:

ind
₁₀43
=
13 ind ₆43
=
?

Решение:

ind₁₀43
=
ind₆43
* ind₁₀6(mod
58)

13=
ind₆43*57(mod
58) ind ₁₀6=57

ind₆43
= 45 (mod 58)

Таблица
индексов по

.

Опр.
Пусть
m
– модуль, a,b
–взаимно простые с модулем числа. Число
sϵN
такое, что a^s=b(mod
m)
, называется индексом b
по модулю а.

ind_ab

a^indab=b(mod
m)

m=11
ᵠ(m)=10

2⁵=–1(mod
11) или 2⁵=10(mod
11)

2 –
первообразный корень по модулю 11

Р(2)=10,
т.е. 2 – первообразный корень.

Пояснение:

2=2(mod
11)

2³=8(mod
11)

2⁶=9(mod
11)

2⁷=7(mod
11)

2⁸=3(mod
11)

2⁹=6(mod
11)

x	1	2	3	4	5	6	7	8	9	10
ind x (mod 11)	0	1	8	2	4	9	7	3	6	5

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

Источник

Макеты страниц

Индексы по простому модулю.

Пусть g есть первообразный корень по модулю . Тогда числа

образуют приведенную систему вычетов по модулю . Поэтому любое число а, взаимно простое с , сравнимо с одним и только с одним из чисел ряда (1).

Если то k называется индексом числа а по модулю при основании g и обозначается символом а или . Если k — другое число, для которого , то и, согласно предложению Таким образом, множество индексов данного числа а образуют класс вычетов по модулю Из определения индекса вытекает, что из следует

Пример. Пусть Число 2 есть первообразный корень по модулю 13. Индексы чисел при основании таковы:

С помощью этой таблицы по данному числу а находится его индекс по модулю 13. Следующая таблица позволяет по данному индексу находить соответствующее число:

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

ТЕОРЕМА 5.12. Если числа а, b взаимно простые с — любое натуральное число, то

Доказательство. По определению индексов чисел а и b имеем:

отсюда находим произведение

Следовательно, есть один из индексов произведения т. е.

Из сравнения следует, что

поэтому есть один из индексов степени , т. е.

Примеры. 1. Пусть тогда

2. Решить сравнение

Данное сравнение равносильно такому:

Отсюда следует, что

ТЕОРЕМА 5.12. Пусть — мультипликативная группа классов вычетов, взаимно простых с и С есть аддитивная группа классов вычетов по модулю Отображение , ставящее в соответствие каждому элементу а группы элемент а группы С, есть изоформизм группы на группу С.

Доказательство. Согласно определению индекса, соответствие является биективным. Кроме того, сохраняется операция умножения в группе так как из сравнения

следует, что

Следовательно, есть изоморфизм группы на группу С.

В обычной арифметике основой теории логарифмов является изоморфизм мультипликативной группы положительных действительных чисел и аддитивной группы всех действительных чисел. Доказанная теорема, являющаяся основной в теории индексов, объясняет причину сходства теории логарифмов (в обычной арифметике) и теории индексов (по простому модулю).

Источник

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

${displaystyle a^{ell }equiv 1{pmod {m}}.}$

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

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

Свойства[править | править код]

, поэтому можно считать, что показатель задан на классе вычетов по модулю .
. В частности, и , где — функция Кармайкла, а — функция Эйлера.
$a^tequiv a^spmod m Leftrightarrow tequiv spmod{P(a)}.$
; если , то
Если — простое число и , то ${displaystyle a,;ldots ,;a^{k}}$ — все решения сравнения .
Если — простое число, то — образующая группы $mathbb {Z} _{p}$ .
Если — количество классов вычетов с показателем , то ${displaystyle sum limits _{k,mid ,varphi (m)}psi (k)=varphi (m)}$ . А для простых модулей даже .
Если — простое число, то группа вычетов ${mathbb {Z}}_{p}^{{times }}$ циклична и потому, если $a=g^{dk}$ , где — образующая, , а — взаимно просто с , то $P(a)=frac{p-1}{d}$ . В общем случае для произвольного модуля можно вывести аналогичную формулу, пользуясь теоремой о структуре мультипликативной группы вычетов ${mathbb {Z}}_{m}^{{times }}$ .

Пример[править | править код]

Так как $2^4equiv 1pmod{15}$ , но $2^1notequiv 1pmod{15}$ , $2^2notequiv 1pmod{15}$ , $2^3notequiv 1pmod{15}$ , то порядок числа 2 по модулю 15 равен 4.

Вычисление[править | править код]

Если известно разложение модуля на простые множители $p_{j}$ и известно разложение чисел p_j-1 на простые множители, то показатель заданного числа может быть найден за полиномиальное время от ln m . Для вычисления достаточно найти разложение на множители функции Кармайкла и вычислить все ${displaystyle a^{d}mod m}$ для всех . Поскольку число делителей ограничено многочленом от ln m , а возведение в степень по модулю происходит за полиномиальное время, то алгоритм поиска будет полиномиальным.

Приложения[править | править код]

Характеры Дирихле[править | править код]

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

См. также[править | править код]

Дискретное логарифмирование
Функция Кармайкла

Примечания[править | править код]

↑ Бухштаб, 1966, с. 140.
↑ Виноградов, 1972, с. 92.

Литература[править | править код]

Бухштаб А. А. Теория чисел. — М.: Просвещение, 1966.
Виноградов И. М. Основы теории чисел. — М.: Наука, 1972.

Источник

Python задачи

Найти номер минимального по модулю элемента массива. Например, в массиве [20, -3, -5, 2, 5] минимальным по модулю элементом является число 2. По индексу число 2 – третье, тк отсчёт с нуля.Разбор задачи на Python

Что такое модуль числа

Если очень грубо объяснять, то минусы отбрасываются. Например, |-4| = 4, модуль числа минус четыре, равен четырём.

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

Алгоритм поиска индекса минимального по модулю элемента массива

1) Вводим какую-то переменную и присваиваем ей индекс первого элемента массива 0, предполагая, что первый элемент массива и является минимальным по модулю.

2) Начинаем в цикле перебор массива со второго элемента и до конца. При этом в цикле в заголовке условного оператора (if) сравниваем модуль текущего элемента с модулем элемента, чей индекс хранится в переменной первой переменной.

3) Если абсолютное значение текущего элемента массива меньше, чем элемента с индексом, которое записано в нашу переменную, то в теле условного оператора присваиваем новый индекс текущего элемента.

Поиск минимального модуля числа в массиве

from random import random
num = 0
n = 10
list = []
for i in range(n):
list.append(int(random() * 100) – 50)
print(list)

for i in range(1, n):
if abs(list[i]) < abs(list[num]):
num = i
print(num)

Python задачи
Все задачи на python

Репост статьи

2 ноября 2022 г.

Комментарии могут оставлять только зарегестрированные пользователи!

3.2 Индексы

Пусть – группа, – её элемент, $b={a}^{k} in {langle}a{rangle}$ . Число называется дискретным логарифмом элемента по основанию (пишут $k={log }_{a}b$ ). В случае, когда – примитивный корень по модулю , дискретный логарифм ещё называют индексом числа по модулю при основании . Пишут: $k=ind_{a}b$ . Когда примитивный корень фиксирован, можно также писать: k=ind b .

Дискретное логарифмирование в произвольной группе является трудноразрешимой задачей. Приведём один из примеров, когда оно всё-таки легко осуществимо.

Пример 3.7 Вычислить дискретный логарифм числа по основанию по модулю .

Решение. Порядок мультипликативной группы поля вычетов по модулю 102673 равен $102672={2}^{4} cdot {3}^{2} cdot 23 cdot 31$ . Число, являющееся произведением большого количества небольших чисел, называется гладким. Для дискретного логарифмирования в таком поле существует алгоритм Полига-Хэллмана, который мы сейчас применим.

Если – решение нашей задачи, и x_1 , x_2 , x_3 , x_4 – остатки от деления на , , и соответственно, то

$begin{center} begin{tabular}{ll} ${left({5}^{{M}_{1}}right)}^{{x}_{1}}=left({a}^{{M}_{1}}right)~(mod p)$,& ${left({5}^{{M}_{2}}right)}^{{x}_{2}}=left({a}^{{M}_{2}}right)~(mod p)$, \ ${left({5}^{{M}_{3}}right)}^{{x}_{3}}=left({a}^{{M}_{3}}right)~(mod p)$, & ${left({5}^{{M}_{4}}right)}^{{x}_{4}}=left({a}^{{M}_{4}}right)~(mod p)$,\ end{tabular} end{center}$

где

${M}_{1}=frac{p-1}{16},{M}_{2}=frac{p-1}{9},{M}_{3}=frac{p-1}{23},{M}_{4}=frac{p-1}{31}.$

Наоборот, если мы найдём x_1 , x_2 , x_3 и x_4 , а решение задачи всегда существует (так как – примитивный корень), то будет совпадать с единственным решением системы:

$left{begin{array}{l}x'=x_1 ~(mod 16), \ x'=x_2 ~(mod 9), \ x'=x_3 ~(mod 23),\ x'=x_4 ~(mod 31). end{array}right.$

Итак, для решения задачи, по китайской теореме об остатках нужно найти:

$begin{center} begin{tabular}{ll} ${M}_{1}=6417,$& ${widetilde{{M}}}_{1}={M}_{1}^{-1}=1~(mod 16);$ \ ${M}_{2}=11408,$ & ${widetilde{{M}}}_{2}={M}_{2}^{-1}=2~(mod 9);$ \ ${M}_{3}=4464,$ & ${widetilde{{M}}}_{3}={M}_{3}^{-1}=12~(mod 23);$ \ ${M}_{4}=3312,$ & ${widetilde{{M}}}_{4}={M}_{4}^{-1}=6~(mod 31);$ end{tabular} end{center} end{center}$

$x={x}_{1} cdot {M}_{1} cdot {widetilde{{M}}}_{1}+{x}_{2} cdot {M}_{2} cdot {widetilde{{M}}}_{2}+{x}_{3} cdot {M}_{3} cdot {widetilde{{M}}}_{3}+{x}_{4} cdot {M}_{4} cdot {widetilde{{M}}}_{4}=\6417{x}_{1}+22816{x}_{2}+53568{x}_{3}+19872{x}_{4}.$

Следовательно, нам нужно найти x_1 , x_2 , x_3 , x_4 .

Имеем:

$begin{center} begin{tabular}{ll} ${97697}^{{x}_{1}}=55814~(mod p),$ & ${170}^{{x}_{2}}=29684~(mod p),$\ ${24920}^{{x}_{3}}=56216~(mod p),$ & ${64646}^{{x}_{4}}=18591~(mod p).$ end{tabular} end{center}$

Поскольку порядок группы ${langle}{5}^{{M}_{3}}{rangle}$ равен 23, а группы ${langle}{5}^{{M}_{4}}{rangle}$ – всего 31, то при различных x_3 , x_4 величины ${24920}^{{x}_{3}}$ и ${64646}^{{x}_{4}}$ пробегают, соответственно, по 23 и 31 различным значениям.

Тогда x_3 и x_4 можно найти полным перебором, проверив , . В нашем случае ${x}_{3}=14$ , ${x}_{4}=12$ . Числа ${x}_{1}$ и ${x}_{2}$ также можно искать полным перебором, но для них можно ещё уменьшить количество попыток. Будем искать

${x}_{1}={x}_{1,1}+2{x}_{1,2}+4{x}_{1,3}+8{x}_{1,4},$

где ${x}_{1,i} in left{0,1right}.$

Имеем:

${left({97697}^{{x}_{1}}right)}^{8}={left({97697}^{8}~(mod p)right)}^{{x}_{1.1}}={(-1)}^{{x}_{1,1}}={55814}^{8}=(-1)~(mod p).$

То есть $(-1)^{x_{1,1}} = -1$ . Отсюда ${x}_{1,1}=1.$

Далее,

${left({97697}^{{x}_{1}}right)}^{4}={97697}^{4+8{x}_{1,2}}=15467 cdot {(-1)}^{{x}_{1,2}}={55814}^{4}=87206~(mod p).$

Проверим оба варианта $x_{1,2}=0,1$ :

$15467 cdot {(-1)}^{0} neq 87206~(mod p),$

$15467 cdot {(-1)}^{1} = 87206~(mod p).$

Отсюда ${x}_{1,2}=1$ .

Далее,

${left({97697}^{{x}_{1}}right)}^{2}={97697}^{2+4+8{x}_{1,3}}=101570 cdot {left(-1right)}^{{x}_{1,3}}={55814}^{2}=1103~(mod p).$

Опять, из двух вариантов выбираем верный: ${x}_{1,3}=1$ .

Наконец,

${97697}^{1+2+4+8{x}_{1,4}}=46859 cdot {left(-1right)}^{{x}_{1,4}}=55814~(mod p),$

откуда ${x}_{1,4}=1.$ Проверяем:

${97697}^{15}=55814~(mod p)Rightarrow {x}_{1}=15.$

Аналогично находим ${x}_{2}={x}_{2,1}+3{x}_{2,2}=5$ .

По китайской теореме об остатках находим x=69359 .

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

Приведем эти таблицы для примитивного корня 2 по модулю 37:

Индекс по числу

	0	1	2	3
0		24	25	14
1	0	30	22	9
2	1	28	31	5
3	26	11	15	20
4	2	33	29	8
5	23	13	10	19
6	27	4	12	18
7	32	7	6
8	3	17	34
9	16	35	21

Число по индексу

	0	1	2	3
0	1	25	33	11
1	2	13	29	22
2	4	26	21	7
3	8	15	5	14
4	16	30	10	28
5	32	23	20	19
6	27	9	3	1
7	17	18	6
8	34	36	12
9	31	35	24

Например, чтобы определить индекс по числу 13, нужно в первой таблице перейти к столбцу “1” и строке “3”. Итак, ${ind}_{2}13=11$ . Наоборот, для нахождения числа по его индексу 11 нужно во второй таблице перейти в столбец “1” строку “1”. Имеем: ${2}^{11}=13mod37$ .