Chapter 9
Factorisation and Discrete Logarithms
Using a Factor Base
February 15, 2010
9
The two intractable problems which are at the heart of public key cryptosystems, are the infeasibility of factorising large integers and of solving the discrete logarithm (DL) problem. In Chapter 8 some simple schemes for solving these problems were presented. In this chapter the more powerful
(and complex) methods based on factor bases are presented.
9.1
It is shown below that the time (T ) taken by these methods can be ap1−a proximated by ln T = c(ln n)a (ln ln n)√
, this is sometimes written as
1
ln T = L(c, a, n), where a = 2 and c is 2, 2 or 1 depending on the method.
(In the faster and even more complex Number Field Sieve a = 13 .)
These methods are known as “sub-exponential”. If a = 1 we have T = nc ; the time depends exponentially on the absolute value of n. If a = 0 we have
T = (ln n)c ; the time depends exponentially on the log, i.e. the length of n ,
i.e. much faster. For intermediate values of a we have a compromise: Faster than exponential but not as fast as ordinary arithmetic.
The existence of these sub-exponential techniques is a weakness in many crypto systems based on modular arithmetic. One of the attractions of using
Elliptic Curves (EC) techniques for cryptographic algorithms is that there are no known sub-exponential methods of attack.(See Chapter 10).
1
9.2 Factorising Large Integers
(We assume that n, the integer to be factorised, is tested in advance to ensure that it is not a prime, e.g. using Rabin’s test.)
Most factorising algorithms - and certainly the most important ones which can be applied to very large integers - aim to find integer solutions x, y (with x, y < n) to the equation x2 = y 2 mod n
(0.1)
Since this can be written (x + y)(x − y) = 0 (mod n) we can then factorise n by finding HCF ((x − y), n) using the Euclidean algorithm. ( (x + y) = n and x = y are obviously “bad” solutions to equation ?? and are discarded if they arise.) The method used to solve equation ?? involves creating a series of congruences x(i)2 mod n = y(i) =
(p(j)e(i,j) ) < n
(0.2)
where the product is over j = 1, m and p(j) stands for the j th prime number.
That is, y(i) is represented in terms of a Factor Base of m primes. If this can be done for a good number, M say, of x(i), then the solutions can be
“cobbled together” multiplicatively to produce a right-hand side that is all squares, thus
(Over selection of x(i)2 ) =
(over j = 1, m)(p(j)f (j) )2 mod n
(0.3)
for some f (j). Equation ?? has the required form of equation ??. It is clear that constructing the “selection” is equivalent to raising each y(i) to a power c(i) = 0 or 1 and solving
(over i)(c(i).e(i, j)) = 2f (j) = 0 mod 2 for c(i), with j = 1, m. For M greater then m this can always be done; but to avoid “bad” solutions it may be necessary to use M = 2m, say. Therefore the time taken by the procedure is determined by m, the size of the factor base, which in turn controls the probability of finding the congruences (equation
2
??). If m is small the probability of finding a relatively random y(i) which can be expressed as in equation ?? is very small. (Remember that the probability of an arbitrary integer, X, not having a prime factor greater than its square root is about 0.3; while the probability of its not having a prime factor greater
1
then X 9 is about 10−9 .) But make m large and the factor base is large and the calculations become very lengthy. Somewhere in between is an optimum value for m.
Differing techniques are used by the various factorising methods based on equation ?? to generate the congruence (see equation ??). The essence of these differences is the way in which each tries to ensure that y(i), while still relatively random, is confined within some range significantly smaller than
(0, n), so that the probability of equation ?? holding is not too small.
9.3 Factorising - Dixon’s Random Method
An understanding of the issues raised above can
