1
$\begingroup$

In Pollard's p-1 algorithm for factoring N, you try to find a L such that p - 1 divides L. Then you check $gcd(pow(a,L,N)- 1, N)$. If 1 < gcd < N, then you have found one of the factors.

I have seen 2 methods to do this.

  1. For n from 1 to Bound, try $L = n!$ (i.e. factorial(n)) & try the $gcd(pow(a,L,N)- 1, N)$ for each one.
  2. for n from 1 to Bound, try $L = LCM(range(1,n))$ & try the $gcd(pow(a,L,N)- 1, N)$ for each one.

In either method, once you hit the Bound unsuccessfully without finding a factor, you redo the loop with a new $a$

I have a few questions

  1. How do you choose the Bound for each of the 2 methods? You are trying to check if the factor is Bound-Powersmooth, but how do you arrive at what Bound you want to check - i.e. what powersmoothness you expect?
  2. In both the methods, how do choose the $a$'s?
  3. In both the methods, how many such $a$'s do you try before giving up (because p - 1 probably doesn't have any small factors)?
$\endgroup$
-1
$\begingroup$

Pollard's p-1 is useful only when for one of the primes p, p-1 is smooth. If you have some random integer you want to factor, you would use ECM and GNFS. Which means, if you are trying p-1, you have a reason to suspect that p-1 is reasonably smooth and then you should already have an idea of how smooth it can be (the smoothness bound L). In any case, the more you try - the more chances to break you have, so you should set as large bound as you can afford to wait, but only if you have reasons to suspect p-1 to be smooth.

I believe choosing $a$ does not matter much, and changing $a$ is not useful at all, until you get a non-trivial $gcd$. The idea is that for new $a$ you have to multiply by all those $1,2,3,...$ again, while you've already done this work for previous $a$. You might get a new $a$ such that some large factor $d$ of $p-1$ is already removed, and then you need a smaller bound $L$ to work, but the chance of that is $1/d$ and you rather keep raising your original $a$ to next powers and reach power $d$ naturally.

The only issue that can occur - is that you will arrive at 1 mod $p$ and 1 mod $q$ simultaneously (i.e. get $a^L\equiv 1 \mod{n}$), which does not leak a factor. Then you try another $a$, but at least you learn that Pollard's $p-1$ is likely to work well on this number.

$\endgroup$
5
  • $\begingroup$ How does one suspect that p-1 is smooth? Is there any algorithm which tells if one of the factors of N may be smooth & also what is the smoothness bound? $\endgroup$
    – user93353
    Jul 12 at 11:44
  • $\begingroup$ As far as $a$ goes, I think it's not guaranteed that every a would work, so if one $a$ fails, you move on to the next one. Or is this not right? $\endgroup$
    – user93353
    Jul 12 at 11:45
  • $\begingroup$ If you get your number from some challenge, you might suspect it can be broken with existing methods and then try everything you can, including p-1. Otherwise, there's no way to check if p-1 is smooth and the probability of this happening for a random number is negligible. $\endgroup$
    – Fractalice
    Jul 12 at 13:40
  • $\begingroup$ The method is guaranteed to work for any $a$ in the sense that you will arrive at $a^L \equiv 1 \mod p$. However, if you get $a^L \equiv 1 \mod q$ for the same $L$, this does not lead to factorization. This would hint that the p-1 method would indeed work on this N and then trying another $a$ makes sense (or better try the same $a$ with a divisor of $L$ instead). Otherwise, there is no sense in switching $a$ until you get $a^L\equiv 1 \mod p$. $\endgroup$
    – Fractalice
    Jul 12 at 13:45
  • $\begingroup$ If you get your number from some challenge - no I am trying to understand the algorithm. $\endgroup$
    – user93353
    Jul 12 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.