Cryptography Reference
In-Depth Information
> n := 516378077600327:
MultSelect(n, verbose = true);
Multiplier: 1, f-value: 3.003686
Multiplier: 2, f-value: 6.066766
Multiplier: 3, f-value: 5.551260
Multiplier: 5, f-value: 5.479701
Multiplier: 6, f-value: 3.930504
Multiplier: 7, f-value: 6.235948
Multiplier: 10, f-value: 4.371940
Multiplier: 11, f-value: 4.268430
Multiplier: 13, f-value: 3.754059
Multiplier: 14, f-value: 3.575559
Multiplier: 15, f-value: 3.866392
Multiplier: 17, f-value: 4.323051
Multiplier: 19, f-value: 4.230414
Multiplier: 21, f-value: 3.580619
Multiplier: 22, f-value: 2.993790
Multiplier: 23, f-value: 4.874019
[7, [-1, 2, 5, 7, 11, 13, 17, 23, 29, 31, 37, 43, 47, 59, 61, 67, 89, 97, 101, 131,
137, 151, 163, 173, 179, 191, 193, 197, 199, 211, 223, 227, 263, 269, 277, 283, 293,
307, 311, 317, 347, 349, 353, 359, 367, 373, 383, 389, 397, 401, 409, 419, 421]]
We see that the best multiplier, and hence the one that this function selects, is
m
7, although the multiplier 2, which we used in our earlier computation of the
relations for this number, is a close second. Note also that not using a multiplier (or,
equivalently, using multiplier 1) gives the worst result except for the case
m
=
=
22.
Now the function
FBFactor
will do all the work including, of course, the selection
of the multiplier. The result of applying it to this number is:
> FBFactor(n);
Using multiplier:
7
Using smoothness bound:
432
Size of factor base:
53
Numbers tried to factor:
7446
Smooth values found:
58
Solving a matrix of size:
58, 53
Number of linear dependencies found:
9
Factors:
(16777259) (30778453)
Example 6.18
We give an even more extreme example of the benefits of using a mul-
tiplier. Consider the integer
n
2
=
5541000035610947 and apply the
MultSelect
function to it:
> n2 := 5541000035610947:
MultSelect(n2, verbose = true);
Multiplier: 1, f-value: 1.573015
Multiplier: 2, f-value: 5.714888
Multiplier: 3, f-value: 6.147232
Multiplier: 5, f-value: 5.501545
Multiplier: 6, f-value: 4.644188
Multiplier: 7, f-value: 5.113436
Multiplier: 10, f-value: 4.215535
Multiplier: 11, f-value: 5.706725
