The number 160451 is obtained by multiplying two prime numbers. Find these prime numbers.© BrainMass Inc. brainmass.com September 27, 2022, 4:59 pm ad1c9bdddf
SOLUTION This solution is FREE courtesy of BrainMass!
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 as we can. It can then be that the power of 2 is already equal to 1 mod p, but because we're reducing mod n, we don't get 1. If we take additional powers of that number it will be stuck at 1 mod p. We can, however, check if this is the case by subtracting 1 from the result. This should then be equal to 0 mod p, therefore it is proportional to p. We can test for that by taking the GCD of that number with n, this should yield p if the power modulo p is stuck at 1 (in general one will find a divisor of n which doesn't have to be a prime number, in this case we already know that n is the product of only two prime numbers). Note that the GCD is efficiently computed using Euclid's algorithm which doesn't involve factoring the numbers.
This method works best if p-1 is divisible by many small primes, in that case it can happen that 2^d = 1 mod p for d a number containing only small prime powers. The number d will contain a certain mumber r1 of factors of 2, a number r2 of factors of 3,a number r3 of factors of 5 etc., so one can then start with computing 2^(2^s1) mod n and then taking this this to the power 3^s2, and then 5^s3, etc. etc. for not too larger s1, s2, s3.. etc. If the s1, s2, s3... exceed the r1, r2, r3..., respectively, then one will find a nontrivial GCD. The powers of 2 can be efficiently computed by repeatedly squaring and multiplication.
Let's start with computing x1 = 2^(2^5) mod n. We have:
x1= 2^(2^5) mod n = 14928
GCD(x1-1,n) = 1, so we need to continue. Let's take x1 to the power 3^4:
x2 = x1^(3^4) mod n = 47212
GCD(x2-1,n) = 1, so we need to continue. Let's take x2 to the power 5^3:
x3 = x2^(5^3) mod n = 116583
GCD(x3-1,n) = 1, so we need to continue. Let's take x3 to the power 7^3:
x4 = x3^(7^3) mod n = 65193
GCD(x4-1,n) = 281
We've thus found that 281 is a prime divisor of 160451 without having to bother checking out all the prime numbers till 281!© BrainMass Inc. brainmass.com September 27, 2022, 4:59 pm ad1c9bdddf>