big integer library
git clone git://
Log | Files | Refs | README | LICENSE

what-is-libzahl.tex (8419B)

      1 \chapter{What is libzahl?}
      2 \label{chap:What is libzahl?}
      4 In this chapter, it is discussed what libzahl is,
      5 why it is called libzahl, why it exists, why
      6 you should use it, what makes it different, and
      7 what is its limitations.
      9 \vspace{1cm}
     10 \minitoc
     13 \newpage
     14 \section{The name and the what}
     15 \label{sec:The name and the what}
     17 In mathematics, the set of all integers is represented
     18 by a bold uppercase `Z' ({\bf Z}), or sometimes              % proper symbol
     19 double-stroked (blackboard bold) ($\mathbb{Z}$). This symbol % hand-written style, specially on whiteboards and blackboards
     20 is derived from the german word for integers: `Zahlen'
     21 [\textprimstress{}tsa\textlengthmark{}l\textschwa{}n],
     22 whose singular is `Zahl' [tsa\textlengthmark{}l]. libzahl
     23 [l\textsecstress{}\textsci{}b\textprimstress{}tsa\textlengthmark{}l]
     24 is a C library capable of representing very large integers,
     25 limited by the memory address space and available memory.
     26 Whilst this is almost none of the elements in {\bf Z},
     27 it is substantially more than available using the intrinsic
     28 integer types in C. libzahl of course also implements
     29 functions for performing arithmetic operations over
     30 integers represented using libzahl. Libraries such as
     31 libzahl are called bigint libraries, big integer libraries,
     32 multiple precision integer libraries, arbitrary precision
     33 integer libraries,\footnote{`Multiple precision integer'
     34 and `arbitrary precision integer' are misnomers, precision
     35 is only relevant for floating-point numbers.} or bignum
     36 libraries, or any of the previous with `number' substituted
     37 for `integer'. Some libraries that refer to themselves as bignum
     38 libraries or any of using the word `number' support other
     39 number types than integers. libzahl only supports integers.
     42 \newpage
     43 \section{Why does it exist?}
     44 \label{sec:Why does it exist?}
     46 libzahl's main competitors are GNU MP (gmp),\footnote{GNU
     47 Multiple Precision Arithmetic Library} LibTomMath (ltm),
     48 TomsFastMath (tfm) and Hebimath. All of these have problems:
     50 \begin{itemize}
     51 \item
     52 GNU MP is extremely bloated, can only be complied with
     53 GCC, and requires that you use glibc unless another C
     54 standard library was used when GNU MP was compiled.
     55 Additionally, whilst its performance is generally good,
     56 it can still be improved. Furthermore, GNU MP cannot be
     57 used for robust applications.
     59 \item
     60 LibTomMath is very slow, in fact performance is not its
     61 priority, rather its simplicity is the priority. Despite
     62 this, it is not really that simple.
     64 \item
     65 TomsFastMath is slow, complicated, and is not a true
     66 big integer library and is specifically targeted at
     67 cryptography.
     68 \end{itemize}
     70 libzahl is developed under the umbrella.
     71 As such, it attempts to follow the suckless
     72 philosophy.\footnote{\href{}
     73 {}} libzahl is simple,
     74 very fast, simple to use, and can be used in robust
     75 applications. Currently however, it does not support
     76 multithreading, but it has better support for multiprocessing
     77 and distributed computing than its competitors.
     79 Lesser ``competitors'' (less known) to libzahl include
     80 Hebimath and bsdnt.
     82 \begin{itemize}
     83 \item
     84 Hebimath is far from stable, some fundamental functions
     85 are not implemented and some functions are broken. The
     86 author of libzahl thinks Hebimath is promising, but that
     87 it could be better designed. Like libzahl, Hebimath aims
     88 to follow the suckless philosophy.
     90 \item
     91 bsdnt has not been thoroughly investigated, but it
     92 does not look promising.
     93 \end{itemize}
     96 \newpage
     97 \section{How is it different?}
     98 \label{sec:How is it different?}
    100 All big number libraries have in common that both input
    101 and output integers are parameters for the functions.
    102 There are however two variants of this: input parameters
    103 followed by output parameters, and output parameters
    104 followed by input parameters. The former variant is the
    105 conventional for C functions. The latter is more in style
    106 with primitive operations, pseudo-code, mathematics, and
    107 how it would look if the output was return. In libzahl, the
    108 latter convention is used. That is, we write
    110 \begin{alltt}
    111    zadd(sum, augend, addend);
    112 \end{alltt}
    114 \noindent
    115 rather than
    117 \begin{alltt}
    118    zadd(augend, addend, sum);
    119 \end{alltt}
    121 \noindent
    122 This can be compared to
    124 \vspace{1em}
    125 $sum \gets augend + addend$
    126 \vspace{1em}
    128 \noindent
    129 versus
    131 \vspace{1em}
    132 $augend + addend \rightarrow sum$.
    133 \vspace{1em}
    135 libzahl, GNU MP, and Hebimath use the output-first
    136 convention.\footnote{GNU MP-style.} LibTomMath and
    137 TomsFastMath use the input-first convention.\footnote{BSD
    138 MP-style.}
    140 Unlike other bignum libraries, errors in libzahl are
    141 caught using {\tt setjmp}. This ensure that it can be
    142 used in robust applications, catching errors does not
    143 become a mess, and it minimises the overhead of
    144 catching errors. Typically, errors can be checked when
    145 they can occur and after each function return; however,
    146 here they can be checked only when they can occur.
    148 Additionally, libzahl tries to keep the functions'
    149 names simple and natural rather than technical or
    150 mathematical. The names resemble those of the standard
    151 integer operators. For example, the left-shift, right-shift
    152 and truncation bit-operations in libzahl are called
    153 {\tt zlsh}, {\tt zrsh} and {\tt ztrunc}, respectively.
    154 In GNU MP, they are called {\tt mpz\_mul\_2exp},
    155 {\tt mpz\_tdiv\_q\_2exp} and {\tt mpz\_tdiv\_r\_2exp}.
    156 The need of complicated names are diminished by resisting
    157 to implement all possible variants of each operations.
    158 Variants of a function simply append a short description
    159 of the difference in plain text. For example, a variant of
    160 {\tt zadd} that makes the assumption that both operands
    161 are non-negative (or if not so, calculates the sum of
    162 their absolute values) is called {\tt zadd\_unsigned}.
    163 If libzahl would have had floored and ceiled variants of
    164 {\tt zdiv} (truncated division), they would have been
    165 called {\tt zdiv\_floor} and {\tt zdiv\_ceiling}.
    166 {\tt zdiv} and {\tt zmod} (modulus) are variants of
    167 {\tt zdivmod} that throw away one of the outputs. These
    168 names can be compared to GNU MP's variants of truncated
    169 division: {\tt mpz\_tdiv\_q}, {\tt mpz\_tdiv\_r} and
    170 {\tt mpz\_tdiv\_qr}.
    173 \newpage
    174 \section{Limitations}
    175 \label{sec:Limitations}
    177 libzahl is not recommended for cryptographic
    178 applications, it is not mature enough, and its
    179 author does not have the necessary expertise.
    180 And in particular, it does not implement constant
    181 time operations, and it does not clear pooled
    182 memory. Using libzahl in cryptographic application
    183 is insecure; your application may become susceptible
    184 attacks such as timing attacks, power-monitoring
    185 attacks, electromagnetic attacks, acoustic
    186 cryptanalysis, and data remanence attacks. libzahl
    187 is known to be susceptible to timing attacks
    188 (due to lack of constant time operations) and
    189 data remanence attacks (due to pooling memory
    190 for reuse without clearing the content of the
    191 memory allocations.) Additionally, libzahl is not
    192 thread-safe.
    194 libzahl is also only designed for POSIX systems.
    195 It will probably run just fine on any modern
    196 system. But it makes some assumption that POSIX
    197 stipulates or are unpractical to leave out from
    198 machines that should support POSIX (or even
    199 support modern software):
    201 \begin{itemize}
    202 \item
    203 Bytes are octets.
    205 \item
    206 There is an integer type that is 64-bits wide.
    207 (The compiler needs to support it, but it is not
    208 strictly necessary for it to be an CPU-intrinsic,
    209 but that would be favourable for performance.)
    211 \item
    212 Two's complement is used.
    213 (The compiler needs to support it, but it is not
    214 strictly necessary for it to be an CPU-intrinsic,
    215 but that would be favourable for performance.)
    216 \end{itemize}
    218 Because of the prevalence of these properties
    219 in contemporary machines, and the utilisation of
    220 these properties in software, especially software
    221 for POSIX and popular platforms with similar
    222 properties, any new general-purpose machine must
    223 have these properties, lest it be useless with
    224 today's software. Therefore, libzahl can make
    225 the assumption that the machine has these
    226 properties. If the machine does not have these
    227 properties, the compiler must compensate for
    228 these machines deficiencies, making it generally
    229 slower.
    231 These limitations may be removed later. And there
    232 is some code that does not make these assumptions
    233 but acknowledge that it may be a case. On the other
    234 hand, these limitations could be fixed, and agnostic
    235 code could be rewritten to assume that these
    236 restrictions are met.