Ooh, I do so love a number theory puzzle. I think it's the correct answer but there are gaps in my proof that I'm working on fixing.

We want the smallest prime p such that 252^128 = -1 mod p.

Since we're always going to work mod some prime p, by Fermat's Little Theorem a^{p-1} = 1 mod p. In particular, this gives that for any k such that a^k = 1 mod p, k must be a factor of p-1. I'm sure there's a way to prove this without too much machinery, but I'll just cite Lagrange's Theorem and move on.

We know a^n is periodic in mod p. First, we need to show a^n = -1 for some n mod p. Here's the hole: not sure how you do this.

Let k be the period, meaning the smallest positive exponent where a^k = 1. Let k' be the power such that a^k' = -1, where k' < k. Then since a^{2k'} = (-1)^2 = 1, we must have k' = k / 2. Quick proof: if k' < k/2, then 2k' < k and k cannot be the period since a^{2k'} = a^0 = 1, a contradiction. If k' > k/2, then a^{2k' - k} = 1 as well, and 2k' - k < k, also a contradiction. Therefore, we must have k' = k / 2.

So, in particular, this gives that the powers such that a^n = -1 mod p are k/2, 3k/2, 5k/2, 7k/2, ... or equivalently some odd multiple of k'. But 128 is a power of 2. Therefore, we must have k' = 128 => k = 256. So, 256 is a factor of p-1. Luckily, it turns out 257 is prime, so the answer is 257.

Edit: Have verified with computer my answer is correct. Working on the hole-filling now.

Edit 2: Some general cleaning up.