Shanks-Tonelli Algorithm in C#

The implementation below uses Visual Studio 2010.  The following references were useful in this implementation.  You will need the BigInteger Library for the computations.

http://www.codeproject.com/KB/cs/biginteger.aspx

Other Sites that are helpful:

http://www.math.vt.edu/people/ezbrown/doc/sqrts.pdf


http://eli.thegreenplace.net/2009/03/07/computing-modular-square-roots-in-python/

http://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm

class ShanksTonelli
    {

        static BigInteger FindS(BigInteger p)
        {
            BigInteger s, e;
            s = p - 1;
            e = 0;
            while (s % 2 == 0)
            {
                s /= 2;
                e += 1;
            }

            return s;
        }

        static BigInteger findE(BigInteger p)
        {
            BigInteger s, e;
            s = p - 1;
            e = 0;
            while (s % 2 == 0)
            {
                s /= 2;
                e += 1;
            }

            return e;
        }


        static BigInteger Ord(BigInteger b, BigInteger p)
        {
            BigInteger m = 1;
            BigInteger e = 0;
            while (b.modPow(m, p) != 1)
            {
                m *= 2;
                e++;
            }

            return e;
        }

        static BigInteger TwoExp(BigInteger e)
        {
            BigInteger a = 1;

            while (e > 0)
            {
                a *= 2;
                e--;
            }

            return a;
        }


        static BigInteger ShanksSqrt(BigInteger a, BigInteger p)
        {

            if (a.modPow((p - 1) / 2, p) == (p - 1))
            {
                return -1;

            }//No Sqrt Exists
            
            if (p % 4 == 3)
            {
             return a.modPow((p + 1) / 4, p);
            }

            //Initialize 
            BigInteger s, e;
            s = FindS(p);
            e = findE(p);

            BigInteger n, m, x, b, g, r;
            n = 2;
            while (n.modPow((p - 1) / 2, p) == 1)
            {
                n++;
            }//Finds Generator

            x = a.modPow((s + 1) / 2, p);
            b = a.modPow(s, p);
            g = n.modPow(s, p);
            r = e;
            m = Ord(b, p);
            if (m == 0)
            {
                return x;
            }
            
            //For Debugging
            //Console.WriteLine("{0}, {1}, {2}, {3}, {4}",m, x, b, g, r);
            while (m > 0)
            {
                
                x = (x * g.modPow(TwoExp(r - m - 1), p)) % p;
                b = (b * g.modPow(TwoExp(r - m), p)) % p;
                g = g.modPow(TwoExp(r - m), p);
                r = m;
                m = Ord(b, p);
                //For Debugging
                //Console.WriteLine("{0}, {1}, {2}, {3}, {4}", m, x, b, g, r);
                

            }

            return x;


        }

        static void Main(string[] args)
        {

            BigInteger p, a, b;
            p = new BigInteger("360027784083079948259017962255826129", 10); Large P

            a = 2;
            Console.WriteLine(ShanksSqrt(a, p));
            Console.ReadLine();


        }
    }