Score:1

Pollard's p - 1 - how do you set the bound & how do you set the base numbers

et flag

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)?
Score:-1
in flag

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.

et flag
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?
et flag
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?
Fractalice avatar
in flag
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.
Fractalice avatar
in flag
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$.
et flag
`If you get your number from some challenge` - no I am trying to understand the algorithm.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.