Algorithmic Number Theory for Cryptography and Cryptanalysis: Primality, Factoring and Discrete Logarithms - Introduction to Cryptography with Maple - page 349

Multiplier: 13, f-value: 4.474718
Multiplier: 14, f-value: 4.740725
Multiplier: 15, f-value: 4.187766
Multiplier: 17, f-value: 5.722923
Multiplier: 19, f-value: 5.106755
Multiplier: 21, f-value: 3.697481
Multiplier: 22, f-value: 3.995631
Multiplier: 23, f-value: 4.099556

[3, [-1, 2, 3, 5, 7, 17, 19, 29, 31, 41, 43, 53, 67, 79, 89, 101, 103, 109, 113,
127, 157, 163, 181, 199, 229, 239, 257, 269, 271, 281, 283, 317, 337, 347, 353,
367, 373, 379, 389, 397, 409, 433, 439, 443, 457, 487, 491, 503]]

Here the multiplier 1 gives the worst result by far and the reason stands out clearly
if we compute the factor base corresponding to n 2 without using a multiplier:

> FactorBase(n2);
[-1, 2, 109, 137, 139, 149, 151, 157, 173, 181, 197, 211, 223, 229, 233, 239, 293,
307, 331, 337, 347, 373, 397, 401, 409, 433, 443, 449]

Already at first sight we notice that this factor base leaves a lot to be desired. It is
small, with only 28 elements, in contrast with the one corresponding to the multiplier
3 above, which has 48 elements. Even worse, the smallest odd prime in the factor
base is 109. On top of all this, we have that n 2 , which makes the

contribution of the prime 2 as small as possible, as we saw when discussing the
choice of multiplier. These inconveniences are reflected in the low f -value for the
multiplier 1 and make it difficult to factor n 2 without using a multiplier; we would
probably have to choose a smoothness bound larger than the usual one and it would
take a lot of time to factor the number. Of course, you are not likely to come across
a number like this one just by chance

≡ 3 ( mod 4 )

...

Let us now try FBFactor on n 2:

> FBFactor(n2);

Using multiplier:
3
Using smoothness bound:
503
Size of factor base:
48
Numbers tried to factor:
25704
Smooth values found:
53
Solving a matrix of size:
53, 48
Number of linear dependencies found:
8
Factors:
(131564099) (42116353)

We see that FBFactor factors n 2 quickly, the reason being that it uses the
multiplier 3, whose f -value is almost four times as big as that of the multiplier 1.

Exercise 6.21 Construct a product of two 10-digit primes such that the multiplier
23 has a higher f -value than all the preceding multipliers, and factor it using

FBFactor .