Cryptography Reference
In-Depth Information
Next we generate a product of two 1024-bit primes whose difference is a 513-bit
number but we do not print it:
> c1 := composite(1024, 513):
According to part (iii) of Proposition 6.3, we should expect that
c1
is factored in
just one iteration of the method. We check that this is indeed the case:
> FermatFactor(c1, numsteps = true);
9376119481598189670178184708249987820587448509732023873535826537240803393373660588\
19380513712288153188129280024514233472603095343822209023819519194028125816920564\
30734569648623401050027331504908846961912515800732207621878653273464460340323263\
640473953205028640607039576812581554998809323921247145004288124531, 937611948159\
81896701781847082499878205874485097320238735358265372408033933736605881938051371\
22881531881292800245142334726030953438222090238195191940281260071669855639848217\
00979054986349614871173594157888917234685456077341614075155720921143462952386782\
80536625430651217614777550489855208414846085134829406163, 1
We obtain the two prime factors and we see that the number was indeed factored
in one iteration. Now, let us generate a product of 1024-bit primes whose difference
is a 526-bit number. According to Proposition 6.3, (iii), the number of iterations
should have an approximate length of 2
·
526
−
1024
−
3
=
25. Let us perform the
experiment:
> c2 := composite(1024, 526):
Now, we factor it using
FermatFactor
. As the expected number of iterations
is more than the default 10
7
we specify 10
8
as the maximum number to be tried:
> f := FermatFactor(c2, 10ˆ8, numsteps = true);
1371090756372659806818343723163080929910852649392940386027201082351525293623195140\
78824607051243378099210660992047039365942797335738870000090922675741218923767096\
39961535568119901378943995414790095078431346645338704104175944621988293586807162\
3038455240028404364795738327217160534157876863150844609179133266013, 13710907563\
72659806818343723163080929910852649392940386027201082351525293623195140788246070\
51243378099210660992047039365942797335738870000090922675741388609351092517832031\
63846447162551666884438118710435418812487176891891229195404892601589615492488429\
2069500769986515032246518398978042664097525378337611240901, 26250266
Next we check the length of the involved primes and of the number of iterations,
as well as the length of the difference
q
−
p
:
> ilog2
∼
([f])+
∼
1;
ilog2(f[2]-f[1])+1;
[1024, 1024, 25]
526
We see that these are indeed 1024-bit primes and their difference is a 526-bit
number. More importantly, we also see that the number of iterations is a 25-bit
integer, agreeing exactly with the expected value.
Exercise 6.15
Make a more exhaustive analysis of the behavior of the number of
iterations in Fermat's method by generating composite numbers which are a product
of two 1024-bit primes whose difference ranges from 513 to 526 bits and compar-
ing the number of iterations required in each case with that expected according to
Proposition 6.3.
