нахождение порядка по модулю

[Rumato]

Здравствуйте, помогите, пожалуйста, разобраться.

если $x$ и $N$ - взаимно простые числа, причём $x < N$, то порядком $x$ по модулю $N$ называют наименьшее целое положительное число $r$, обладающее свойством $x^r = 1 \mod N$, это как? как вычислить $r$?

Просто в книге, которую читаю это написано как очевидное, а я понять этого не могу

[Sonic86]

Самая простая книжка, где об этом написано - Бухштаб Теория чисел.
Кратко: точно $r$ вычислить сложно. Известно, что для всех $x$ верно $x^{L(n)} \equiv 1 \pmod n$, где $L(n)$ - функция Люка $L(n)$ (другое название - функция Кармайлка), $n=p_1^{a_1}...p_s^{a_s} \Rightarrow L(n) = \text{НОК} (p_1^{a_1-1}(p_1-1),...,p_s^{a_s-1}(p_s-1))$, то есть всегда $r$ делит $L(n)$, разложив $n$ на множители $r$ можно найти небольшим оптимизированным перебором. Для простых $n$ значение функции Люка совпадает со значением функции Эйлера: $n \in P \Rightarrow L(n) = \varphi (n) = n-1$, то есть $x^{n-1} \equiv 1 \pmod n$.
Можете погуглить термины.

-- Сб апр 30, 2011 22:32:14 --

(Оффтоп)

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

[alex1910]

Rumato в сообщении #440400 писал(а):

Здравствуйте, помогите, пожалуйста, разобраться.

если x и N - взаимно простые числа, причём x < N, то порядком x по модулю N называют наименьшее целое положительное число r, обладающее свойством x^r = 1 mod N, это как? как вычислить r?

Просто в книге, которую читаю это написано как очевидное, а я понять этого не могу

Во-первых, условие x<N совершенно несущественно.
Во-вторых, r - делитель количества чисел, меньших N и взаимно-простых с N.

Вычислять можно наивно - проследовательным нахождением степеней mod N (то есть остатков степеней) до тех пор, пока не получится единица.

Можно разложить N на множители и найти порядки по модулю простых делителей (или их степеней) N - и "собрать" из этого результат.

Есть еще куча способов, но полагаю, Вам за глаза хватит наивных.

UPD. Опередили. Постом выше тоже самое, только подробней.

[Rumato]

так немного начинаю понимать(завтра высплюсь почитаю), а вот в вдогонку вопрос в книге было написано, что эта задача сложная для классического компьютера и нет компьютерного алгоритма, реализующего его. Это так? Если да то почему?

Заранее спасибо за помощь

[alex1910]

Rumato в сообщении #440420 писал(а):

так немного начинаю понимать(завтра высплюсь почитаю), а вот в вдогонку вопрос в книге было написано, что эта задача сложная для классического компьютера и нет компьютерного алгоритма, реализующего его. Это так? Если да то почему?

Заранее спасибо за помощь

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

[VAL]

Sonic86 в сообщении #440407 писал(а):

(другое название - функция Кармайлка)
[...]
Можете погуглить термины.

(Оффтоп)

Хотел съязвить, что "функцию Кармайлка" нагуглить вряд ли удастся. Но сначала проверил. Гугл без труда переставил буковки как надо. Так что, все правильно :)

[Rumato]

я не сильно обнаглею, если продолжу: а какие именно алгоритмы есть? просто напишите, пару если не сложно.


Заранее спасибо))

-- Вс май 01, 2011 15:14:21 --

и ещё, я просто, правда пока разобраться не могу $1 mod 11$ - это как считать? приведите, пожалуйста, пример решения

[Sonic86]

Rumato писал(а):

и ещё, я просто, правда пока разобраться не могу $1 mod 11$ - это как считать?

$a \mod b$ - остаток от деления $a$ на $b$.

(Оффтоп)

VAL писал(а):

Хотел съязвить, что "функцию Кармайлка" нагуглить вряд ли удастся. Но сначала проверил. Гугл без труда переставил буковки как надо. Так что, все правильно :)

Опечатался

[Rumato]

Sonic86
это я понимаю, остаток от деления - это число, которое в сумме с произведением неполного частного и делителя даёт делимое, т.е. $ a mod b = q$, которое $a = b*p + q$, $5*1 + 6 = 11$ или же $5*2 + 1 = 11$ и т.д. я правильно понимаю?

но тогда получается, что функция mod не однозначная, Покажите, пожалуйста просто на примере $ 1 mod 11 = ?$, что должно получится?

[Sonic86]

$r = a \mod b \Leftrightarrow a=bq+r, q \in \mathbb{Z}, 0 \leq r < b$. Т.е. Вы ищете $r$ из равенства $1 = 11q+r$. Функция однозначная.

[VAL]

Sonic86 в сообщении #440648 писал(а):

$r = a \mod b \Leftrightarrow a=bq+r, q \in \mathbb{Z}, 0 \leq r < b$. Т.е. Вы ищете $r$ из равенства $1 = 11q+r$. Функция однозначная.

Уважаемый Sonic86! Уверен, что Вы все правильно понимаете. Но не уверен, что все правильно объясняете. Поэтому вмешаюсь.
Различают два понятия:
1. $\mod$ как функцию двух аргументов (ну или бинарную операцию). С оговоркой, что второй аргумент (второй операнд) отличен от 0. То есть, $a \mod b $ - остаток от деления $a$ на $b$. Тогда она, конечно, однозначна.
2. $\mod$ как отношение сравнимости по модулю. Два целых числа сравнимы по модулю $m$, если они имеют одинаковые остатки от деления на $m$. В этом случае никакой однозначности, разумеется, нет.

Путаница заключается в том, что Вы обсуждаете функцию $\mod$, а используете обозначение для отношения.

[Rumato]

в ещё раз вопрос вдогонку: $1(mod N)$ - это получается отношение сравнимости по модулю? а как вычислить? т.е. $a = b(mod N)$, при делении a на N и b на N остатки равны, так? а какая-нибудь формула для вычисления $a = b(mod N)$ есть?

[Sonic86]

VAL, ну да имел ввиду это плохо у меня с объяснялкой. Я только думал, что при обозначении отношения $\mod$ берется в скобки.

Rumato писал(а):

в ещё раз вопрос вдогонку: $1(mod N)$ - это получается отношение сравнимости по модулю? а как вычислить? т.е. $a = b(mod N)$, при делении a на N и b на N остатки равны, так? а какая-нибудь формула для вычисления $a = b(mod N)$ есть?

$1 (\mod N)$ - так вообще не пишут (и $a=b \pmod N$ строго говоря тоже не пишут). Либо $r = a \mod b$ - Maple и в Pascale вроде (ну или $r=mod(a,b)$ - это в SQL например ) - остаток от деления $a$ на $b$ - функция, 2-хместная, $b>0$, либо $a \equiv b \pmod N$ - отношение "$a$ сравнимо с $b$" по модулю $N$ (т.е. когда $\mod$ заключено в скобки и значок $\equiv$ - это отношение, а когда скобок нет и знак $=$, то функция остатка от деления). Вычислить его можно лишь в программистском смысле $a \equiv b \pmod N = true$ или $false$.
Еще $a \equiv b \pmod N \Leftrightarrow a \mod N = b \mod N$. Например $8 \equiv 5 \pmod 3$, поскольку $8-5$ делится на 3, ну или $8 \mod 3 = 5 \mod 3 = 2$.

Открыли бы Бухштаба, да прочли...

[Rumato]

Большое спасибо, Бухштаба обязательно прочту