Somebody asked me a question, I have no idea about it, the question is:
If a positive integer $n\equiv 1\pmod 4$ is the product of two primes, (denotes $n=pq,$ such as a RSA number) but we don't know what $p,q$ is, can we find whether $p,q\equiv 1\pmod 4$ or $p,q\equiv -1\pmod 4$ quickly?
Edit: To make this problem clearer, I'd like to illustrate this with an example:
Given $n=54106525115786488721104110650095154684919808365060517563123199931159\\ 571762703975072565387621847347234678280888429084887681391085492532589162\\ 3649321540843857479706239369353295580392388377=pq,$
Can you find $p\pmod 4$ and $q\pmod 4$ in less than one hour by computer?
$p,q\equiv 1\pmod 4$ if and only if the congruency $x^2\equiv -1\pmod{pq}, x\in\mathbb Z$ is solvable.
Because of the first supplement to quadratic reciprocity, this holds true for the congruencies $$x_1^2\equiv -1\pmod p\\x_2^2\equiv -1\pmod q$$ separately. Since $x_1$ and $x_2$ are only defined up to a multiple of p and q respectively, a simultaneous solution is possible whenever both congruencies are solvable (by the chinese remainder theorem).