Cryptography Reference
In-Depth Information
by about 25 percent. Such possibilities are realizable with functions written
in assembler with direct access to 64-bit results of machine instructions for
multiplication and division or with processors with 64-bit registers that would
also allow to C implementations the lossless storage of such results in a
ULONG
type. The FLINT/C package contains some examples whose gain in speed results
from the use of arithmetic assembler functions (see Chapter 19).
The next question is that of the ordering of the
USHORT
digits within a vector.
We can imagine two possibilities: from left to right, with a descending evaluation
of digits from lower to higher memory addresses, or the other way round, with
an ascending evaluation of digits from lower to higher memory addresses. The
latter arrangement, which is the reverse of our usual notation, has the advantage
that changes in the size of numbers at constant addresses can take place with the
simple allocation of additional digits, without the numbers having to be relocated
in memory. Thus the choice is clear: The evaluation of digits of our numerical
representation increases with increasing memory address or vector index.
As a further element of the representation the number of digits will be
appended and stored in the first element of the vector. The representation of long
numbersinmemorythushastheformat
n
=(
ln
1
n
2
...n
l
)
B
,
0
≤ l ≤
CLINTMAXDIGIT
,
0
≤ n
i
<B, i
=1
,...,l,
where
B
denotes the base of the numerical representation; for the FLINT/C
package we have
B
:= 2
16
= 65536
. The value of
B
will be our companion from
here on and will appear continually in what follows. The constant
CLINTMAXDIGIT
represents the maximal number of digits of a
CLINT
object.
Zero is represented by the length
l
=0
. The value
n
of a number that is
represented by a FLINT/C variable
n_l
is calculated as
⎧
⎨
n_l
[0]
n_l
[
i
]
B
i
−
1
,
if
n_l
[0]
>
0
,
n
=
⎩
i
=1
0
,
otherwise
.
If
n>
0
, then the least-significant digit of
n
to the base
B
is given by
n_l[1]
,
and the most-significant digit by
n_l[n_l[0]]
. The number of digits of
n_l[0]
will be read in what follows by the macro
DIGITS_L (n_l)
and set to
l
by the
macro
SETDIGITS_L (n_l, l)
. Likewise, access to the least-significant and most-
significant digits of
n_l
will be conveyed by
LSDPTR_L(n_l)
and
MSDPTR_L(n_l)
,
each of which returns a pointer to the digit in question. The use of the macros
defined in
flint.h
yields independence from the actual representation of the
number.
