### notred's blog

By notred, history, 15 months ago,

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

 » 15 months ago, # | ← Rev. 2 →   -12 If $n$is odd, $\dfrac{3^n-1}{2} mod \: 2^k$is odd, else it is even.
 » 15 months ago, # |   -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$).
•  » » 15 months ago, # ^ |   0 Thanks