f the matrix might take as much time as the sieving stage, or just a fraction thereof. Once found, this solution leads to instant fac- torization or logarithm definition. The two parameters of interest for attacking a number n (as defined by its bit length, also referred to as "field size") are the requirements in time (L) and memory space (S). It can be shown that these requirements are defined by L(n) = (25.1) S(n)= VL(n), (25.2) where C is a constant. Knowing these requirements for a smaller number n', we get the relative estimates (25.3) (25.4) Table 25.6 provides the numbers (In/n',Sn/n') corresponding to the different values of (n, n'). The first row corresponds to the data provided by RSA, 10 i.e., where estimates are relative to n' = 512. Analyzing these data, the constant C involved in the definition in Eq. (25.1) is observed to follow a heuristic rule C = 64.11 X (n/n')0.2542. We can use this rule to compute other estimates with n' = 576, 640, 704, 768, 1024, and 2048. The new dataset we, thus, obtain heuristically provides some estimates for the time and memory size increase factors required to reach larger-number sizes from the best previous achievement. We, thus, see from the table that the time increase from RSA- 512 to RSA-576 represents about an 11-fold factor, corresponding to a raw computing time of 11 X 7.4 months = 81.4 months, or 6 years and 9 months! But if about 1000 See RSA Bulletin 13 (2000), www.rsa.com/rsalabs/node.asp?id=2088 10 See RSA Bulletin 13 (2000), www.rsa.com/rsalabs/node.asp?id=2088. 25.5 Public-key cryptography and RSA Table 25.6 Relative time and memory space increases for factoring number n or solving a logarithm problem of same field size (top row) in reference to the corresponding data for smaller number n' (left columns). The numbers are expressed in bit size. Time increase Memory-space increase 7x106 9x1015 9x107 3x105 2x1014 1x107 3x1010 3x1012 2x105 2x106 1x1011 4x105 9x109 9x104 3x106 workstations and personal computers were used along with (say) five supercomputers