Factorization Techniques - Introduction to Cryptography with Java Applets - page 220

CHAPTER 12

Factorization Techniques

The Rabin cipher, like some other modern ciphers, is believed secure because break-
ing it seems to involve factoring a huge integer having two large prime factors. This
certainly appears to be the case; finding large prime factors is an intractable problem. Hence,
research into better factorization techniques is a very serious endeavor now, often involv-
ing fair sums of money.
Many factorization methods have been developed over the years, but unfortunately, they
are not widely known to the public. In fact, it is likely that trial division is the only method
of factoring most people will learn in their lives.
Recall how the trial division method works; to factor an integer n , do trial divisions of n
by integers between 2 and the square root of n . A factor, say d , of n is guaranteed to lie in
this range by proposition 6. We can then take n 1 = n / d , then continue to factor n 1 by look-
ing for factors between 2 and the square root of n 1 . We continue in this way, reducing the
size of n by producing a smaller number n i to factor, at iteration i . We will eventually obtain
the full factorization of n . The trial division method is quite simple, but is very inefficient
when n has only large prime factors, since it may be necessary to try factors very near

√ n .
When n is very large, its square root is also very large; a loop passing through all the primes
less than √ n could take virtually an eternity. However, it is important to note that when n does

have small prime factors, this sequential search for factors is quite efficient, and often finds
small factors well before an alternative factoring method would.
We will cover a few alternative methods of factoring here; many are quite innovative, and
the fact that they actually work may seem surprising to you. Though none of the methods
covered here are nearly fast enough to break ciphers based on the factoring problem, inves-
tigating them is undoubtedly worthwhile, for they may provide insight into even better fac-
torization methods.

12.1

FERMAT FACTORIZATION
This method is named after Pierre de Fermat. Though it can be even more inefficient than
the trial division method, it is valuable in that it provides you with an alternative view of
factoring.