Is $2^n \mod m \equiv (2^{n/2} \pmod m ) ^ 2 \pmod m$?

Question

I'm trying to write a procedure that solves (2^n - 1) mod 1000000007 for a given n.

n can be very large (~10^9).

Say m = 1000000007

So this is what I have so far:

func(n):
  if n = 1 return 2
  if n is even return ((func(n/2) mod m)^2)mod m
  else return ((func(n/2) mod m)^2 * 2)mod m

I'll call func and subtract 1 from the result to get the final answer.

Is it right to use that recursion?

Answer 1

If you are asking whether $(2^{n/2})^2 \equiv 2^n \pmod{m}$ then the answer is yes, since they are already equal as integers, so they will be equal after you pass to the residue classes. There is no need to drag the symbol "mod" along everywhere in your title. Just put it at the end of the congruence.

By the way, the multiplicative order of $2$ in $\mathbb{Z}/1000000007\mathbb{Z}$ is $500000003$. So let $r$ be the remainder after division of $n$ by $500000003$, and we'll have $2^n \equiv 2^r \pmod{1000000007}$. That is probably the most efficient way to it.

Answer 2

I've done it in lisp, but it could easily be done in a conventional language.

(defun mod97 (x)
       (mod x 1000000007))

(defun simple (exxp)
    "Do (2^exp) mod 1000000007 
     as if you didn't have to worry about overflow and such."
    (mod97 (expt 2 exxp)))

(defun 2expmod (exxp)
    "do (2^exxp) mod 1000000007 even if it would normally overflow"
    (cond
        ((< exxp 10)   ; is exponent small enough to not worry about overflow
         (simple exxp))
        ((evenp exxp)  ; break the 2^(2n) into (2^n)^2
         (mod97 (expt (2expmod (/ exxp 2)) 2)))
        (t             ; otherwise break 2^(2n+1) into 2*2^(2n)
         (mod97 (* 2 (2expmod (1- exxp)))))))