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

Large Numbers Modulo a Non-Prime
Автор n0tred, история, 5 лет назад, По-английски

How to efficiently calculate the value of $$$ \frac{3^{n}-1}{2} $$$ modulo an even number $$$ p $$$, when the bound on $$$ n $$$ is up to $$$ 10^{18} $$$ and $$$ p $$$ is up to $$$ 10^9 $$$?

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

»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится -12 Проголосовать: не нравится

If

$$$n$$$

is odd,

$$$\dfrac{3^n-1}{2} mod \: 2^k $$$

is odd, else it is even.

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

If $$$ka = kb \text{ (mod } km)$$$, then $$$a = b \text{ (mod } m)$$$.

Thus, you can compute $$$x \text{ (mod } 2p)$$$ and then divide by 2 to get $$$x/2 \text{ (mod } p)$$$ (in this example, $$$x = 3^n-1$$$).

→ Ответить