bn.tex revision f7fc46c63fdc8f39234fea409b8dbe116d73ebf8
1f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\documentclass[synpaper]{book} 2f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\usepackage{hyperref} 3f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\usepackage{makeidx} 4f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\usepackage{amssymb} 5f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\usepackage{color} 6f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\usepackage{alltt} 7f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\usepackage{graphicx} 8f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\usepackage{layout} 9f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\union{\cup} 10f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\intersect{\cap} 11f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\getsrandom{\stackrel{\rm R}{\gets}} 12f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\cross{\times} 13f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\cat{\hspace{0.5em} \| \hspace{0.5em}} 14f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\catn{$\|$} 15f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\divides{\hspace{0.3em} | \hspace{0.3em}} 16f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\nequiv{\not\equiv} 17f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\approx{\raisebox{0.2ex}{\mbox{\small $\sim$}}} 18f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\lcm{{\rm lcm}} 19f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\gcd{{\rm gcd}} 20f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\log{{\rm log}} 21f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\ord{{\rm ord}} 22f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\abs{{\mathit abs}} 23f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\rep{{\mathit rep}} 24f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\mod{{\mathit\ mod\ }} 25f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\renewcommand{\pmod}[1]{\ ({\rm mod\ }{#1})} 26f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} 27f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil} 28f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\Or{{\rm\ or\ }} 29f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\And{{\rm\ and\ }} 30f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\iff{\hspace{1em}\Longleftrightarrow\hspace{1em}} 31f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\implies{\Rightarrow} 32f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\undefined{{\rm ``undefined"}} 33f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\Proof{\vspace{1ex}\noindent {\bf Proof:}\hspace{1em}} 34f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\let\oldphi\phi 35f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\phi{\varphi} 36f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\Pr{{\rm Pr}} 37f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\newcommand{\str}[1]{{\mathbf{#1}}} 38f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\F{{\mathbb F}} 39f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\N{{\mathbb N}} 40f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\Z{{\mathbb Z}} 41f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\R{{\mathbb R}} 42f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\C{{\mathbb C}} 43f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\Q{{\mathbb Q}} 44f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\definecolor{DGray}{gray}{0.5} 45f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\newcommand{\emailaddr}[1]{\mbox{$<${#1}$>$}} 46f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\twiddle{\raisebox{0.3ex}{\mbox{\tiny $\sim$}}} 47f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\def\gap{\vspace{0.5ex}} 48f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\makeindex 49f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{document} 50f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\frontmatter 51f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\pagestyle{empty} 52f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\title{LibTomMath User Manual \\ v0.40} 53f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\author{Tom St Denis \\ tomstdenis@gmail.com} 54f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\maketitle 55f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis text, the library and the accompanying textbook are all hereby placed in the public domain. This book has been 56f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectformatted for B5 [176x250] paper using the \LaTeX{} {\em book} macro package. 57f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 58f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\vspace{10cm} 59f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 60f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{flushright}Open Source. Open Academia. Open Minds. 61f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 62f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\mbox{ } 63f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 64f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectTom St Denis, 65f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 66f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectOntario, Canada 67f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{flushright} 68f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 69f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\tableofcontents 70f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\listoffigures 71f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\mainmatter 72f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\pagestyle{headings} 73f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\chapter{Introduction} 74f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{What is LibTomMath?} 75f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectLibTomMath is a library of source code which provides a series of efficient and carefully written functions for manipulating 76f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectlarge integer numbers. It was written in portable ISO C source code so that it will build on any platform with a conforming 77f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectC compiler. 78f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 79f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectIn a nutshell the library was written from scratch with verbose comments to help instruct computer science students how 80f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectto implement ``bignum'' math. However, the resulting code has proven to be very useful. It has been used by numerous 81f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectuniversities, commercial and open source software developers. It has been used on a variety of platforms ranging from 82f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectLinux and Windows based x86 to ARM based Gameboys and PPC based MacOS machines. 83f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 84f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{License} 85f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectAs of the v0.25 the library source code has been placed in the public domain with every new release. As of the v0.28 86f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectrelease the textbook ``Implementing Multiple Precision Arithmetic'' has been placed in the public domain with every new 87f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectrelease as well. This textbook is meant to compliment the project by providing a more solid walkthrough of the development 88f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectalgorithms used in the library. 89f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 90f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectSince both\footnote{Note that the MPI files under mtest/ are copyrighted by Michael Fromberger. They are not required to use LibTomMath.} are in the 91f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectpublic domain everyone is entitled to do with them as they see fit. 92f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 93f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Building LibTomMath} 94f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 95f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectLibTomMath is meant to be very ``GCC friendly'' as it comes with a makefile well suited for GCC. However, the library will 96f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectalso build in MSVC, Borland C out of the box. For any other ISO C compiler a makefile will have to be made by the end 97f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectdeveloper. 98f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 99f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\subsection{Static Libraries} 100f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectTo build as a static library for GCC issue the following 101f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 102f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectmake 103f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 104f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 105f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectcommand. This will build the library and archive the object files in ``libtommath.a''. Now you link against 106f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectthat and include ``tommath.h'' within your programs. Alternatively to build with MSVC issue the following 107f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 108f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectnmake -f makefile.msvc 109f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 110f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 111f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis will build the library and archive the object files in ``tommath.lib''. This has been tested with MSVC 112f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectversion 6.00 with service pack 5. 113f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 114f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\subsection{Shared Libraries} 115f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectTo build as a shared library for GCC issue the following 116f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 117f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectmake -f makefile.shared 118f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 119f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis requires the ``libtool'' package (common on most Linux/BSD systems). It will build LibTomMath as both shared 120f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectand static then install (by default) into /usr/lib as well as install the header files in /usr/include. The shared 121f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectlibrary (resource) will be called ``libtommath.la'' while the static library called ``libtommath.a''. Generally 122f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectyou use libtool to link your application against the shared object. 123f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 124f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThere is limited support for making a ``DLL'' in windows via the ``makefile.cygwin\_dll'' makefile. It requires 125f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectCygwin to work with since it requires the auto-export/import functionality. The resulting DLL and import library 126f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project``libtommath.dll.a'' can be used to link LibTomMath dynamically to any Windows program using Cygwin. 127f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 128f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\subsection{Testing} 129f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectTo build the library and the test harness type 130f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 131f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 132f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectmake test 133f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 134f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 135f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis will build the library, ``test'' and ``mtest/mtest''. The ``test'' program will accept test vectors and verify the 136f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectresults. ``mtest/mtest'' will generate test vectors using the MPI library by Michael Fromberger\footnote{A copy of MPI 137f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectis included in the package}. Simply pipe mtest into test using 138f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 139f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 140f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectmtest/mtest | test 141f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 142f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 143f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectIf you do not have a ``/dev/urandom'' style RNG source you will have to write your own PRNG and simply pipe that into 144f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectmtest. For example, if your PRNG program is called ``myprng'' simply invoke 145f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 146f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 147f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectmyprng | mtest/mtest | test 148f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 149f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 150f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis will output a row of numbers that are increasing. Each column is a different test (such as addition, multiplication, etc) 151f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectthat is being performed. The numbers represent how many times the test was invoked. If an error is detected the program 152f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectwill exit with a dump of the relevent numbers it was working with. 153f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 154f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Build Configuration} 155f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectLibTomMath can configured at build time in three phases we shall call ``depends'', ``tweaks'' and ``trims''. 156f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectEach phase changes how the library is built and they are applied one after another respectively. 157f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 158f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectTo make the system more powerful you can tweak the build process. Classes are defined in the file 159f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project``tommath\_superclass.h''. By default, the symbol ``LTM\_ALL'' shall be defined which simply 160f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectinstructs the system to build all of the functions. This is how LibTomMath used to be packaged. This will give you 161f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectaccess to every function LibTomMath offers. 162f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 163f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectHowever, there are cases where such a build is not optional. For instance, you want to perform RSA operations. You 164f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectdon't need the vast majority of the library to perform these operations. Aside from LTM\_ALL there is 165f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectanother pre--defined class ``SC\_RSA\_1'' which works in conjunction with the RSA from LibTomCrypt. Additional 166f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectclasses can be defined base on the need of the user. 167f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 168f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\subsection{Build Depends} 169f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectIn the file tommath\_class.h you will see a large list of C ``defines'' followed by a series of ``ifdefs'' 170f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectwhich further define symbols. All of the symbols (technically they're macros $\ldots$) represent a given C source 171f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectfile. For instance, BN\_MP\_ADD\_C represents the file ``bn\_mp\_add.c''. When a define has been enabled the 172f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectfunction in the respective file will be compiled and linked into the library. Accordingly when the define 173f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectis absent the file will not be compiled and not contribute any size to the library. 174f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 175f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectYou will also note that the header tommath\_class.h is actually recursively included (it includes itself twice). 176f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis is to help resolve as many dependencies as possible. In the last pass the symbol LTM\_LAST will be defined. 177f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis is useful for ``trims''. 178f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 179f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\subsection{Build Tweaks} 180f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectA tweak is an algorithm ``alternative''. For example, to provide tradeoffs (usually between size and space). 181f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThey can be enabled at any pass of the configuration phase. 182f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 183f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{small} 184f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{center} 185f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{tabular}{|l|l|} 186f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline \textbf{Define} & \textbf{Purpose} \\ 187f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline BN\_MP\_DIV\_SMALL & Enables a slower, smaller and equally \\ 188f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project & functional mp\_div() function \\ 189f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline 190f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{tabular} 191f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{center} 192f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{small} 193f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 194f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\subsection{Build Trims} 195f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectA trim is a manner of removing functionality from a function that is not required. For instance, to perform 196f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectRSA cryptography you only require exponentiation with odd moduli so even moduli support can be safely removed. 197f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectBuild trims are meant to be defined on the last pass of the configuration which means they are to be defined 198f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectonly if LTM\_LAST has been defined. 199f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 200f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\subsubsection{Moduli Related} 201f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{small} 202f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{center} 203f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{tabular}{|l|l|} 204f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline \textbf{Restriction} & \textbf{Undefine} \\ 205f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline Exponentiation with odd moduli only & BN\_S\_MP\_EXPTMOD\_C \\ 206f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project & BN\_MP\_REDUCE\_C \\ 207f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project & BN\_MP\_REDUCE\_SETUP\_C \\ 208f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project & BN\_S\_MP\_MUL\_HIGH\_DIGS\_C \\ 209f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project & BN\_FAST\_S\_MP\_MUL\_HIGH\_DIGS\_C \\ 210f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline Exponentiation with random odd moduli & (The above plus the following) \\ 211f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project & BN\_MP\_REDUCE\_2K\_C \\ 212f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project & BN\_MP\_REDUCE\_2K\_SETUP\_C \\ 213f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project & BN\_MP\_REDUCE\_IS\_2K\_C \\ 214f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project & BN\_MP\_DR\_IS\_MODULUS\_C \\ 215f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project & BN\_MP\_DR\_REDUCE\_C \\ 216f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project & BN\_MP\_DR\_SETUP\_C \\ 217f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline Modular inverse odd moduli only & BN\_MP\_INVMOD\_SLOW\_C \\ 218f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline Modular inverse (both, smaller/slower) & BN\_FAST\_MP\_INVMOD\_C \\ 219f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline 220f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{tabular} 221f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{center} 222f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{small} 223f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 224f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\subsubsection{Operand Size Related} 225f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{small} 226f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{center} 227f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{tabular}{|l|l|} 228f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline \textbf{Restriction} & \textbf{Undefine} \\ 229f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline Moduli $\le 2560$ bits & BN\_MP\_MONTGOMERY\_REDUCE\_C \\ 230f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project & BN\_S\_MP\_MUL\_DIGS\_C \\ 231f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project & BN\_S\_MP\_MUL\_HIGH\_DIGS\_C \\ 232f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project & BN\_S\_MP\_SQR\_C \\ 233f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline Polynomial Schmolynomial & BN\_MP\_KARATSUBA\_MUL\_C \\ 234f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project & BN\_MP\_KARATSUBA\_SQR\_C \\ 235f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project & BN\_MP\_TOOM\_MUL\_C \\ 236f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project & BN\_MP\_TOOM\_SQR\_C \\ 237f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 238f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline 239f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{tabular} 240f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{center} 241f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{small} 242f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 243f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 244f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Purpose of LibTomMath} 245f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectUnlike GNU MP (GMP) Library, LIP, OpenSSL or various other commercial kits (Miracl), LibTomMath was not written with 246f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectbleeding edge performance in mind. First and foremost LibTomMath was written to be entirely open. Not only is the 247f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectsource code public domain (unlike various other GPL/etc licensed code), not only is the code freely downloadable but the 248f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectsource code is also accessible for computer science students attempting to learn ``BigNum'' or multiple precision 249f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectarithmetic techniques. 250f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 251f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectLibTomMath was written to be an instructive collection of source code. This is why there are many comments, only one 252f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectfunction per source file and often I use a ``middle-road'' approach where I don't cut corners for an extra 2\% speed 253f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectincrease. 254f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 255f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectSource code alone cannot really teach how the algorithms work which is why I also wrote a textbook that accompanies 256f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectthe library (beat that!). 257f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 258f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectSo you may be thinking ``should I use LibTomMath?'' and the answer is a definite maybe. Let me tabulate what I think 259f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectare the pros and cons of LibTomMath by comparing it to the math routines from GnuPG\footnote{GnuPG v1.2.3 versus LibTomMath v0.28}. 260f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 261f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\newpage\begin{figure}[here] 262f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{small} 263f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{center} 264f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{tabular}{|l|c|c|l|} 265f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline \textbf{Criteria} & \textbf{Pro} & \textbf{Con} & \textbf{Notes} \\ 266f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline Few lines of code per file & X & & GnuPG $ = 300.9$, LibTomMath $ = 71.97$ \\ 267f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline Commented function prototypes & X && GnuPG function names are cryptic. \\ 268f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline Speed && X & LibTomMath is slower. \\ 269f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline Totally free & X & & GPL has unfavourable restrictions.\\ 270f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline Large function base & X & & GnuPG is barebones. \\ 271f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline Five modular reduction algorithms & X & & Faster modular exponentiation for a variety of moduli. \\ 272f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline Portable & X & & GnuPG requires configuration to build. \\ 273f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline 274f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{tabular} 275f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{center} 276f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{small} 277f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\caption{LibTomMath Valuation} 278f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{figure} 279f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 280f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectIt may seem odd to compare LibTomMath to GnuPG since the math in GnuPG is only a small portion of the entire application. 281f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectHowever, LibTomMath was written with cryptography in mind. It provides essentially all of the functions a cryptosystem 282f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectwould require when working with large integers. 283f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 284f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectSo it may feel tempting to just rip the math code out of GnuPG (or GnuMP where it was taken from originally) in your 285f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectown application but I think there are reasons not to. While LibTomMath is slower than libraries such as GnuMP it is 286f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectnot normally significantly slower. On x86 machines the difference is normally a factor of two when performing modular 287f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectexponentiations. It depends largely on the processor, compiler and the moduli being used. 288f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 289f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectEssentially the only time you wouldn't use LibTomMath is when blazing speed is the primary concern. However, 290f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projecton the other side of the coin LibTomMath offers you a totally free (public domain) well structured math library 291f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectthat is very flexible, complete and performs well in resource contrained environments. Fast RSA for example can 292f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectbe performed with as little as 8KB of ram for data (again depending on build options). 293f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 294f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\chapter{Getting Started with LibTomMath} 295f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Building Programs} 296f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectIn order to use LibTomMath you must include ``tommath.h'' and link against the appropriate library file (typically 297f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectlibtommath.a). There is no library initialization required and the entire library is thread safe. 298f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 299f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Return Codes} 300f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThere are three possible return codes a function may return. 301f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 302f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{MP\_OKAY}\index{MP\_YES}\index{MP\_NO}\index{MP\_VAL}\index{MP\_MEM} 303f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{figure}[here!] 304f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{center} 305f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{small} 306f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{tabular}{|l|l|} 307f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline \textbf{Code} & \textbf{Meaning} \\ 308f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline MP\_OKAY & The function succeeded. \\ 309f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline MP\_VAL & The function input was invalid. \\ 310f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline MP\_MEM & Heap memory exhausted. \\ 311f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline &\\ 312f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline MP\_YES & Response is yes. \\ 313f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline MP\_NO & Response is no. \\ 314f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline 315f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{tabular} 316f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{small} 317f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{center} 318f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\caption{Return Codes} 319f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{figure} 320f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 321f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThe last two codes listed are not actually ``return'ed'' by a function. They are placed in an integer (the caller must 322f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectprovide the address of an integer it can store to) which the caller can access. To convert one of the three return codes 323f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectto a string use the following function. 324f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 325f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_error\_to\_string} 326f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 327f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectchar *mp_error_to_string(int code); 328f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 329f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 330f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis will return a pointer to a string which describes the given error code. It will not work for the return codes 331f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectMP\_YES and MP\_NO. 332f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 333f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Data Types} 334f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThe basic ``multiple precision integer'' type is known as the ``mp\_int'' within LibTomMath. This data type is used to 335f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectorganize all of the data required to manipulate the integer it represents. Within LibTomMath it has been prototyped 336f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectas the following. 337f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 338f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_int} 339f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 340f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projecttypedef struct \{ 341f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int used, alloc, sign; 342f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_digit *dp; 343f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\} mp_int; 344f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 345f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 346f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectWhere ``mp\_digit'' is a data type that represents individual digits of the integer. By default, an mp\_digit is the 347f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectISO C ``unsigned long'' data type and each digit is $28-$bits long. The mp\_digit type can be configured to suit other 348f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectplatforms by defining the appropriate macros. 349f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 350f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectAll LTM functions that use the mp\_int type will expect a pointer to mp\_int structure. You must allocate memory to 351f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projecthold the structure itself by yourself (whether off stack or heap it doesn't matter). The very first thing that must be 352f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectdone to use an mp\_int is that it must be initialized. 353f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 354f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Function Organization} 355f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 356f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThe arithmetic functions of the library are all organized to have the same style prototype. That is source operands 357f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectare passed on the left and the destination is on the right. For instance, 358f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 359f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 360f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectmp_add(&a, &b, &c); /* c = a + b */ 361f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectmp_mul(&a, &a, &c); /* c = a * a */ 362f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectmp_div(&a, &b, &c, &d); /* c = [a/b], d = a mod b */ 363f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 364f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 365f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectAnother feature of the way the functions have been implemented is that source operands can be destination operands as well. 366f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectFor instance, 367f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 368f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 369f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectmp_add(&a, &b, &b); /* b = a + b */ 370f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectmp_div(&a, &b, &a, &c); /* a = [a/b], c = a mod b */ 371f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 372f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 373f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis allows operands to be re-used which can make programming simpler. 374f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 375f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Initialization} 376f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\subsection{Single Initialization} 377f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectA single mp\_int can be initialized with the ``mp\_init'' function. 378f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 379f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_init} 380f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 381f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_init (mp_int * a); 382f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 383f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 384f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis function expects a pointer to an mp\_int structure and will initialize the members of the structure so the mp\_int 385f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectrepresents the default integer which is zero. If the functions returns MP\_OKAY then the mp\_int is ready to be used 386f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectby the other LibTomMath functions. 387f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 388f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{small} \begin{alltt} 389f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint main(void) 390f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\{ 391f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_int number; 392f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int result; 393f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 394f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_init(&number)) != MP_OKAY) \{ 395f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error initializing the number. \%s", 396f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 397f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 398f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 399f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 400f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* use the number */ 401f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 402f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_SUCCESS; 403f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\} 404f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} \end{small} 405f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 406f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\subsection{Single Free} 407f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectWhen you are finished with an mp\_int it is ideal to return the heap it used back to the system. The following function 408f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectprovides this functionality. 409f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 410f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_clear} 411f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 412f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectvoid mp_clear (mp_int * a); 413f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 414f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 415f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThe function expects a pointer to a previously initialized mp\_int structure and frees the heap it uses. It sets the 416f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectpointer\footnote{The ``dp'' member.} within the mp\_int to \textbf{NULL} which is used to prevent double free situations. 417f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectIs is legal to call mp\_clear() twice on the same mp\_int in a row. 418f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 419f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{small} \begin{alltt} 420f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint main(void) 421f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\{ 422f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_int number; 423f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int result; 424f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 425f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_init(&number)) != MP_OKAY) \{ 426f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error initializing the number. \%s", 427f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 428f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 429f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 430f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 431f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* use the number */ 432f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 433f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* We're done with it. */ 434f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_clear(&number); 435f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 436f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_SUCCESS; 437f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\} 438f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} \end{small} 439f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 440f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\subsection{Multiple Initializations} 441f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectCertain algorithms require more than one large integer. In these instances it is ideal to initialize all of the mp\_int 442f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectvariables in an ``all or nothing'' fashion. That is, they are either all initialized successfully or they are all 443f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectnot initialized. 444f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 445f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThe mp\_init\_multi() function provides this functionality. 446f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 447f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_init\_multi} \index{mp\_clear\_multi} 448f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 449f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_init_multi(mp_int *mp, ...); 450f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 451f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 452f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectIt accepts a \textbf{NULL} terminated list of pointers to mp\_int structures. It will attempt to initialize them all 453f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectat once. If the function returns MP\_OKAY then all of the mp\_int variables are ready to use, otherwise none of them 454f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectare available for use. A complementary mp\_clear\_multi() function allows multiple mp\_int variables to be free'd 455f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectfrom the heap at the same time. 456f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 457f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{small} \begin{alltt} 458f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint main(void) 459f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\{ 460f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_int num1, num2, num3; 461f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int result; 462f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 463f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_init_multi(&num1, 464f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project &num2, 465f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project &num3, NULL)) != MP\_OKAY) \{ 466f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error initializing the numbers. \%s", 467f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 468f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 469f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 470f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 471f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* use the numbers */ 472f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 473f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* We're done with them. */ 474f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_clear_multi(&num1, &num2, &num3, NULL); 475f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 476f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_SUCCESS; 477f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\} 478f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} \end{small} 479f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 480f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\subsection{Other Initializers} 481f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectTo initialized and make a copy of an mp\_int the mp\_init\_copy() function has been provided. 482f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 483f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_init\_copy} 484f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 485f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_init_copy (mp_int * a, mp_int * b); 486f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 487f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 488f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis function will initialize $a$ and make it a copy of $b$ if all goes well. 489f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 490f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{small} \begin{alltt} 491f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint main(void) 492f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\{ 493f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_int num1, num2; 494f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int result; 495f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 496f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* initialize and do work on num1 ... */ 497f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 498f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* We want a copy of num1 in num2 now */ 499f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_init_copy(&num2, &num1)) != MP_OKAY) \{ 500f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error initializing the copy. \%s", 501f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 502f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 503f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 504f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 505f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* now num2 is ready and contains a copy of num1 */ 506f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 507f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* We're done with them. */ 508f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_clear_multi(&num1, &num2, NULL); 509f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 510f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_SUCCESS; 511f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\} 512f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} \end{small} 513f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 514f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectAnother less common initializer is mp\_init\_size() which allows the user to initialize an mp\_int with a given 515f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectdefault number of digits. By default, all initializers allocate \textbf{MP\_PREC} digits. This function lets 516f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectyou override this behaviour. 517f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 518f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_init\_size} 519f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 520f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_init_size (mp_int * a, int size); 521f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 522f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 523f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThe $size$ parameter must be greater than zero. If the function succeeds the mp\_int $a$ will be initialized 524f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectto have $size$ digits (which are all initially zero). 525f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 526f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{small} \begin{alltt} 527f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint main(void) 528f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\{ 529f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_int number; 530f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int result; 531f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 532f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* we need a 60-digit number */ 533f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_init_size(&number, 60)) != MP_OKAY) \{ 534f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error initializing the number. \%s", 535f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 536f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 537f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 538f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 539f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* use the number */ 540f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 541f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_SUCCESS; 542f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\} 543f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} \end{small} 544f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 545f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Maintenance Functions} 546f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 547f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\subsection{Reducing Memory Usage} 548f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectWhen an mp\_int is in a state where it won't be changed again\footnote{A Diffie-Hellman modulus for instance.} excess 549f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectdigits can be removed to return memory to the heap with the mp\_shrink() function. 550f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 551f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_shrink} 552f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 553f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_shrink (mp_int * a); 554f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 555f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 556f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis will remove excess digits of the mp\_int $a$. If the operation fails the mp\_int should be intact without the 557f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectexcess digits being removed. Note that you can use a shrunk mp\_int in further computations, however, such operations 558f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectwill require heap operations which can be slow. It is not ideal to shrink mp\_int variables that you will further 559f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectmodify in the system (unless you are seriously low on memory). 560f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 561f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{small} \begin{alltt} 562f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint main(void) 563f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\{ 564f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_int number; 565f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int result; 566f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 567f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_init(&number)) != MP_OKAY) \{ 568f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error initializing the number. \%s", 569f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 570f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 571f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 572f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 573f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* use the number [e.g. pre-computation] */ 574f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 575f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* We're done with it for now. */ 576f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_shrink(&number)) != MP_OKAY) \{ 577f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error shrinking the number. \%s", 578f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 579f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 580f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 581f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 582f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* use it .... */ 583f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 584f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 585f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* we're done with it. */ 586f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_clear(&number); 587f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 588f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_SUCCESS; 589f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\} 590f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} \end{small} 591f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 592f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\subsection{Adding additional digits} 593f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 594f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectWithin the mp\_int structure are two parameters which control the limitations of the array of digits that represent 595f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectthe integer the mp\_int is meant to equal. The \textit{used} parameter dictates how many digits are significant, that is, 596f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectcontribute to the value of the mp\_int. The \textit{alloc} parameter dictates how many digits are currently available in 597f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectthe array. If you need to perform an operation that requires more digits you will have to mp\_grow() the mp\_int to 598f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectyour desired size. 599f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 600f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_grow} 601f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 602f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_grow (mp_int * a, int size); 603f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 604f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 605f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis will grow the array of digits of $a$ to $size$. If the \textit{alloc} parameter is already bigger than 606f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project$size$ the function will not do anything. 607f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 608f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{small} \begin{alltt} 609f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint main(void) 610f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\{ 611f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_int number; 612f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int result; 613f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 614f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_init(&number)) != MP_OKAY) \{ 615f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error initializing the number. \%s", 616f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 617f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 618f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 619f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 620f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* use the number */ 621f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 622f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* We need to add 20 digits to the number */ 623f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_grow(&number, number.alloc + 20)) != MP_OKAY) \{ 624f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error growing the number. \%s", 625f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 626f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 627f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 628f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 629f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 630f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* use the number */ 631f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 632f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* we're done with it. */ 633f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_clear(&number); 634f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 635f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_SUCCESS; 636f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\} 637f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} \end{small} 638f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 639f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\chapter{Basic Operations} 640f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Small Constants} 641f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectSetting mp\_ints to small constants is a relatively common operation. To accomodate these instances there are two 642f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectsmall constant assignment functions. The first function is used to set a single digit constant while the second sets 643f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectan ISO C style ``unsigned long'' constant. The reason for both functions is efficiency. Setting a single digit is quick but the 644f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectdomain of a digit can change (it's always at least $0 \ldots 127$). 645f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 646f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\subsection{Single Digit} 647f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 648f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectSetting a single digit can be accomplished with the following function. 649f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 650f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_set} 651f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 652f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectvoid mp_set (mp_int * a, mp_digit b); 653f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 654f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 655f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis will zero the contents of $a$ and make it represent an integer equal to the value of $b$. Note that this 656f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectfunction has a return type of \textbf{void}. It cannot cause an error so it is safe to assume the function 657f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectsucceeded. 658f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 659f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{small} \begin{alltt} 660f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint main(void) 661f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\{ 662f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_int number; 663f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int result; 664f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 665f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_init(&number)) != MP_OKAY) \{ 666f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error initializing the number. \%s", 667f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 668f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 669f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 670f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 671f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* set the number to 5 */ 672f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_set(&number, 5); 673f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 674f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* we're done with it. */ 675f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_clear(&number); 676f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 677f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_SUCCESS; 678f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\} 679f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} \end{small} 680f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 681f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\subsection{Long Constants} 682f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 683f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectTo set a constant that is the size of an ISO C ``unsigned long'' and larger than a single digit the following function 684f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectcan be used. 685f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 686f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_set\_int} 687f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 688f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_set_int (mp_int * a, unsigned long b); 689f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 690f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 691f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis will assign the value of the 32-bit variable $b$ to the mp\_int $a$. Unlike mp\_set() this function will always 692f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectaccept a 32-bit input regardless of the size of a single digit. However, since the value may span several digits 693f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectthis function can fail if it runs out of heap memory. 694f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 695f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectTo get the ``unsigned long'' copy of an mp\_int the following function can be used. 696f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 697f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_get\_int} 698f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 699f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectunsigned long mp_get_int (mp_int * a); 700f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 701f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 702f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis will return the 32 least significant bits of the mp\_int $a$. 703f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 704f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{small} \begin{alltt} 705f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint main(void) 706f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\{ 707f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_int number; 708f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int result; 709f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 710f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_init(&number)) != MP_OKAY) \{ 711f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error initializing the number. \%s", 712f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 713f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 714f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 715f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 716f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* set the number to 654321 (note this is bigger than 127) */ 717f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_set_int(&number, 654321)) != MP_OKAY) \{ 718f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error setting the value of the number. \%s", 719f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 720f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 721f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 722f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 723f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("number == \%lu", mp_get_int(&number)); 724f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 725f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* we're done with it. */ 726f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_clear(&number); 727f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 728f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_SUCCESS; 729f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\} 730f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} \end{small} 731f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 732f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis should output the following if the program succeeds. 733f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 734f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 735f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectnumber == 654321 736f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 737f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 738f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\subsection{Initialize and Setting Constants} 739f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectTo both initialize and set small constants the following two functions are available. 740f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_init\_set} \index{mp\_init\_set\_int} 741f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 742f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_init_set (mp_int * a, mp_digit b); 743f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_init_set_int (mp_int * a, unsigned long b); 744f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 745f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 746f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectBoth functions work like the previous counterparts except they first mp\_init $a$ before setting the values. 747f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 748f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 749f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint main(void) 750f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\{ 751f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_int number1, number2; 752f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int result; 753f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 754f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* initialize and set a single digit */ 755f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_init_set(&number1, 100)) != MP_OKAY) \{ 756f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error setting number1: \%s", 757f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 758f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 759f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 760f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 761f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* initialize and set a long */ 762f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_init_set_int(&number2, 1023)) != MP_OKAY) \{ 763f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error setting number2: \%s", 764f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 765f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 766f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 767f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 768f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* display */ 769f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Number1, Number2 == \%lu, \%lu", 770f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_get_int(&number1), mp_get_int(&number2)); 771f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 772f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* clear */ 773f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_clear_multi(&number1, &number2, NULL); 774f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 775f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_SUCCESS; 776f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\} 777f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 778f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 779f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectIf this program succeeds it shall output. 780f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 781f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectNumber1, Number2 == 100, 1023 782f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 783f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 784f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Comparisons} 785f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 786f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectComparisons in LibTomMath are always performed in a ``left to right'' fashion. There are three possible return codes 787f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectfor any comparison. 788f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 789f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{MP\_GT} \index{MP\_EQ} \index{MP\_LT} 790f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{figure}[here] 791f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{center} 792f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{tabular}{|c|c|} 793f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline \textbf{Result Code} & \textbf{Meaning} \\ 794f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline MP\_GT & $a > b$ \\ 795f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline MP\_EQ & $a = b$ \\ 796f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline MP\_LT & $a < b$ \\ 797f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline 798f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{tabular} 799f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{center} 800f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\caption{Comparison Codes for $a, b$} 801f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\label{fig:CMP} 802f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{figure} 803f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 804f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectIn figure \ref{fig:CMP} two integers $a$ and $b$ are being compared. In this case $a$ is said to be ``to the left'' of 805f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project$b$. 806f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 807f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\subsection{Unsigned comparison} 808f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 809f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectAn unsigned comparison considers only the digits themselves and not the associated \textit{sign} flag of the 810f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectmp\_int structures. This is analogous to an absolute comparison. The function mp\_cmp\_mag() will compare two 811f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectmp\_int variables based on their digits only. 812f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 813f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_cmp\_mag} 814f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 815f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_cmp_mag(mp_int * a, mp_int * b); 816f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 817f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis will compare $a$ to $b$ placing $a$ to the left of $b$. This function cannot fail and will return one of the 818f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectthree compare codes listed in figure \ref{fig:CMP}. 819f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 820f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{small} \begin{alltt} 821f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint main(void) 822f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\{ 823f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_int number1, number2; 824f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int result; 825f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 826f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_init_multi(&number1, &number2, NULL)) != MP_OKAY) \{ 827f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error initializing the numbers. \%s", 828f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 829f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 830f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 831f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 832f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* set the number1 to 5 */ 833f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_set(&number1, 5); 834f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 835f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* set the number2 to -6 */ 836f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_set(&number2, 6); 837f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_neg(&number2, &number2)) != MP_OKAY) \{ 838f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error negating number2. \%s", 839f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 840f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 841f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 842f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 843f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project switch(mp_cmp_mag(&number1, &number2)) \{ 844f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project case MP_GT: printf("|number1| > |number2|"); break; 845f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project case MP_EQ: printf("|number1| = |number2|"); break; 846f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project case MP_LT: printf("|number1| < |number2|"); break; 847f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 848f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 849f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* we're done with it. */ 850f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_clear_multi(&number1, &number2, NULL); 851f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 852f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_SUCCESS; 853f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\} 854f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} \end{small} 855f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 856f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectIf this program\footnote{This function uses the mp\_neg() function which is discussed in section \ref{sec:NEG}.} completes 857f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectsuccessfully it should print the following. 858f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 859f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 860f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project|number1| < |number2| 861f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 862f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 863f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis is because $\vert -6 \vert = 6$ and obviously $5 < 6$. 864f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 865f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\subsection{Signed comparison} 866f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 867f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectTo compare two mp\_int variables based on their signed value the mp\_cmp() function is provided. 868f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 869f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_cmp} 870f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 871f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_cmp(mp_int * a, mp_int * b); 872f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 873f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 874f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis will compare $a$ to the left of $b$. It will first compare the signs of the two mp\_int variables. If they 875f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectdiffer it will return immediately based on their signs. If the signs are equal then it will compare the digits 876f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectindividually. This function will return one of the compare conditions codes listed in figure \ref{fig:CMP}. 877f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 878f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{small} \begin{alltt} 879f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint main(void) 880f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\{ 881f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_int number1, number2; 882f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int result; 883f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 884f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_init_multi(&number1, &number2, NULL)) != MP_OKAY) \{ 885f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error initializing the numbers. \%s", 886f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 887f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 888f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 889f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 890f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* set the number1 to 5 */ 891f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_set(&number1, 5); 892f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 893f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* set the number2 to -6 */ 894f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_set(&number2, 6); 895f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_neg(&number2, &number2)) != MP_OKAY) \{ 896f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error negating number2. \%s", 897f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 898f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 899f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 900f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 901f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project switch(mp_cmp(&number1, &number2)) \{ 902f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project case MP_GT: printf("number1 > number2"); break; 903f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project case MP_EQ: printf("number1 = number2"); break; 904f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project case MP_LT: printf("number1 < number2"); break; 905f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 906f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 907f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* we're done with it. */ 908f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_clear_multi(&number1, &number2, NULL); 909f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 910f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_SUCCESS; 911f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\} 912f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} \end{small} 913f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 914f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectIf this program\footnote{This function uses the mp\_neg() function which is discussed in section \ref{sec:NEG}.} completes 915f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectsuccessfully it should print the following. 916f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 917f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 918f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectnumber1 > number2 919f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 920f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 921f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\subsection{Single Digit} 922f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 923f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectTo compare a single digit against an mp\_int the following function has been provided. 924f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 925f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_cmp\_d} 926f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 927f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_cmp_d(mp_int * a, mp_digit b); 928f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 929f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 930f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis will compare $a$ to the left of $b$ using a signed comparison. Note that it will always treat $b$ as 931f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectpositive. This function is rather handy when you have to compare against small values such as $1$ (which often 932f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectcomes up in cryptography). The function cannot fail and will return one of the tree compare condition codes 933f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectlisted in figure \ref{fig:CMP}. 934f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 935f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 936f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{small} \begin{alltt} 937f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint main(void) 938f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\{ 939f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_int number; 940f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int result; 941f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 942f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_init(&number)) != MP_OKAY) \{ 943f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error initializing the number. \%s", 944f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 945f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 946f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 947f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 948f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* set the number to 5 */ 949f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_set(&number, 5); 950f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 951f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project switch(mp_cmp_d(&number, 7)) \{ 952f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project case MP_GT: printf("number > 7"); break; 953f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project case MP_EQ: printf("number = 7"); break; 954f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project case MP_LT: printf("number < 7"); break; 955f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 956f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 957f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* we're done with it. */ 958f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_clear(&number); 959f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 960f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_SUCCESS; 961f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\} 962f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} \end{small} 963f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 964f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectIf this program functions properly it will print out the following. 965f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 966f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 967f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectnumber < 7 968f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 969f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 970f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Logical Operations} 971f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 972f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectLogical operations are operations that can be performed either with simple shifts or boolean operators such as 973f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectAND, XOR and OR directly. These operations are very quick. 974f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 975f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\subsection{Multiplication by two} 976f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 977f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectMultiplications and divisions by any power of two can be performed with quick logical shifts either left or 978f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectright depending on the operation. 979f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 980f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectWhen multiplying or dividing by two a special case routine can be used which are as follows. 981f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_mul\_2} \index{mp\_div\_2} 982f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 983f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_mul_2(mp_int * a, mp_int * b); 984f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_div_2(mp_int * a, mp_int * b); 985f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 986f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 987f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThe former will assign twice $a$ to $b$ while the latter will assign half $a$ to $b$. These functions are fast 988f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectsince the shift counts and maskes are hardcoded into the routines. 989f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 990f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{small} \begin{alltt} 991f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint main(void) 992f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\{ 993f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_int number; 994f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int result; 995f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 996f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_init(&number)) != MP_OKAY) \{ 997f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error initializing the number. \%s", 998f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 999f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 1000f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 1001f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1002f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* set the number to 5 */ 1003f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_set(&number, 5); 1004f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1005f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* multiply by two */ 1006f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp\_mul\_2(&number, &number)) != MP_OKAY) \{ 1007f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error multiplying the number. \%s", 1008f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 1009f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 1010f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 1011f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project switch(mp_cmp_d(&number, 7)) \{ 1012f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project case MP_GT: printf("2*number > 7"); break; 1013f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project case MP_EQ: printf("2*number = 7"); break; 1014f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project case MP_LT: printf("2*number < 7"); break; 1015f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 1016f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1017f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* now divide by two */ 1018f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp\_div\_2(&number, &number)) != MP_OKAY) \{ 1019f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error dividing the number. \%s", 1020f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 1021f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 1022f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 1023f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project switch(mp_cmp_d(&number, 7)) \{ 1024f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project case MP_GT: printf("2*number/2 > 7"); break; 1025f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project case MP_EQ: printf("2*number/2 = 7"); break; 1026f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project case MP_LT: printf("2*number/2 < 7"); break; 1027f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 1028f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1029f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* we're done with it. */ 1030f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_clear(&number); 1031f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1032f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_SUCCESS; 1033f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\} 1034f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} \end{small} 1035f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1036f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectIf this program is successful it will print out the following text. 1037f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1038f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1039f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project2*number > 7 1040f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project2*number/2 < 7 1041f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1042f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1043f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectSince $10 > 7$ and $5 < 7$. To multiply by a power of two the following function can be used. 1044f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1045f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_mul\_2d} 1046f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1047f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_mul_2d(mp_int * a, int b, mp_int * c); 1048f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1049f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1050f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis will multiply $a$ by $2^b$ and store the result in ``c''. If the value of $b$ is less than or equal to 1051f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectzero the function will copy $a$ to ``c'' without performing any further actions. 1052f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1053f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectTo divide by a power of two use the following. 1054f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1055f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_div\_2d} 1056f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1057f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_div_2d (mp_int * a, int b, mp_int * c, mp_int * d); 1058f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1059f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectWhich will divide $a$ by $2^b$, store the quotient in ``c'' and the remainder in ``d'. If $b \le 0$ then the 1060f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectfunction simply copies $a$ over to ``c'' and zeroes $d$. The variable $d$ may be passed as a \textbf{NULL} 1061f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectvalue to signal that the remainder is not desired. 1062f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1063f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\subsection{Polynomial Basis Operations} 1064f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1065f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectStrictly speaking the organization of the integers within the mp\_int structures is what is known as a 1066f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project``polynomial basis''. This simply means a field element is stored by divisions of a radix. For example, if 1067f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project$f(x) = \sum_{i=0}^{k} y_ix^k$ for any vector $\vec y$ then the array of digits in $\vec y$ are said to be 1068f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectthe polynomial basis representation of $z$ if $f(\beta) = z$ for a given radix $\beta$. 1069f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1070f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectTo multiply by the polynomial $g(x) = x$ all you have todo is shift the digits of the basis left one place. The 1071f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectfollowing function provides this operation. 1072f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1073f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_lshd} 1074f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1075f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_lshd (mp_int * a, int b); 1076f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1077f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1078f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis will multiply $a$ in place by $x^b$ which is equivalent to shifting the digits left $b$ places and inserting zeroes 1079f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectin the least significant digits. Similarly to divide by a power of $x$ the following function is provided. 1080f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1081f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_rshd} 1082f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1083f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectvoid mp_rshd (mp_int * a, int b) 1084f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1085f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis will divide $a$ in place by $x^b$ and discard the remainder. This function cannot fail as it performs the operations 1086f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectin place and no new digits are required to complete it. 1087f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1088f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\subsection{AND, OR and XOR Operations} 1089f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1090f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectWhile AND, OR and XOR operations are not typical ``bignum functions'' they can be useful in several instances. The 1091f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectthree functions are prototyped as follows. 1092f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1093f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_or} \index{mp\_and} \index{mp\_xor} 1094f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1095f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_or (mp_int * a, mp_int * b, mp_int * c); 1096f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_and (mp_int * a, mp_int * b, mp_int * c); 1097f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_xor (mp_int * a, mp_int * b, mp_int * c); 1098f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1099f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1100f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectWhich compute $c = a \odot b$ where $\odot$ is one of OR, AND or XOR. 1101f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1102f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Addition and Subtraction} 1103f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1104f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectTo compute an addition or subtraction the following two functions can be used. 1105f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1106f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_add} \index{mp\_sub} 1107f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1108f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_add (mp_int * a, mp_int * b, mp_int * c); 1109f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_sub (mp_int * a, mp_int * b, mp_int * c) 1110f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1111f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1112f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectWhich perform $c = a \odot b$ where $\odot$ is one of signed addition or subtraction. The operations are fully sign 1113f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectaware. 1114f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1115f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Sign Manipulation} 1116f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\subsection{Negation} 1117f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\label{sec:NEG} 1118f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectSimple integer negation can be performed with the following. 1119f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1120f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_neg} 1121f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1122f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_neg (mp_int * a, mp_int * b); 1123f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1124f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1125f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectWhich assigns $-a$ to $b$. 1126f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1127f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\subsection{Absolute} 1128f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectSimple integer absolutes can be performed with the following. 1129f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1130f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_neg} 1131f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1132f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_abs (mp_int * a, mp_int * b); 1133f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1134f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1135f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectWhich assigns $\vert a \vert$ to $b$. 1136f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1137f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Integer Division and Remainder} 1138f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectTo perform a complete and general integer division with remainder use the following function. 1139f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1140f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_div} 1141f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1142f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_div (mp_int * a, mp_int * b, mp_int * c, mp_int * d); 1143f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1144f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1145f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis divides $a$ by $b$ and stores the quotient in $c$ and $d$. The signed quotient is computed such that 1146f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project$bc + d = a$. Note that either of $c$ or $d$ can be set to \textbf{NULL} if their value is not required. If 1147f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project$b$ is zero the function returns \textbf{MP\_VAL}. 1148f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1149f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1150f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\chapter{Multiplication and Squaring} 1151f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Multiplication} 1152f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectA full signed integer multiplication can be performed with the following. 1153f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_mul} 1154f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1155f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_mul (mp_int * a, mp_int * b, mp_int * c); 1156f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1157f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectWhich assigns the full signed product $ab$ to $c$. This function actually breaks into one of four cases which are 1158f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectspecific multiplication routines optimized for given parameters. First there are the Toom-Cook multiplications which 1159f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectshould only be used with very large inputs. This is followed by the Karatsuba multiplications which are for moderate 1160f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectsized inputs. Then followed by the Comba and baseline multipliers. 1161f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1162f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectFortunately for the developer you don't really need to know this unless you really want to fine tune the system. mp\_mul() 1163f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectwill determine on its own\footnote{Some tweaking may be required.} what routine to use automatically when it is called. 1164f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1165f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1166f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint main(void) 1167f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\{ 1168f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_int number1, number2; 1169f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int result; 1170f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1171f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* Initialize the numbers */ 1172f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_init_multi(&number1, 1173f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project &number2, NULL)) != MP_OKAY) \{ 1174f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error initializing the numbers. \%s", 1175f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 1176f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 1177f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 1178f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1179f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* set the terms */ 1180f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_set_int(&number, 257)) != MP_OKAY) \{ 1181f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error setting number1. \%s", 1182f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 1183f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 1184f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 1185f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1186f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_set_int(&number2, 1023)) != MP_OKAY) \{ 1187f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error setting number2. \%s", 1188f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 1189f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 1190f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 1191f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1192f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* multiply them */ 1193f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_mul(&number1, &number2, 1194f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project &number1)) != MP_OKAY) \{ 1195f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error multiplying terms. \%s", 1196f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 1197f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 1198f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 1199f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1200f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* display */ 1201f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("number1 * number2 == \%lu", mp_get_int(&number1)); 1202f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1203f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* free terms and return */ 1204f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_clear_multi(&number1, &number2, NULL); 1205f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1206f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_SUCCESS; 1207f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\} 1208f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1209f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1210f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectIf this program succeeds it shall output the following. 1211f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1212f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1213f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectnumber1 * number2 == 262911 1214f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1215f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1216f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Squaring} 1217f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectSince squaring can be performed faster than multiplication it is performed it's own function instead of just using 1218f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectmp\_mul(). 1219f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1220f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_sqr} 1221f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1222f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_sqr (mp_int * a, mp_int * b); 1223f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1224f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1225f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectWill square $a$ and store it in $b$. Like the case of multiplication there are four different squaring 1226f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectalgorithms all which can be called from mp\_sqr(). It is ideal to use mp\_sqr over mp\_mul when squaring terms because 1227f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectof the speed difference. 1228f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1229f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Tuning Polynomial Basis Routines} 1230f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1231f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectBoth of the Toom-Cook and Karatsuba multiplication algorithms are faster than the traditional $O(n^2)$ approach that 1232f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectthe Comba and baseline algorithms use. At $O(n^{1.464973})$ and $O(n^{1.584962})$ running times respectively they require 1233f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectconsiderably less work. For example, a 10000-digit multiplication would take roughly 724,000 single precision 1234f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectmultiplications with Toom-Cook or 100,000,000 single precision multiplications with the standard Comba (a factor 1235f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectof 138). 1236f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1237f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectSo why not always use Karatsuba or Toom-Cook? The simple answer is that they have so much overhead that they're not 1238f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectactually faster than Comba until you hit distinct ``cutoff'' points. For Karatsuba with the default configuration, 1239f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectGCC 3.3.1 and an Athlon XP processor the cutoff point is roughly 110 digits (about 70 for the Intel P4). That is, at 1240f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project110 digits Karatsuba and Comba multiplications just about break even and for 110+ digits Karatsuba is faster. 1241f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1242f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectToom-Cook has incredible overhead and is probably only useful for very large inputs. So far no known cutoff points 1243f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectexist and for the most part I just set the cutoff points very high to make sure they're not called. 1244f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1245f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectA demo program in the ``etc/'' directory of the project called ``tune.c'' can be used to find the cutoff points. This 1246f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectcan be built with GCC as follows 1247f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1248f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1249f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectmake XXX 1250f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1251f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectWhere ``XXX'' is one of the following entries from the table \ref{fig:tuning}. 1252f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1253f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{figure}[here] 1254f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{center} 1255f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{small} 1256f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{tabular}{|l|l|} 1257f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline \textbf{Value of XXX} & \textbf{Meaning} \\ 1258f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline tune & Builds portable tuning application \\ 1259f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline tune86 & Builds x86 (pentium and up) program for COFF \\ 1260f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline tune86c & Builds x86 program for Cygwin \\ 1261f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline tune86l & Builds x86 program for Linux (ELF format) \\ 1262f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline 1263f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{tabular} 1264f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{small} 1265f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{center} 1266f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\caption{Build Names for Tuning Programs} 1267f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\label{fig:tuning} 1268f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{figure} 1269f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1270f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectWhen the program is running it will output a series of measurements for different cutoff points. It will first find 1271f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectgood Karatsuba squaring and multiplication points. Then it proceeds to find Toom-Cook points. Note that the Toom-Cook 1272f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projecttuning takes a very long time as the cutoff points are likely to be very high. 1273f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1274f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\chapter{Modular Reduction} 1275f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1276f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectModular reduction is process of taking the remainder of one quantity divided by another. Expressed 1277f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectas (\ref{eqn:mod}) the modular reduction is equivalent to the remainder of $b$ divided by $c$. 1278f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1279f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{equation} 1280f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projecta \equiv b \mbox{ (mod }c\mbox{)} 1281f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\label{eqn:mod} 1282f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{equation} 1283f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1284f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectOf particular interest to cryptography are reductions where $b$ is limited to the range $0 \le b < c^2$ since particularly 1285f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectfast reduction algorithms can be written for the limited range. 1286f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1287f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectNote that one of the four optimized reduction algorithms are automatically chosen in the modular exponentiation 1288f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectalgorithm mp\_exptmod when an appropriate modulus is detected. 1289f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1290f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Straight Division} 1291f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectIn order to effect an arbitrary modular reduction the following algorithm is provided. 1292f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1293f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_mod} 1294f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1295f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_mod(mp_int *a, mp_int *b, mp_int *c); 1296f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1297f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1298f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis reduces $a$ modulo $b$ and stores the result in $c$. The sign of $c$ shall agree with the sign 1299f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectof $b$. This algorithm accepts an input $a$ of any range and is not limited by $0 \le a < b^2$. 1300f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1301f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Barrett Reduction} 1302f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1303f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectBarrett reduction is a generic optimized reduction algorithm that requires pre--computation to achieve 1304f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projecta decent speedup over straight division. First a $\mu$ value must be precomputed with the following function. 1305f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1306f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_reduce\_setup} 1307f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1308f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_reduce_setup(mp_int *a, mp_int *b); 1309f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1310f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1311f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectGiven a modulus in $b$ this produces the required $\mu$ value in $a$. For any given modulus this only has to 1312f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectbe computed once. Modular reduction can now be performed with the following. 1313f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1314f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_reduce} 1315f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1316f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_reduce(mp_int *a, mp_int *b, mp_int *c); 1317f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1318f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1319f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis will reduce $a$ in place modulo $b$ with the precomputed $\mu$ value in $c$. $a$ must be in the range 1320f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project$0 \le a < b^2$. 1321f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1322f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1323f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint main(void) 1324f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\{ 1325f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_int a, b, c, mu; 1326f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int result; 1327f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1328f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* initialize a,b to desired values, mp_init mu, 1329f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * c and set c to 1...we want to compute a^3 mod b 1330f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project */ 1331f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1332f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* get mu value */ 1333f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_reduce_setup(&mu, b)) != MP_OKAY) \{ 1334f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error getting mu. \%s", 1335f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 1336f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 1337f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 1338f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1339f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* square a to get c = a^2 */ 1340f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_sqr(&a, &c)) != MP_OKAY) \{ 1341f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error squaring. \%s", 1342f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 1343f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 1344f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 1345f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1346f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* now reduce `c' modulo b */ 1347f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_reduce(&c, &b, &mu)) != MP_OKAY) \{ 1348f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error reducing. \%s", 1349f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 1350f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 1351f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 1352f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1353f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* multiply a to get c = a^3 */ 1354f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_mul(&a, &c, &c)) != MP_OKAY) \{ 1355f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error reducing. \%s", 1356f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 1357f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 1358f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 1359f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1360f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* now reduce `c' modulo b */ 1361f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_reduce(&c, &b, &mu)) != MP_OKAY) \{ 1362f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error reducing. \%s", 1363f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 1364f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 1365f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 1366f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1367f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* c now equals a^3 mod b */ 1368f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1369f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_SUCCESS; 1370f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\} 1371f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1372f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1373f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis program will calculate $a^3 \mbox{ mod }b$ if all the functions succeed. 1374f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1375f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Montgomery Reduction} 1376f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1377f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectMontgomery is a specialized reduction algorithm for any odd moduli. Like Barrett reduction a pre--computation 1378f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectstep is required. This is accomplished with the following. 1379f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1380f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_montgomery\_setup} 1381f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1382f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_montgomery_setup(mp_int *a, mp_digit *mp); 1383f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1384f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1385f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectFor the given odd moduli $a$ the precomputation value is placed in $mp$. The reduction is computed with the 1386f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectfollowing. 1387f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1388f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_montgomery\_reduce} 1389f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1390f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_montgomery_reduce(mp_int *a, mp_int *m, mp_digit mp); 1391f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1392f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis reduces $a$ in place modulo $m$ with the pre--computed value $mp$. $a$ must be in the range 1393f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project$0 \le a < b^2$. 1394f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1395f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectMontgomery reduction is faster than Barrett reduction for moduli smaller than the ``comba'' limit. With the default 1396f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectsetup for instance, the limit is $127$ digits ($3556$--bits). Note that this function is not limited to 1397f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project$127$ digits just that it falls back to a baseline algorithm after that point. 1398f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1399f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectAn important observation is that this reduction does not return $a \mbox{ mod }m$ but $aR^{-1} \mbox{ mod }m$ 1400f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectwhere $R = \beta^n$, $n$ is the n number of digits in $m$ and $\beta$ is radix used (default is $2^{28}$). 1401f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1402f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectTo quickly calculate $R$ the following function was provided. 1403f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1404f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_montgomery\_calc\_normalization} 1405f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1406f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_montgomery_calc_normalization(mp_int *a, mp_int *b); 1407f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1408f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectWhich calculates $a = R$ for the odd moduli $b$ without using multiplication or division. 1409f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1410f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThe normal modus operandi for Montgomery reductions is to normalize the integers before entering the system. For 1411f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectexample, to calculate $a^3 \mbox { mod }b$ using Montgomery reduction the value of $a$ can be normalized by 1412f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectmultiplying it by $R$. Consider the following code snippet. 1413f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1414f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1415f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint main(void) 1416f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\{ 1417f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_int a, b, c, R; 1418f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_digit mp; 1419f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int result; 1420f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1421f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* initialize a,b to desired values, 1422f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * mp_init R, c and set c to 1.... 1423f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project */ 1424f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1425f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* get normalization */ 1426f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_montgomery_calc_normalization(&R, b)) != MP_OKAY) \{ 1427f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error getting norm. \%s", 1428f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 1429f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 1430f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 1431f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1432f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* get mp value */ 1433f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_montgomery_setup(&c, &mp)) != MP_OKAY) \{ 1434f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error setting up montgomery. \%s", 1435f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 1436f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 1437f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 1438f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1439f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* normalize `a' so now a is equal to aR */ 1440f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_mulmod(&a, &R, &b, &a)) != MP_OKAY) \{ 1441f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error computing aR. \%s", 1442f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 1443f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 1444f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 1445f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1446f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* square a to get c = a^2R^2 */ 1447f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_sqr(&a, &c)) != MP_OKAY) \{ 1448f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error squaring. \%s", 1449f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 1450f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 1451f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 1452f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1453f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* now reduce `c' back down to c = a^2R^2 * R^-1 == a^2R */ 1454f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_montgomery_reduce(&c, &b, mp)) != MP_OKAY) \{ 1455f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error reducing. \%s", 1456f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 1457f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 1458f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 1459f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1460f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* multiply a to get c = a^3R^2 */ 1461f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_mul(&a, &c, &c)) != MP_OKAY) \{ 1462f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error reducing. \%s", 1463f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 1464f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 1465f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 1466f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1467f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* now reduce `c' back down to c = a^3R^2 * R^-1 == a^3R */ 1468f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_montgomery_reduce(&c, &b, mp)) != MP_OKAY) \{ 1469f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error reducing. \%s", 1470f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 1471f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 1472f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 1473f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1474f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* now reduce (again) `c' back down to c = a^3R * R^-1 == a^3 */ 1475f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((result = mp_montgomery_reduce(&c, &b, mp)) != MP_OKAY) \{ 1476f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Error reducing. \%s", 1477f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_error_to_string(result)); 1478f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_FAILURE; 1479f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project \} 1480f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1481f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* c now equals a^3 mod b */ 1482f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1483f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return EXIT_SUCCESS; 1484f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\} 1485f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1486f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1487f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis particular example does not look too efficient but it demonstrates the point of the algorithm. By 1488f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectnormalizing the inputs the reduced results are always of the form $aR$ for some variable $a$. This allows 1489f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projecta single final reduction to correct for the normalization and the fast reduction used within the algorithm. 1490f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1491f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectFor more details consider examining the file \textit{bn\_mp\_exptmod\_fast.c}. 1492f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1493f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Restricted Dimminished Radix} 1494f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1495f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project``Dimminished Radix'' reduction refers to reduction with respect to moduli that are ameniable to simple 1496f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectdigit shifting and small multiplications. In this case the ``restricted'' variant refers to moduli of the 1497f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectform $\beta^k - p$ for some $k \ge 0$ and $0 < p < \beta$ where $\beta$ is the radix (default to $2^{28}$). 1498f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1499f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectAs in the case of Montgomery reduction there is a pre--computation phase required for a given modulus. 1500f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1501f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_dr\_setup} 1502f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1503f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectvoid mp_dr_setup(mp_int *a, mp_digit *d); 1504f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1505f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1506f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis computes the value required for the modulus $a$ and stores it in $d$. This function cannot fail 1507f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectand does not return any error codes. After the pre--computation a reduction can be performed with the 1508f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectfollowing. 1509f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1510f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_dr\_reduce} 1511f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1512f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_dr_reduce(mp_int *a, mp_int *b, mp_digit mp); 1513f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1514f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1515f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis reduces $a$ in place modulo $b$ with the pre--computed value $mp$. $b$ must be of a restricted 1516f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectdimminished radix form and $a$ must be in the range $0 \le a < b^2$. Dimminished radix reductions are 1517f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectmuch faster than both Barrett and Montgomery reductions as they have a much lower asymtotic running time. 1518f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1519f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectSince the moduli are restricted this algorithm is not particularly useful for something like Rabin, RSA or 1520f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectBBS cryptographic purposes. This reduction algorithm is useful for Diffie-Hellman and ECC where fixed 1521f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectprimes are acceptable. 1522f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1523f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectNote that unlike Montgomery reduction there is no normalization process. The result of this function is 1524f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectequal to the correct residue. 1525f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1526f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Unrestricted Dimminshed Radix} 1527f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1528f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectUnrestricted reductions work much like the restricted counterparts except in this case the moduli is of the 1529f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectform $2^k - p$ for $0 < p < \beta$. In this sense the unrestricted reductions are more flexible as they 1530f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectcan be applied to a wider range of numbers. 1531f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1532f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_reduce\_2k\_setup} 1533f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1534f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_reduce_2k_setup(mp_int *a, mp_digit *d); 1535f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1536f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1537f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis will compute the required $d$ value for the given moduli $a$. 1538f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1539f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_reduce\_2k} 1540f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1541f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_reduce_2k(mp_int *a, mp_int *n, mp_digit d); 1542f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1543f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1544f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis will reduce $a$ in place modulo $n$ with the pre--computed value $d$. From my experience this routine is 1545f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectslower than mp\_dr\_reduce but faster for most moduli sizes than the Montgomery reduction. 1546f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1547f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\chapter{Exponentiation} 1548f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Single Digit Exponentiation} 1549f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_expt\_d} 1550f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1551f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_expt_d (mp_int * a, mp_digit b, mp_int * c) 1552f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1553f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis computes $c = a^b$ using a simple binary left-to-right algorithm. It is faster than repeated multiplications by 1554f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project$a$ for all values of $b$ greater than three. 1555f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1556f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Modular Exponentiation} 1557f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_exptmod} 1558f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1559f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y) 1560f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1561f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis computes $Y \equiv G^X \mbox{ (mod }P\mbox{)}$ using a variable width sliding window algorithm. This function 1562f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectwill automatically detect the fastest modular reduction technique to use during the operation. For negative values of 1563f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project$X$ the operation is performed as $Y \equiv (G^{-1} \mbox{ mod }P)^{\vert X \vert} \mbox{ (mod }P\mbox{)}$ provided that 1564f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project$gcd(G, P) = 1$. 1565f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1566f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis function is actually a shell around the two internal exponentiation functions. This routine will automatically 1567f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectdetect when Barrett, Montgomery, Restricted and Unrestricted Dimminished Radix based exponentiation can be used. Generally 1568f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectmoduli of the a ``restricted dimminished radix'' form lead to the fastest modular exponentiations. Followed by Montgomery 1569f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectand the other two algorithms. 1570f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1571f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Root Finding} 1572f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_n\_root} 1573f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1574f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_n_root (mp_int * a, mp_digit b, mp_int * c) 1575f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1576f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis computes $c = a^{1/b}$ such that $c^b \le a$ and $(c+1)^b > a$. The implementation of this function is not 1577f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectideal for values of $b$ greater than three. It will work but become very slow. So unless you are working with very small 1578f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectnumbers (less than 1000 bits) I'd avoid $b > 3$ situations. Will return a positive root only for even roots and return 1579f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projecta root with the sign of the input for odd roots. For example, performing $4^{1/2}$ will return $2$ whereas $(-8)^{1/3}$ 1580f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectwill return $-2$. 1581f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1582f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis algorithm uses the ``Newton Approximation'' method and will converge on the correct root fairly quickly. Since 1583f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectthe algorithm requires raising $a$ to the power of $b$ it is not ideal to attempt to find roots for large 1584f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectvalues of $b$. If particularly large roots are required then a factor method could be used instead. For example, 1585f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project$a^{1/16}$ is equivalent to $\left (a^{1/4} \right)^{1/4}$ or simply 1586f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project$\left ( \left ( \left ( a^{1/2} \right )^{1/2} \right )^{1/2} \right )^{1/2}$ 1587f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1588f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\chapter{Prime Numbers} 1589f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Trial Division} 1590f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_prime\_is\_divisible} 1591f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1592f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_prime_is_divisible (mp_int * a, int *result) 1593f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1594f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis will attempt to evenly divide $a$ by a list of primes\footnote{Default is the first 256 primes.} and store the 1595f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectoutcome in ``result''. That is if $result = 0$ then $a$ is not divisible by the primes, otherwise it is. Note that 1596f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectif the function does not return \textbf{MP\_OKAY} the value in ``result'' should be considered undefined\footnote{Currently 1597f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectthe default is to set it to zero first.}. 1598f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1599f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Fermat Test} 1600f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_prime\_fermat} 1601f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1602f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_prime_fermat (mp_int * a, mp_int * b, int *result) 1603f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1604f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectPerforms a Fermat primality test to the base $b$. That is it computes $b^a \mbox{ mod }a$ and tests whether the value is 1605f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectequal to $b$ or not. If the values are equal then $a$ is probably prime and $result$ is set to one. Otherwise $result$ 1606f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectis set to zero. 1607f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1608f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Miller-Rabin Test} 1609f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_prime\_miller\_rabin} 1610f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1611f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_prime_miller_rabin (mp_int * a, mp_int * b, int *result) 1612f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1613f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectPerforms a Miller-Rabin test to the base $b$ of $a$. This test is much stronger than the Fermat test and is very hard to 1614f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectfool (besides with Carmichael numbers). If $a$ passes the test (therefore is probably prime) $result$ is set to one. 1615f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectOtherwise $result$ is set to zero. 1616f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1617f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectNote that is suggested that you use the Miller-Rabin test instead of the Fermat test since all of the failures of 1618f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectMiller-Rabin are a subset of the failures of the Fermat test. 1619f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1620f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\subsection{Required Number of Tests} 1621f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectGenerally to ensure a number is very likely to be prime you have to perform the Miller-Rabin with at least a half-dozen 1622f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projector so unique bases. However, it has been proven that the probability of failure goes down as the size of the input goes up. 1623f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis is why a simple function has been provided to help out. 1624f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1625f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_prime\_rabin\_miller\_trials} 1626f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1627f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_prime_rabin_miller_trials(int size) 1628f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1629f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis returns the number of trials required for a $2^{-96}$ (or lower) probability of failure for a given ``size'' expressed 1630f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectin bits. This comes in handy specially since larger numbers are slower to test. For example, a 512-bit number would 1631f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectrequire ten tests whereas a 1024-bit number would only require four tests. 1632f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1633f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectYou should always still perform a trial division before a Miller-Rabin test though. 1634f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1635f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Primality Testing} 1636f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_prime\_is\_prime} 1637f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1638f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_prime_is_prime (mp_int * a, int t, int *result) 1639f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1640f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis will perform a trial division followed by $t$ rounds of Miller-Rabin tests on $a$ and store the result in $result$. 1641f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectIf $a$ passes all of the tests $result$ is set to one, otherwise it is set to zero. Note that $t$ is bounded by 1642f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project$1 \le t < PRIME\_SIZE$ where $PRIME\_SIZE$ is the number of primes in the prime number table (by default this is $256$). 1643f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1644f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Next Prime} 1645f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_prime\_next\_prime} 1646f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1647f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_prime_next_prime(mp_int *a, int t, int bbs_style) 1648f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1649f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis finds the next prime after $a$ that passes mp\_prime\_is\_prime() with $t$ tests. Set $bbs\_style$ to one if you 1650f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectwant only the next prime congruent to $3 \mbox{ mod } 4$, otherwise set it to zero to find any next prime. 1651f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1652f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Random Primes} 1653f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_prime\_random} 1654f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1655f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_prime_random(mp_int *a, int t, int size, int bbs, 1656f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project ltm_prime_callback cb, void *dat) 1657f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1658f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis will find a prime greater than $256^{size}$ which can be ``bbs\_style'' or not depending on $bbs$ and must pass 1659f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project$t$ rounds of tests. The ``ltm\_prime\_callback'' is a typedef for 1660f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1661f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1662f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projecttypedef int ltm_prime_callback(unsigned char *dst, int len, void *dat); 1663f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1664f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1665f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectWhich is a function that must read $len$ bytes (and return the amount stored) into $dst$. The $dat$ variable is simply 1666f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectcopied from the original input. It can be used to pass RNG context data to the callback. The function 1667f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectmp\_prime\_random() is more suitable for generating primes which must be secret (as in the case of RSA) since there 1668f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectis no skew on the least significant bits. 1669f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1670f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\textit{Note:} As of v0.30 of the LibTomMath library this function has been deprecated. It is still available 1671f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectbut users are encouraged to use the new mp\_prime\_random\_ex() function instead. 1672f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1673f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\subsection{Extended Generation} 1674f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_prime\_random\_ex} 1675f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1676f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_prime_random_ex(mp_int *a, int t, 1677f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int size, int flags, 1678f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project ltm_prime_callback cb, void *dat); 1679f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1680f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis will generate a prime in $a$ using $t$ tests of the primality testing algorithms. The variable $size$ 1681f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectspecifies the bit length of the prime desired. The variable $flags$ specifies one of several options available 1682f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project(see fig. \ref{fig:primeopts}) which can be OR'ed together. The callback parameters are used as in 1683f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectmp\_prime\_random(). 1684f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1685f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{figure}[here] 1686f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{center} 1687f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{small} 1688f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{tabular}{|r|l|} 1689f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline \textbf{Flag} & \textbf{Meaning} \\ 1690f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline LTM\_PRIME\_BBS & Make the prime congruent to $3$ modulo $4$ \\ 1691f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline LTM\_PRIME\_SAFE & Make a prime $p$ such that $(p - 1)/2$ is also prime. \\ 1692f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project & This option implies LTM\_PRIME\_BBS as well. \\ 1693f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline LTM\_PRIME\_2MSB\_OFF & Makes sure that the bit adjacent to the most significant bit \\ 1694f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project & Is forced to zero. \\ 1695f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline LTM\_PRIME\_2MSB\_ON & Makes sure that the bit adjacent to the most significant bit \\ 1696f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project & Is forced to one. \\ 1697f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\hline 1698f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{tabular} 1699f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{small} 1700f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{center} 1701f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\caption{Primality Generation Options} 1702f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\label{fig:primeopts} 1703f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{figure} 1704f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1705f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\chapter{Input and Output} 1706f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{ASCII Conversions} 1707f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\subsection{To ASCII} 1708f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_toradix} 1709f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1710f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_toradix (mp_int * a, char *str, int radix); 1711f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1712f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis still store $a$ in ``str'' as a base-``radix'' string of ASCII chars. This function appends a NUL character 1713f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectto terminate the string. Valid values of ``radix'' line in the range $[2, 64]$. To determine the size (exact) required 1714f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectby the conversion before storing any data use the following function. 1715f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1716f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_radix\_size} 1717f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1718f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_radix_size (mp_int * a, int radix, int *size) 1719f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1720f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis stores in ``size'' the number of characters (including space for the NUL terminator) required. Upon error this 1721f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectfunction returns an error code and ``size'' will be zero. 1722f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1723f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\subsection{From ASCII} 1724f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_read\_radix} 1725f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1726f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_read_radix (mp_int * a, char *str, int radix); 1727f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1728f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis will read the base-``radix'' NUL terminated string from ``str'' into $a$. It will stop reading when it reads a 1729f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectcharacter it does not recognize (which happens to include th NUL char... imagine that...). A single leading $-$ sign 1730f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectcan be used to denote a negative number. 1731f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1732f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Binary Conversions} 1733f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1734f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectConverting an mp\_int to and from binary is another keen idea. 1735f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1736f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_unsigned\_bin\_size} 1737f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1738f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_unsigned_bin_size(mp_int *a); 1739f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1740f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1741f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis will return the number of bytes (octets) required to store the unsigned copy of the integer $a$. 1742f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1743f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_to\_unsigned\_bin} 1744f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1745f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_to_unsigned_bin(mp_int *a, unsigned char *b); 1746f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1747f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis will store $a$ into the buffer $b$ in big--endian format. Fortunately this is exactly what DER (or is it ASN?) 1748f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectrequires. It does not store the sign of the integer. 1749f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1750f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_read\_unsigned\_bin} 1751f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1752f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_read_unsigned_bin(mp_int *a, unsigned char *b, int c); 1753f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1754f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis will read in an unsigned big--endian array of bytes (octets) from $b$ of length $c$ into $a$. The resulting 1755f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectinteger $a$ will always be positive. 1756f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1757f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectFor those who acknowledge the existence of negative numbers (heretic!) there are ``signed'' versions of the 1758f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectprevious functions. 1759f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1760f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1761f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_signed_bin_size(mp_int *a); 1762f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_read_signed_bin(mp_int *a, unsigned char *b, int c); 1763f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_to_signed_bin(mp_int *a, unsigned char *b); 1764f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1765f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThey operate essentially the same as the unsigned copies except they prefix the data with zero or non--zero 1766f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectbyte depending on the sign. If the sign is zpos (e.g. not negative) the prefix is zero, otherwise the prefix 1767f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectis non--zero. 1768f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1769f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\chapter{Algebraic Functions} 1770f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Extended Euclidean Algorithm} 1771f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_exteuclid} 1772f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1773f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_exteuclid(mp_int *a, mp_int *b, 1774f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_int *U1, mp_int *U2, mp_int *U3); 1775f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1776f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1777f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis finds the triple U1/U2/U3 using the Extended Euclidean algorithm such that the following equation holds. 1778f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1779f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{equation} 1780f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projecta \cdot U1 + b \cdot U2 = U3 1781f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{equation} 1782f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1783f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectAny of the U1/U2/U3 paramters can be set to \textbf{NULL} if they are not desired. 1784f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1785f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Greatest Common Divisor} 1786f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_gcd} 1787f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1788f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_gcd (mp_int * a, mp_int * b, mp_int * c) 1789f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1790f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis will compute the greatest common divisor of $a$ and $b$ and store it in $c$. 1791f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1792f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Least Common Multiple} 1793f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_lcm} 1794f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1795f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_lcm (mp_int * a, mp_int * b, mp_int * c) 1796f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1797f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis will compute the least common multiple of $a$ and $b$ and store it in $c$. 1798f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1799f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Jacobi Symbol} 1800f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_jacobi} 1801f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1802f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_jacobi (mp_int * a, mp_int * p, int *c) 1803f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1804f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThis will compute the Jacobi symbol for $a$ with respect to $p$. If $p$ is prime this essentially computes the Legendre 1805f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectsymbol. The result is stored in $c$ and can take on one of three values $\lbrace -1, 0, 1 \rbrace$. If $p$ is prime 1806f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectthen the result will be $-1$ when $a$ is not a quadratic residue modulo $p$. The result will be $0$ if $a$ divides $p$ 1807f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectand the result will be $1$ if $a$ is a quadratic residue modulo $p$. 1808f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1809f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Modular Inverse} 1810f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_invmod} 1811f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1812f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_invmod (mp_int * a, mp_int * b, mp_int * c) 1813f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1814f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectComputes the multiplicative inverse of $a$ modulo $b$ and stores the result in $c$ such that $ac \equiv 1 \mbox{ (mod }b\mbox{)}$. 1815f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1816f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\section{Single Digit Functions} 1817f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1818f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectFor those using small numbers (\textit{snicker snicker}) there are several ``helper'' functions 1819f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1820f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\index{mp\_add\_d} \index{mp\_sub\_d} \index{mp\_mul\_d} \index{mp\_div\_d} \index{mp\_mod\_d} 1821f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\begin{alltt} 1822f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_add_d(mp_int *a, mp_digit b, mp_int *c); 1823f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_sub_d(mp_int *a, mp_digit b, mp_int *c); 1824f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_mul_d(mp_int *a, mp_digit b, mp_int *c); 1825f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_div_d(mp_int *a, mp_digit b, mp_int *c, mp_digit *d); 1826f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_mod_d(mp_int *a, mp_digit b, mp_digit *c); 1827f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{alltt} 1828f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1829f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectThese work like the full mp\_int capable variants except the second parameter $b$ is a mp\_digit. These 1830f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectfunctions fairly handy if you have to work with relatively small numbers since you will not have to allocate 1831f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectan entire mp\_int to store a number like $1$ or $2$. 1832f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1833f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\input{bn.ind} 1834f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1835f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project\end{document} 1836