1
$\begingroup$

The Pollard p-1 factorization method states if $\gcd(2^{B!}-1,n)=p$ where $p>1$ and $B$ bounds the prime factors of $p$, then $p$ is a prime factor of $n$.

  • Shouldn't it be $\gcd(a^{B!}-1,n)$ for any arbitrary $a$?
  • Why are we choosing $a=2$? Is it because it is computationally cheaper to compute powers of $2$? ( left shift ).
  • Moreover, should $B$ be an upper bound of the prime factor of $p-1$ or an upper bound of the prime factor of $p-1$ along with its powers? pollard
$\endgroup$
0
$\begingroup$
  • Shouldn't it be $\gcd(a^{B!}-1,n)$ for any arbitrary $a$.

Yes, and your code tries calculates it in the while loop. Note: normally

$$M = \prod_{\text{primes}~q \le B} q^{ \lfloor \log_q{B} \rfloor }$$ only primes which are less then or equal to $B$ constitute to $M$. The pseudocode in your slide includes all numbers $<B$ which is not correct, it must be prime less or equal to $B$.

  • Why are we choosing $a=2$? is it because it is computationally cheaper to compute powers of $2$? ( left shift ).

We want a random integer $a$ that is co-prime to $n$, i.e $\gcd(a,n)=1$. If 2 is possible choice as in RSA modulus - $n$ is a product of two odd primes, it will be easy to calculate $\gcd(2^{B!}-1,n)$

  • moreover, should $B$, be an upper bound of prime factor of $p-1$ or upper bound of prime factor of $p-1$ along with its powers?

$B$ is a smooth number, and in the beginning, you select any smoothness bound for $B$. From Wikipedia code;

  1. select a smoothness bound B
  2. define $M = \prod_{\text{primes}~q \le B} q^{ \lfloor \log_q{B} \rfloor }$
  3. randomly pick a coprime to $n$ (note: we can actually fix $a$, e.g. if $n$ is odd, then we can always select $a = 2$, random selection here is not imperative)
  4. compute $g = \gcd(a^M − 1, n)$ (note: exponentiation can be done modulo $n$)
  5. if $1 < g < n$ then return $g$
  6. if $g = 1$ then select a larger $B$ and go to step 2 or return failure
  7. if $g = n$ then select a smaller $B$ and go to step 2 or return failure

So the algorithm in sense an adaptive algorithm. In a failure either you can stop or adjust the smoothness bound.

| improve this answer | |
$\endgroup$

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.