(4) Pollard's p - 1 factorization algorithm (4 pts each) This algorithm seeks to find factors...

 

Transcribed Image Text:

(4) Pollard's p - 1 factorization algorithm (4 pts each) This algorithm seeks to find factors of a composite integer N. We only consider the case when N is a product of two odd primes p and q. As discussed in class, this algorithm can be useful if p-1 has only (relatively) small prime factors, whereas q- 1 has at least one (relatively large) prime factor. The algorithm is as follows: (1) Fix an integer B> 1, and choose an integer a = ao > 1 (start with a = 2). (2) For j = 1,..., B, compute a = a1 (N) and check if 1 < gcd(a,-1, N) < N. If so, you have found a factor of N. (3) If no non-trivial factor has been found in (2), start over with a different a (and maybe with a different B). (i) Find a factor of N = 1739. (ii) Find a factor of N = 34571. (iii) Find a factor of N = 220459. Show your work, i.e., explain which a and B you have chosen, and for which j you have obtained a non-trivial factor. Hint. B-8 should be sufficient in all those cases. (4) Pollard's p - 1 factorization algorithm (4 pts each) This algorithm seeks to find factors of a composite integer N. We only consider the case when N is a product of two odd primes p and q. As discussed in class, this algorithm can be useful if p-1 has only (relatively) small prime factors, whereas q- 1 has at least one (relatively large) prime factor. The algorithm is as follows: (1) Fix an integer B> 1, and choose an integer a = ao > 1 (start with a = 2). (2) For j = 1,..., B, compute a = a1 (N) and check if 1 < gcd(a,-1, N) < N. If so, you have found a factor of N. (3) If no non-trivial factor has been found in (2), start over with a different a (and maybe with a different B). (i) Find a factor of N = 1739. (ii) Find a factor of N = 34571. (iii) Find a factor of N = 220459. Show your work, i.e., explain which a and B you have chosen, and for which j you have obtained a non-trivial factor. Hint. B-8 should be sufficient in all those cases.