Блог пользователя liveoverflow

Number of solutions for the given condition
Автор liveoverflow, история, 5 лет назад, По-английски

Given $$$X,p,a,b$$$, we need to find out how many $$$n\in\mathbb N,\;(1\leqslant n\leqslant X)\;$$$ satisfy the following condition:

>

$$$na^n\equiv b\pmod{p}$$$

Constraints:

$$$\begin{aligned}\begin{equation}2\leqslant p\leqslant 10^6\\1\leqslant a,b\lt p\\1\leqslant X\leqslant 10^{12}\end{equation}\end{aligned}$$$

I have no idea how to solve this question, any approach or proof will be highly appreciated.

Thank you in advance!

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Only $$$X$$$ is given? What about $$$a$$$ and $$$b$$$ and $$$p$$$? They can be anything?

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It seems related to the discrete logarithm, so start by reading about it.

https://en.wikipedia.org/wiki/Discrete_logarithm

→ Ответить