Principal Square Roots Mod Suppose you know the factorization $8509 = 67\times127$.
(a) Use this to compute the principal square roots of $98^2$, $99^2$, $100^2$, and
$101^2$, modulo $8509$.
I thought that I find the principal square roots in this way:
$(98^2)^{(8509+1)/4} \mod 8509$
I guess I don't understand how knowing the factorization help me compute the principal square roots?
(b) In which of the above cases would knowing the principal square root
together with the given square root allow one to factor $8509$ easily?
 A: Not a direct answer to your question, but here is a C++ program that might be of help:
#include <iostream>
using namespace std;

int GCD(int a,int b) // assuming a >= b >= 1
{
    int c = a%b;
    if (c == 0)
        return b;
    return GCD(b,c);
}

int PowMod(int x,int e,int n)
{
    int y = 1;
    while (e > 0)
    {
        if (e & 1)
            y = (y*x)%n;
        x = (x*x)%n;
        e >>= 1;
    }
    return y;
}

bool InQR(int y,int p)
{
    return PowMod(y,(p-1)/2,p) == 1;
}

bool InQR(int y,int p,int q)
{
    return InQR(y,p) && InQR(y,q);
}

int Inverse(int n,int a)
{
    int x1 = 1;
    int x2 = 0;
    int y1 = 0;
    int y2 = 1;
    int r1 = n;
    int r2 = a;

    while (r2 != 0)
    {
        int r3 = r1%r2;
        int q3 = r1/r2;
        int x3 = x1-q3*x2;
        int y3 = y1-q3*y2;

        x1 = x2;
        x2 = x3;
        y1 = y2;
        y2 = y3;
        r1 = r2;
        r2 = r3;
    }

    return y1>0? y1:y1+n;
}

int Map(int u,int v,int p,int q)
{
    int a = q*Inverse(p,q);
    int b = p*Inverse(q,p);
    return (u*a+v*b)%(p*q);
}

void CalcRoots(int p,int q,int y)
{
    if (GCD(p*q,y) == 1 && InQR(y,p,q))
    {
        int yp = PowMod(y,(p+1)/4,p);
        int yq = PowMod(y,(q+1)/4,q);
        int r1 = Map(0+yp,0+yq,p,q);
        int r2 = Map(0+yp,q-yq,p,q);
        int r3 = Map(p-yp,0+yq,p,q);
        int r4 = Map(p-yp,q-yq,p,q);
        cout << r1 << ',' << r2 << ',' << r3 << ',' << r4 << endl;
    }
    else
    {
        cout << "Invalid Value" << endl;
    }
}

int main()
{
    CalcRoots(67,127,98*98);   // the output is 3654,8411,98,4855
    CalcRoots(67,127,99*99);   // the output is 7338,8410,99,1171
    CalcRoots(67,127,100*100); // the output is 100,5996,2513,8409
    CalcRoots(67,127,101*101); // the output is 8408,6197,2312,101
    return 0;
}

