Question

Are there any easy steps to find the factors of big numbers by factorisation process?

Answer 1

Are there any easy steps to find the factors of big numbers by factorisation process?
one you know, where you divide successively by 2, 3, 5, 7, 11, 13,
17, 19, 23, ..., the prime numbers in order, is called Trial Division.
It is very effective for numbers up to about 1000 when doing the
divisions by hand, and to about 1,000,000 when using a computer. The
worst-case time to factor a composite N is sqrt(N) divisions. The
smallest prime factor is always found first.

An old-fashioned way which is often effective is to express N as
the difference of two squares, that is, to find x and y such that
N = x^2 - y^2 = (x - y)*(x + y). One way to do this is to start with
x being the integer just larger than sqrt(N), and see if x^2 - N is
or is not a perfect square. If it is, you have found y^2. If it
is not, replace x by x + 1, and try again. There are some shortcuts
which you'll soon discover, since (for example) perfect squares
must end in 00, n1, n4, 25, m6, or n9, where n is an even digit and
m is an odd one. Even better, one can eliminate whole congruence
classes of possible values of x by reducing the equation modulo a
small prime, and using the fact that both x^2 and y^2 must be
quadratic residues modulo that prime.