On Sun, Aug 02, 2015 at 08:31:19AM -0700, Mehdi Sotoodeh wrote: > This characteristic is not limited to common factors of p-1 and q-1. For > every factor of (p-1) (and similarly for q-1) there exists a k where p*q+k > having same factor. In this case p-1 and q+k are sharing the same factor: > p*q+k = (p-1)(q-1) + (p-1) + (q+k). Based on this GCD(n+x,n+y) for a range > of x and y's can reveal some factors of (p-1)(q-1).
For what it's worth, a common factor of (p-1) and (q-1), when it exists, in principle gets you twice as much information a common factor of either alone. It remains unclear whether such information is practically useful, and how you'd know you actually have it. Of course computing GCDs is much faster than factoring, but what sort of false positive rate should one expect? For (x,y) << n, how often will g=GCD(n + x, n + y) yield numbers that have nothing in common with either (p-1) or (q-1)? Any such g divides (x-y), and assuming wlog that r = x - y > 0, we can restate this as r | (n + x). Clearly for every r there is an x < r, such that r | (n + x). So there's no need to "search" for such pairs, just: Let r = some positive integer >= 2, with n mod r != 0. Let j,k = some non-negative integers. Let r' = r - (n mod r) Let y = r' + kr and x = y + jr. Then r | GCD(n+x, n+y). So every number will be a false positive, and no GCDs need to be computed at all. And of course this approach is rather impractical for finding large common factors, where-as, ECM might hypothetically find some large factor of (n-1) that (expontially rarely) just happens to be a factor of (p-1) and (q-1). It is not clear that finding modestly sized factors is particularly useful. -- Viktor. _______________________________________________ openssl-dev mailing list To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev