n0tred's blog

Large Numbers Modulo a Non-Prime
By n0tred, history, 7 years ago, In English

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 $$$?

  • Vote: I like it
  • -21
  • Vote: I do not like it

»
7 years ago, hide # |
← Rev. 2  
Vote: I like it -12 Vote: I do not like it

If

$$$n$$$

is odd,

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

is odd, else it is even.

→ Reply
»
7 years ago, hide # |
 
Vote: I like it -7 Vote: I do not like it

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$$$).

→ Reply