Теория чисел: сравнение по модулю

[Pigs]

Доброго времени суток!

Помогите пожалуйста разобраться в следующем:

Есть сравнение вида $a^b \equiv x \pmod p$, где $a,b $ - известные числа, $x $ - нужно найти, $p$ - простое число.
В этом случае по свойствам операции модуля неизвестное можно найти так $x = ((a \% p) ^ {b \% (p - 1)}) \% p$, где $a \% b$ взятие остатка от деления(mod) $a$ на $b$.

Вопрос, каким образом найти $x$, если сравнение будет иметь вид:
$a^b \equiv x \pmod {p^c} $, где $ c > 1$?

где $a,b,c $ - большие известные числа, $x $ - неизвестное, $p$ - простое число.

Спасибо заранее.

[nnosipov]

Pigs в сообщении #843324 писал(а):

Вопрос, каким образом найти $x$, если сравнение будет иметь вид:
$a^b \equiv x \pmod {p^c} $, где $ c > 1$?

где $a,b,c $ - большие известные числа, $x $ - неизвестное, $p$ - простое число.

Если $c$ большое, то никаким, поскольку $x$ будет очень большим. Если же $a$, $b$ и $m=p^c$ --- большие, то для быстрого отыскания $a^b \bmod{m}$ используют бинарный алгоритм.

[ИСН]

Сдаётся мне, вопрос хотел быть про другое. Но по сути да: если основание и так большое, то нет особого смысла сокращать $b$, деля его на $p-1$ или что там вместо этого в случае $\mod p^c$.

[Pigs]

nnosipov в сообщении #843401 писал(а):

Pigs в сообщении #843324 писал(а):

Вопрос, каким образом найти $x$, если сравнение будет иметь вид:
$a^b \equiv x \pmod {p^c} $, где $ c > 1$?

где $a,b,c $ - большие известные числа, $x $ - неизвестное, $p$ - простое число.

Если $c$ большое, то никаким, поскольку $x$ будет очень большим. Если же $a$, $b$ и $m=p^c$ --- большие, то для быстрого отыскания $a^b \bmod{m}$ используют бинарный алгоритм.

Бинарный алгоритм можно использовать только после взятия модуля $a \% p, b \% (p-1)$, так как одно умножение $a * a$ уже не приемлемо. И так как модуль $ p^c $ составной, то брать таким образом по модулю $p^c$ нельзя, а следовательно воспользоваться бинарный алгоритмом не получиться.

ИСН в сообщении #843421 писал(а):

Сдаётся мне, вопрос хотел быть про другое. Но по сути да: если основание и так большое, то нет особого смысла сокращать $b$, деля его на $p-1$ или что там вместо этого в случае $\mod p^c$.

Извиняюсь не написал(неправильно написал), известно, что $a^b > p^c$, то есть число $p^c$ не большое (порядка $10^9$), а вот $a,b$ огромные числа, каждое из которых порядка $(10^9)^{(10^9)}$.

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

А так действительно не ясно, однако в книге "Бухштаба - теория чисел", рассмотрен примерно такой случай, там находятся решение сначала для $p$, а потом из найденного решения для $p^1, ... p^c$, и т.д., используются биномиальные коэффициенты и т.п. Но там решается уравнение, а у меня возведение большого числа в большую степень.

Спасибо.

[ИСН]

Pigs в сообщении #843436 писал(а):

Бинарный алгоритм можно использовать только после взятия модуля $a \% p, b \% (p-1)$, так как одно умножение $a * a$ уже не приемлемо. И так как модуль $ p^c $ составной, то

...то надо брать $a\mod p^c,\;b\mod (p-1)p^{c-1}$.

[Pigs]

ИСН в сообщении #843440 писал(а):

Pigs в сообщении #843436 писал(а):

Бинарный алгоритм можно использовать только после взятия модуля $a \% p, b \% (p-1)$, так как одно умножение $a * a$ уже не приемлемо. И так как модуль $ p^c $ составной, то

