Cryptography Reference
In-Depth Information
(((2((2(1)
2
)
2
)
2
)
2
)
2
)
2
(((2(2
2
)
2
)
2
)
2
)
2
(((2(4)
2
)
2
)
2
)
2
((32
2
)
2
)
2
(1
2
)
2
1 (mod 341).
Writing these computations out is far uglier than actually doing them. You will notice
that calculating 2
340
modulo 341 this way only requires 9 squarings, and only 3 multi-
plications by the base 2. This is a dramatic improvement over 339 multiplications, and
this improvement becomes even more obvious as we use much larger exponents.
To do this, it may help to look at the binary representation of 340; that is,
340 = 101010100
(base 2)
When calculating the lnr
x
of
2
340
(mod 341)
x
You may see an efficient way to determine when to square, and when to multiply by
the base.
5.
Write the following constructor for the Int class.
public Int(int bitlength, int certainty, Random r);
It should generate probable primes of the desired bitlength. They should be prime with
probability exceeding 1
0.25
certainty
.
Search WWH ::
Custom Search