Assume p and q are approximately of the same size, argue for or against if its easy to solve RSA-problem using Pollard's p-1 factorization method

36 Views Asked by At

Assignment: Assume $p$ and $q$ are approximately of the same size (p 1000 digits and q 1001 digits), argue for or against if its easy to solve RSA-problem using Pollard's $p-1$ factorization method

Against: First we note that if $p$ and $q$ is of approximately the same size, we have chosen them in the most secure way, since its not easier to find either of them. And note that the larger the number the higher the probability is that the number is not a factor of small primes, so since $p$ and $q$ are as large as they are, we may not be able to use Pollar's $p-1$ fac. method.

For: Pollard's $p-1$ method works fast and good if $p-1$ or $q-1$ is a product of small primes. So IF $p-1$ OR $q-1$ are a product of small primes then its easy to solve the RSA-problem using this method. This is because: Assume $p-1$ is a product of small primes. Then $p-1|n!$ for not a too large n. Then its high probability that $p|a^{n!}-1$, since $a^{n!}=a^{(p-1)k}=1$ mod $p$. This also means that $q\not | a^{n!}-1$. So for most choices of a we get a factor of N: $p=$gcd$(a^{n!}-1,N)$.

Is this a true argument? Or have I missed something?