[openssl-dev] common factors in (p-1) and (q-1)

[Viktor Dukhovni]

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.