The number 160451 is obtained by multiplying two prime numbers. Find these prime numbers.© BrainMass Inc. brainmass.com October 10, 2019, 5:58 am ad1c9bdddf
We can easily check that the number n = 160451 isn't divisible by small prime numbers like 2, 3, 5, 7, etc. So, we need a method that find large prime divisors without us having to try all the previous ones. One such method is "Pollard's p-1 method" which we'll use here. This is based on Fermat's little theorem:
x^(p-1) mod p = 1
for p a prime number and x not equal to 0 mod p.
Pollard's p-1 method works by computing large powers of 2 modulo n. If p is a (unknown) prime divisor of n, then the computation modulo n is consistent with the same computation modulo p, the only difference is that we're not simplifying things as much ...
We explain how Pollard's p-1 method can be used to factor the number.