Most efficient way to square modulo a Mersenne prime

Question

I realise this question is somewhere in between Math StackExchange and StackOverflow. So forgive me if this is too much of a practical question, it would probably too theoretical elsewhere.

I am looking for the quickest way to compute the square of a number, modulo a medium-sized Mersenne prime. More specifically, let $P = 2^p - 1$ be a Mersenne prime. For the sake of argument, we can set, e.g., $p = 521$. Let $x$ be an arbitrary number between $1$ and $P$. I want to compute $x^2 \bmod P$.

I need to do this using only 32-bit integers. So, $x$ could for example be encoded in an array of $17$ 32-bit integers, and I'd need another array as output.

How would I go about doing this? I know I could use, e.g., FFT, but for not-that-big numbers it feels like an overkill maybe? I'm thinking Karatsuba, but I'm wondering whether there are shortcuts that either leverage the Mersenne modulo or the fact that it's a square I'm doing, and not a generic multiplication?

Answer 1

Here are a few things :

1. $(n+1)k+r\equiv k+r\pmod n$ so we can take all bits above the $p$-th bit and shift them down by $p$ bits and add them, then repeat until we only have p bits to modularly reduce.
2. $m=2^i+2^j+2^l+\cdots\implies m^2= m2^i+m2^j+m2^l+\cdots$ so we can shift the value of $m$ to every bit that's 1 and sum those to square. shifting each to modularly reduce like in the first thing from the ( p-th bit of the sum).