Fuller explanation:

When you have powers of an integer modulo a certain other integer, those powers always go in a cycle. For example, let n = 3,p = 10, and the notation (3,k,10) = 3 ^ k mod 10.

(3,1,10) = 3

(3,2,10) = [(3,1,10) * 3] mod 10 = (3*3) mod 10 = 9

(3,3,10) = [(3,2,10) * 3] mod 10 = (9*3) mod 10 = 7

(3,4,10) = [(3,3,10) * 3] mod 10 = (7*3) mod 10 = 1

(3,5,10) = [(3,4,10) * 3] mod 10 = (1*3) mod 10 = 3

(3,6,10) = [(3,5,10) * 3] mod 10 = (3*3) mod 10 = 9

(3,7,10) = [(3,6,10) * 3] mod 10 = (9*3) mod 10 = 7

(3,8,10) = [(3,7,10) * 3] mod 10 = (7*3) mod 10 = 1

And so on.

It so turns out that for prime numbers the cycle length has to be a factor of p-1, so n^(p-1) mod p = 1, although it can also equal 1 at one or more intermediate points. You can find proofs of this here:

http://en.wikipedia.org/wiki/Proofs_of_Fermat's_little_theorem#Necklaces.

For example, for n = 3, p = 11, the cycle looks like this:

3,9,5,4,1,3,9,5,4,1,3...

Notice how 3^10 mod 11 = 1, although 3^5 mod 11 also = 1. For n = 6, p = 11, the cycle goes:

6,3,7,9,10,5,8,4,2,1,6...

The criterion for a number to cycle in (p-1)/2 steps rather than (p-1) is that the number has to be a

*quadratic residue*, meaning that it has to be a square of another number modulo p. For p=11, for example, 3 = 6^2 mod 11 (since 6^2 = 36, and the nearest multiple of 11 below 36 is 33). The reason why this is the case is simple: if n is a quadratic residue, it can be represented as k^2 mod p. Since k has to cycle every p-1 steps and each step of n corresponds to 2 steps of k, n can cover the cycle in (p-1)/2 steps.

Now, on to the main problem.

We are trying to find the square root of n mod p. What this means is that we want to find some number k such that k^2 mod p = n. However, we know that this k exists, so n must be a quadratic residue. This means that the cycle length of n is (p-1)/2, meaning that:

n ^ [(p-1)/2] mod p = 1

n ^ [(p-1)/2 + 1] mod p = n

n ^ [(p+1)/2] mod p = n

If (p+1)/2 is itself an even number, then we can go exactly (p+1)/4 steps to get k. Now, what is the value of k^2 mod p?

k^2 mod p = {n ^ [(p+1)/4] } ^ 2 mod p = {n ^ [(p+1)/2] } mod p = n

And there you have it, you've found a value k that satisfies the condition that makes it a square root of n. The only condition for this algorithm is that (p+1) / 2 is even, ie. p+1 is a multiple of 4, or p mod 4 = 3.