Solve an equation for a p*q modulus without factoring the modulus

Questions
1

How to solve an equation for a p*q modulus without factoring the modulus?

2

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 quad_1 + quad_2 == 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).

3

568 and 945 are the two square roots of -1 mod 89*29

4

I am trying to find an option in the Solve command that so that the Solve command does not factor the modulus first, but tries to solve the equation without factoring the modulus

5

Not possible so far as I am aware. With that composite modulus Solve needs to compute a Groebner basis over the integers.

polys = {a + b - 567, c + d - 569, a c + 1, b d + 1, a d + b c, 89*29};
GroebnerBasis[polys, {a, b, c, d}, CoefficientDomain -> Integers]

(* Out[572]= {2581, 568 - 569 d + d^2, -569 + c + d, -567 + b + 568 d,  a - 568 d} *)

Now we have a quadratic equation, in the variable d. Solving that requires first solving modulo the factors of the modulus (followed by CRA to reconstruct the full solutions), ergo the factorization must happen. The fact that there are four solutions, rather than 2, is a strong hint that this needs to happen.

6

thanks, I noticed after I posted that solutions in either prime as modulus always have 1 as one of the variables, which simplifies the equation tremendously,

Once again, thanks for replying