20140404, 19:20  #1 
Apr 2014
1_{16} Posts 
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? 
20140404, 20:19  #2  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}·3·311 Posts 
Quote:
Factoring x by difference of squares with exclusion moduli (which is what you are discussing, if in a confused way) is strictly an exponential time algorithm. > worthless for numbers of any moderate (e.g. 25+ digits) size. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Primality test based on factorization of n^2+n+1  carpetpool  Miscellaneous Math  5  20180205 05:20 
Calculating E based on B1  c10ck3r  Math  1  20120222 06:29 
Is based 10 used for calculations?  Googol  Information & Answers  2  20070727 03:09 
DWTbased calendar  ewmayer  Puzzles  7  20070419 22:33 
Prime95 on NTbased OS  ThomRuley  Software  2  20040321 15:30 