The following describes pollard’s p−1 method of factoring large numbers. (note: there’s no universal way to factor large numbers, or rsa encryption wouldn’t work! )
let n be a large number, and suppose that p is one of its (unknown to us) prime factors. the p−1 method works well if p−1 factors into small primes.
pollard’s algorithm is as follows.
1. begin with a small a1, such as a1= 2. if a1is not relatively prime to n, then we have found a factor of n.
2. otherwise, follow the recursive formula
a2=a1^2(mod n)
a3=a2^3(mod n)
.
.
.
ai=(ai−1)^i(mod n)
to construct a sequence of numbers a1, . . , ai, until we have found
d= gcd(ai−1, n)not equal to 1
(note: that’s not a typo, i do indeed mean (ai)−1, not ai−1).
3. if d not equal to n, we have found a factor of n. if d=n, then the algorithm has failed and we try again with a different a.
(a) perform the algorithm to factor n= 901 with a starting a= 2.
(b) whenever we discuss an algorithm, we want to know if this algorithm terminates. suppose n is our large number, pis a factor of n, and b is an integer such that p−1 divides b. we claim that the algorithm terminates in b steps. write ai in terms of a1, (mod n).
(c) show that ab≡1 (mod p).
(d) argue that the algorithm thus terminates in b or fewer steps.