notred's blog

By notred, history, 15 months 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

»
15 months ago, # |
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.

»
15 months ago, # |
  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$$$).