...то надо брать $a\mod p^c,\;b\mod (p-1)p^{c-1}$.

А что имелось ввиду $p^{c-1} * (b \mod (p - 1))$ или $b \mod ((p - 1)*p^{c-1})$? Попробовал и так и этак, все равно не получилось буду искать ошибку в расчетах.

[Pigs]

Pigs в сообщении #843452 писал(а):

ИСН в сообщении #843440 писал(а):

Pigs в сообщении #843436 писал(а):

Бинарный алгоритм можно использовать только после взятия модуля $a \% p, b \% (p-1)$, так как одно умножение $a * a$ уже не приемлемо. И так как модуль $ p^c $ составной, то

...то надо брать $a\mod p^c,\;b\mod (p-1)p^{c-1}$.

А что имелось ввиду $p^{c-1} * (b \mod (p - 1))$ или $b \mod ((p - 1)*p^{c-1})$? Попробовал и так и этак, все равно не получилось буду искать ошибку в расчетах.

Спасибо, нашел ошибку, правильно будет $b \mod ((p - 1)*p^{c-1})$.

Если не сложно, можете подсказать что почитать, или где почитать доказательство, из чего это следует?

[ИСН]

Из $a^{\varphi(m)} \equiv 1 \pmod m$

-- менее минуты назад --

https://ru.wikipedia.org/wiki/%D0%A2%D0 ... 5%D0%BB%29

[Pigs]

ИСН в сообщении #843516 писал(а):

Из $a^{\varphi(m)} \equiv 1 \pmod m$

-- менее минуты назад --

https://ru.wikipedia.org/wiki/%D0%A2%D0 ... 5%D0%BB%29

Читал это, спасибо.

Еще не большое вопрос, если модуль такой
$a^b \mod (p^c \cdot q^d)$
$q$ - тоже простое.

То так будет ведь неправильно:
$b \mod ((p - 1) \cdot p^{(c-1)} (q - 1) \cdot q^{(d - 1)})$
А как правильно?

[Sonic86]

Pigs в сообщении #843528 писал(а):

То так будет ведь неправильно:
$b \mod ((p - 1) \cdot p^{(c-1)} (q - 1) \cdot q^{(d - 1)})$
А как правильно?

$b \mod ((p - 1) \cdot p^{(c-1)} (q - 1) \cdot q^{(d - 1)})$ - Это не утверждение, это терм, пишите вменяемо, пожалуйста.
Верно, что если $a$ взаимно просто с $m=p^cq^d$, то $a^{(p - 1) p^{(c-1)} (q - 1) q^{(d - 1)}}\equiv 1 \pmod m$. Верно даже и то, что для любого $a$ $a^{\text{НОК}((p - 1) p^{(c-1)} ;(q - 1) q^{(d - 1)})}\equiv 1 \pmod m$.

[Pigs]

Спасибо всем.
Вывод:
$a^b \equiv ((a \mod m) ^ {b \mod \varphi (m) }) \mod m \pmod m$ ?

[ИСН]

У Вас слово mod применено в двух разных смыслах, от этого создаётся впечатление, как от фразы "Косил косой косой косой", а так-то всё верно.

[Pigs]

ИСН в сообщении #843597 писал(а):

У Вас слово mod применено в двух разных смыслах, от этого создаётся впечатление, как от фразы "Косил косой косой косой", а так-то всё верно.

$4^4 \mod 4 = 256 \mod 4 = 0$

$4^4 \mod 4 = ((4 \mod 4)^{(4 \mod 2)}) \mod 4 = (0 ^ 0) \mod 4 = 1 $
Что не так?

[ИСН]

Цитата:

Если a и m взаимно просты

[Pigs]

ИСН в сообщении #843610 писал(а):

Цитата:

Если a и m взаимно просты

Тогда если они не взаимно просты, то ответ 0 если $a^b \leqslant m$, иначе ответ $a^b$.


Косил косой косой, косой куст!