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

The reason this works is that a square is going to have even numbers as exponents of prime factors. If we
have two numbers that when multiplied together (adding their exponents) have even numbers in the exponent,
we have a perfect square.

3.4.1.1 Analysis of CFRAC
Although the above work is fairly complex and involved, the above method saves an extraordinary amount of
time. Using the CFRAC method to factor an integer will yield a running time on the order of
For reference, a normal exponential algorithm might be about . For a = 10,000,000,000 (10 billion),
this means a running time on the order of 10,000,000,000 operations for an exponential method, and on the
order of 170,000 operations for CFRAC.

3.4.2 Sieving Methods
Twofinal methods that weshall notdelve toodeeply into are the quadraticsieve (QS)andthe generalnumber
field sieve (GNFS). Both rely on the principle of Fermat's difference of squares and produce factors using this
idea.
For QS, the idea is very similar to the continued fraction method in the previous section, using sieve instead
of trial division for factorizations. The running time of QS tends to be on the order of about with a

being the integer to be factored. For more information on QS, see References [3] and [13].
A lot of focus has been on the GNFS, since it is the fastest known method for factoring large integers, or in
testing the primality of extremely large integers.
The GNFS works in three basic parts. First, the algorithm finds an irreducible polynomial that has a zero
modulo n [where n is the modulo base we are working with, so that gcd( x - y , n ) > 1, to find a factor]. Next, we
find squares of a certain form that will likely yield factors. Then we find the square roots.
The “sieve” in the GNFS comes from the finding of squares in the second step. The special form that the
squares come into involves calculating products of the sums of relatively prime integers. These relatively prime
integers are calculated using sieving techniques.
For more information on the GNFS, see, for example, References [2] and [8].

3.5 Discrete Logarithms
Many algorithms use large group operations, such as exponentiation and large integer multiplication, to hide
data.
For example, we can choose a finite field such as ( 23 , +, ×) and a generator 2. We can easily calculate 2 9
= 6 in 23 . But, if someone saw a message passed as the integer 6, even with the knowledge that the generator
is 2 and the field is over 23 , it is still, in general, a difficult problem to discover the exponent applied to the
generator that yielded the given integer.
Solving an equation
a x = b