Factoring and Discrete Logarithms - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 53

3.3 Exponential Factoring Methods
When we refer to the speeds of the factoring methods, we are usually concerned not so much with the number
itself, but with its size, typically in binary. For example, the number 700 (in decimal) would be written in binary
as
10 1011 1100
Thus, 700 takes 10 bits to represent in binary. In general, we can use the logarithm function to calculate this.
The base 2 logarithm calculates what power of 2 is required to get the desired number. With the above example,
we can calculate
log 2 700 ≈ 9.4512
We round this up to determine the number of bits needed to represent the number, which is 10 bits. 2
Since, by nature, we do not know the actual number to be factored, but we can generally tell the size of the
number, this is how we categorize factorization algorithms. Categorizing them by this method also lets us see
how well the algorithms do when the numbers start to get very large (hundreds or thousands of digits).
This chapter is concerned with exponential-time algorithms. As we defined earlier, this means that the al-
gorithm running time will be O(a n ), where n is the size of the number (in bits) and a is some number greater
than 1.
Exponential factoring methods are often the easiest to understand. Unfortunately, while they are simple
and often elegant, they are also incredibly slow. Nevertheless, some have advantages over even the fastest al-
gorithms in some circumstances.
3.3.1 Brute-Force
Brute-force algorithms are usually the simplest method to solve most problems with a known set of solutions:
just try every possible solution. Brute-force's motto is, if we don't know where to start, just start trying. Throw
all of your computing power at the problem, and hope to come out on top!
The natural way to brute-force factors? Just try them all. Well, maybe not every number. If you have divided
a number by 2 and found it is not divisible, it's fairly pointless to divide it by 4, 6, 8, and all the rest of the
multiples of 2. It is similarly pointless to divide by 3 and then by 6, 9, 12, and the rest of the multiples of 3, and
if we follow suit, then with the multiples of the rest of the numbers we try.
Therefore, we will limit ourselves to merely trying all of the prime numbers and dividing our target number
by each prime. If the division succeeds (i.e., no remainder), then we have a factor — save the factor, take the
result of the division (the quotient), and continue the algorithm with the quotient. We would start with that same
factor again, since it could be repeated (as in 175 = 5 × 5 × 7).
This technique provides an upper-bound on the amount of work we are willing to do: If any technique takes
more work than brute forcing, then the algorithm doesn't work well.
Animmediateassumptionthatmanymakewhennaivelyimplementingthisalgorithmistotryallprimenum-
bers between 1 and n - 1. However, in general, n - 1 will never divide n (once n > 2). As the numbers get larger,
then n - 2 will never divide n, and so forth. In general, the largest factor that we need to try is Why? The
simple reason is that if n has a factor greater than its square root, it will have to have a factor less than its square