Explore BrainMass

Explore BrainMass

    Factoring into Prime Factors

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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

    Solution Preview

    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 ...

    Solution Summary

    We explain how Pollard's p-1 method can be used to factor the number.