Where to look for a prime factor?
Factoring is a Holy Grail of Math and modern cryptography. There are many newbies and pros likes to play around it. If you are one of them then you probably may be interested in the following fact.
Let N is a composite number and N = pq, where p and q are primes and p < q. Assume S = ÖN. In this case ÖS < p < (N mod S). You may consider it as a theorem but I’m not going to give any proves here. You may accept it as a way to reduce a set of trial candidates or simply flag it. It is your call.
NB: The low boundary is actually valid only if a distance between p and q is not so big (a difference on a digit number order is one or two digits). Otherwise boundaries are shifted to 2 < p < ÖS. Unless distance between p and q is small - in this case boundaries are (N mod S) < p < S. Yep, nobody promised it will be easy.
Subscribe to RSS feed