Principal Square Roots Mod

Question

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?

Answer 1

Note that your formula can be invalid even for primes. The principle square root $x$ of $y$ modulo a prime $p$ is given by the formula $x=y^{(p+1)/4}\bmod p\;$ if y is a quadratic residue (see the cases below).

Part a) 

For $m=98\dots 101\,$ either $x_p\equiv +m \pmod {67}\,$ or $x_p\equiv -m \pmod {67}\,$ are the principal roots of $m^2 \pmod {67},\,$ and analogous for $127$. Check this e.g. with the Jacobi symbol, here for $98$:

$$\left(\frac{98}{67}\right)=-1, \;\left(\frac{-98}{67}\right)=1.$$ If you have the principal roots $x_p, x_q$ then using the two-equation form of the CRT the principal root $\pmod{8509}$ is $$x \equiv 127 x_p \left(127^{-1} \pmod {67}\right) + 67x_q \left(67^{-1} \pmod {127}\right) \pmod {8509}$$ $$x \equiv 127 \times 19 \times x_p + 67 \times 91 \times x_q \pmod {8509}$$

$$x \equiv 2413 x_p + 6097 x_q \pmod {8509}$$ Now for your cases $m=98:$ $$x_p\equiv 36\equiv -98 \pmod {67}$$ $$x_q\equiv 98 \pmod {127}$$ $$x\equiv 3654 \pmod {8509}$$

Case $m=99:$ $$x_p\equiv 35\equiv -99 \pmod {67}$$ $$x_q\equiv 99 \pmod {127}$$ $$x\equiv 7338 \pmod {8509}$$

Case $m=100:$ $$x_p\equiv 33\equiv 100 \pmod {67}$$ $$x_q\equiv 100 \pmod {127}$$ $$x\equiv 100 \pmod {8509}$$

Case $m=101:$ $$x_p\equiv 33\equiv -101 \pmod {67}$$ $$x_q\equiv 26\equiv -101 \pmod {127}$$ $$x\equiv 8408 \pmod {8509}$$

Part b) 

In cases $m=98,99\,$ we have the following $\gcd$ values, giving the factorization of $8509$ $$\gcd(3654+98,8509) = 67, \; \gcd(3654-98,8509) = 127$$ $$\gcd(7338+99,8509) = 67, \; \gcd(7338-99,8509) = 127$$

In the other cases the $\gcd$ are trivial ($1\,$ or $8509\,$) and give no factorization information.

Answer 2

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;
}