On Sun, Jun 07, 2009 at 05:41:00PM -0700, Greg Perry wrote: > The significance of this method is the ability to determine any > properties of p and q from a simple operation to n.
To be blunt, I see no significance of any kind... You have observed that unless N is divisible by 3, p and q are both also not divisible by 3. This is not new, and does not speed up factorization in any significant way (yes, you can skip candidate factors that are divisible by 3, but this is not new, and only speeds up the really slow naive algorithms like trial division). You have also observed that: N = p*q => for all moduli m, N = p * q (mod m) this too is not new, and does not speed up factorization. One does not search for both p and q simultaneously, finding the smaller of the two is sufficient, and with q not in the picture the "p" candidates are not constrained in any way by this relation: any prime < N has an inverse mod m, provided p does not divide "m". So for every prime candidate ( that is not a factor of "m") the equation N = p * q (mod m) has a solution. > n is a black box with p and q irretrievably discarded after key > materials are created, are you aware of any process other than this > method that can determine with any level of accuracy properties of p > and q from n? Certainly C.F. Gauss was aware of interesting properties of this type. In Section VI, Articles 329-334 of "Disquisitiones Arithmeticae", he showed a sieve for prime factors of composite numbers based on quadratic reciprocity. This sieve was useful (no computers in ~1800) for numbers difficult to factor by hand without effective short-cuts, 7-10 digit numbers with 3-5 digit prime factors. Gauss had tables of residues that made it possible to quickly read off primes that simultaneously satisfied all the residue constraints. -- Viktor. --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com