I am trying to find one of the quad roots of 1 mod pq while knowing one of the square roots of -1 mod pq for a 1 mod 4 semiprime.
Now quad1 + quad2 == square root of -1 plus or minus 1
When I solve for this equation:
Solve[a + b == 567 && c + d == 569 && a c == -1 && b d == -1 &&
a d == -b c, {a, b, c, d}, Modulus -> 89 29]
I get
{{a -> 568, b -> 2580, c -> 568, d -> 1}, {a -> 800, b -> 2348,
c -> 713, d -> 2437}, {a -> 2348, b -> 800, c -> 2437,
d -> 713}, {a -> 2580, b -> 568, c -> 1, d -> 568}}
One of these four answers is the correct one. Now I know that the Mathematica Solve command always factors the modulus first.
When I put much larger numbers in this equation it takes a long time to factor the p*q but then immediately comes up with the answer
When I use one of the large primes (like 150 bits) in, it instantly comes up with the answer.
Is there anything about this Solve equation given above that requires a prime to be the modulus. It doesn't look like there is a need
for factoring the modulus. There is no square in the equation so no prime modulus is needed.
The whole aim is to factor the modulus with knowledge of one square root of -1 alone (the modular imaginary number if you may).
