On crt based factorization?
It is bothering my why I have never read ideas on this, not a single word. Eventhough it may be due to my unknowledge on this subject. If I am wasting time of forum goers, please forgive me.
Any odd integer x in can be presented in the form x = a^2  b^2. Being so, there must be quadratic residues d and e modulo n, a = d  e, where a is remainder of x modulo n ,and n arbitrary integer number.
There are various, and really various, numbers n and residues, where this condition is meat only once. Solution in unique.
For example, if number to be factorized is of the form 8n+1, then a must be of form 8n+1 and b of the form 8n. Like numbers 3*11 = 7^28^2 are.
How fast can factorization be, using these facts and chinese remainder theorem?
If the amount of these solutions is small and modulo is large, a large amount of factors is outsieved. Could this be useful?
