Cryptography Reference
In-Depth Information
Since with the use of assembler functions we are abandoning our previous
strategy of independence of special platforms, it is useful to implement such
functions in a narrowly targeted way. We must therefore identify those FLINT/C
functions that would most profit in speedup from assembler support. It is
not difficult to determine which are the functions in question. They are those
arithmetic functions with quadratic run-time behavior: multiplication, squaring,
and division. Since the basic operations occupy the principal portion of time
taken up by most of the number-theoretic functions, time improvements in
those functions would be linear, without directly changing the implementation
of the algorithms. To benefit from such a potential, for the FLINT/C package the
functions
mult(), umul(), sqr(),
div_l(),
are implemented in 80x86 assembler. The functions
mult()
,
umul()
,and
sqr()
form the respective kernels of the functions
mult_l()
,
umul_l()
, and
sqr_l()
(see
page 72). The functions support arguments up to length 4096 binary digits, which
is 256 (
= MAX
B
)digitsofa
CLINT
number, and results of double that length.
The assembler functions are, like the corresponding C functions, implemented
according to the algorithms given in Chapter 4, where access to the CPU register
allows processing of 32-bit arguments and 64-bit results with the arithmetic
machine commands (cf. Chapter 2).
The modules
mult.asm
,
mult.s
,
umul.asm
,
umul.s
,
sqr.asm
,
sqr.s
,aswellas
div.asm
and
div.s
, are contained in the FLINT/C package as assembler code.
They can be assembled using Microsoft MASM (call:
ml /Cx /c /Gd <filename>
),
Watcom WASM,
1
or GNU GAS, and these replace the corresponding C functions
when the module
flint.c
is translated with
-DFLINT_ASM
.
2
The calculation times
given again in Appendix D permit a direct comparison of some of the important
functions with and without assembler support.
Montgomery exponentiation (see Chapter 6) offers additional savings
potential, and also the two auxiliary functions
mulmon_l()
and
sqrmon_l()
(cf.
page 111) can be implemented profitably as assembler functions with 32-bit
digits. A starting point for this is offered by the modules
mul.asm
and
sqr.asm
.As
the interested reader can see, there is a very large sandbox out there to play in.
For now, this is all we know.
—Jon Hiseman,
Colosseum
1
Depending on the compiler used the indicators
mult
,
umul
,
sqr
, and
div_l
of the assembler
procedures are to be provided with underscores (
_mult
,
_umul
,
_sqr
, and
_div_l
), since WASM
does not generate them.
2
modules
mult.asm
,
sqr.asm
,
umul.asm
,
and
div.asm
this
With
the
functions
on
80x86
compatible
platforms.
For
other
platforms
one
must
carry
out
the
corresponding
implementations.
