annotate tommath.src @ 142:d29b64170cf0 libtommath-orig

import of libtommath 0.32
author Matt Johnston <matt@ucc.asn.au>
date Sun, 19 Dec 2004 11:33:56 +0000
parents e1037a1e12e7
children d8254fc979e9
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
19
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1 \documentclass[b5paper]{book}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
2 \usepackage{hyperref}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
3 \usepackage{makeidx}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
4 \usepackage{amssymb}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
5 \usepackage{color}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
6 \usepackage{alltt}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
7 \usepackage{graphicx}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
8 \usepackage{layout}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
9 \def\union{\cup}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
10 \def\intersect{\cap}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
11 \def\getsrandom{\stackrel{\rm R}{\gets}}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
12 \def\cross{\times}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
13 \def\cat{\hspace{0.5em} \| \hspace{0.5em}}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
14 \def\catn{$\|$}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
15 \def\divides{\hspace{0.3em} | \hspace{0.3em}}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
16 \def\nequiv{\not\equiv}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
17 \def\approx{\raisebox{0.2ex}{\mbox{\small $\sim$}}}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
18 \def\lcm{{\rm lcm}}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
19 \def\gcd{{\rm gcd}}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
20 \def\log{{\rm log}}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
21 \def\ord{{\rm ord}}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
22 \def\abs{{\mathit abs}}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
23 \def\rep{{\mathit rep}}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
24 \def\mod{{\mathit\ mod\ }}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
25 \renewcommand{\pmod}[1]{\ ({\rm mod\ }{#1})}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
26 \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
27 \newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
28 \def\Or{{\rm\ or\ }}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
29 \def\And{{\rm\ and\ }}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
30 \def\iff{\hspace{1em}\Longleftrightarrow\hspace{1em}}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
31 \def\implies{\Rightarrow}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
32 \def\undefined{{\rm ``undefined"}}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
33 \def\Proof{\vspace{1ex}\noindent {\bf Proof:}\hspace{1em}}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
34 \let\oldphi\phi
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
35 \def\phi{\varphi}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
36 \def\Pr{{\rm Pr}}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
37 \newcommand{\str}[1]{{\mathbf{#1}}}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
38 \def\F{{\mathbb F}}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
39 \def\N{{\mathbb N}}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
40 \def\Z{{\mathbb Z}}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
41 \def\R{{\mathbb R}}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
42 \def\C{{\mathbb C}}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
43 \def\Q{{\mathbb Q}}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
44 \definecolor{DGray}{gray}{0.5}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
45 \newcommand{\emailaddr}[1]{\mbox{$<${#1}$>$}}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
46 \def\twiddle{\raisebox{0.3ex}{\mbox{\tiny $\sim$}}}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
47 \def\gap{\vspace{0.5ex}}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
48 \makeindex
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
49 \begin{document}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
50 \frontmatter
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
51 \pagestyle{empty}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
52 \title{Implementing Multiple Precision Arithmetic \\ ~ \\ Draft Edition }
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
53 \author{\mbox{
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
54 %\begin{small}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
55 \begin{tabular}{c}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
56 Tom St Denis \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
57 Algonquin College \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
58 \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
59 Mads Rasmussen \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
60 Open Communications Security \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
61 \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
62 Greg Rose \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
63 QUALCOMM Australia \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
64 \end{tabular}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
65 %\end{small}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
66 }
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
67 }
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
68 \maketitle
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
69 This text has been placed in the public domain. This text corresponds to the v0.30 release of the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
70 LibTomMath project.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
71
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
72 \begin{alltt}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
73 Tom St Denis
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
74 111 Banning Rd
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
75 Ottawa, Ontario
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
76 K2L 1C3
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
77 Canada
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
78
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
79 Phone: 1-613-836-3160
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
80 Email: [email protected]
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
81 \end{alltt}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
82
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
83 This text is formatted to the international B5 paper size of 176mm wide by 250mm tall using the \LaTeX{}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
84 {\em book} macro package and the Perl {\em booker} package.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
85
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
86 \tableofcontents
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
87 \listoffigures
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
88 \chapter*{Prefaces to the Draft Edition}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
89 I started this text in April 2003 to complement my LibTomMath library. That is, explain how to implement the functions
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
90 contained in LibTomMath. The goal is to have a textbook that any Computer Science student can use when implementing their
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
91 own multiple precision arithmetic. The plan I wanted to follow was flesh out all the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
92 ideas and concepts I had floating around in my head and then work on it afterwards refining a little bit at a time. Chance
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
93 would have it that I ended up with my summer off from Algonquin College and I was given four months solid to work on the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
94 text.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
95
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
96 Choosing to not waste any time I dove right into the project even before my spring semester was finished. I wrote a bit
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
97 off and on at first. The moment my exams were finished I jumped into long 12 to 16 hour days. The result after only
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
98 a couple of months was a ten chapter, three hundred page draft that I quickly had distributed to anyone who wanted
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
99 to read it. I had Jean-Luc Cooke print copies for me and I brought them to Crypto'03 in Santa Barbara. So far I have
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
100 managed to grab a certain level of attention having people from around the world ask me for copies of the text was certain
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
101 rewarding.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
102
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
103 Now we are past December 2003. By this time I had pictured that I would have at least finished my second draft of the text.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
104 Currently I am far off from this goal. I've done partial re-writes of chapters one, two and three but they are not even
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
105 finished yet. I haven't given up on the project, only had some setbacks. First O'Reilly declined to publish the text then
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
106 Addison-Wesley and Greg is tried another which I don't know the name of. However, at this point I want to focus my energy
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
107 onto finishing the book not securing a contract.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
108
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
109 So why am I writing this text? It seems like a lot of work right? Most certainly it is a lot of work writing a textbook.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
110 Even the simplest introductory material has to be lined with references and figures. A lot of the text has to be re-written
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
111 from point form to prose form to ensure an easier read. Why am I doing all this work for free then? Simple. My philosophy
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
112 is quite simply ``Open Source. Open Academia. Open Minds'' which means that to achieve a goal of open minds, that is,
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
113 people willing to accept new ideas and explore the unknown you have to make available material they can access freely
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
114 without hinderance.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
115
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
116 I've been writing free software since I was about sixteen but only recently have I hit upon software that people have come
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
117 to depend upon. I started LibTomCrypt in December 2001 and now several major companies use it as integral portions of their
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
118 software. Several educational institutions use it as a matter of course and many freelance developers use it as
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
119 part of their projects. To further my contributions I started the LibTomMath project in December 2002 aimed at providing
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
120 multiple precision arithmetic routines that students could learn from. That is write routines that are not only easy
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
121 to understand and follow but provide quite impressive performance considering they are all in standard portable ISO C.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
122
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
123 The second leg of my philosophy is ``Open Academia'' which is where this textbook comes in. In the end, when all is
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
124 said and done the text will be useable by educational institutions as a reference on multiple precision arithmetic.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
125
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
126 At this time I feel I should share a little information about myself. The most common question I was asked at
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
127 Crypto'03, perhaps just out of professional courtesy, was which school I either taught at or attended. The unfortunate
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
128 truth is that I neither teach at or attend a school of academic reputation. I'm currently at Algonquin College which
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
129 is what I'd like to call ``somewhat academic but mostly vocational'' college. In otherwords, job training.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
130
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
131 I'm a 21 year old computer science student mostly self-taught in the areas I am aware of (which includes a half-dozen
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
132 computer science fields, a few fields of mathematics and some English). I look forward to teaching someday but I am
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
133 still far off from that goal.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
134
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
135 Now it would be improper for me to not introduce the rest of the texts co-authors. While they are only contributing
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
136 corrections and editorial feedback their support has been tremendously helpful in presenting the concepts laid out
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
137 in the text so far. Greg has always been there for me. He has tracked my LibTom projects since their inception and even
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
138 sent cheques to help pay tuition from time to time. His background has provided a wonderful source to bounce ideas off
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
139 of and improve the quality of my writing. Mads is another fellow who has just ``been there''. I don't even recall what
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
140 his interest in the LibTom projects is but I'm definitely glad he has been around. His ability to catch logical errors
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
141 in my written English have saved me on several occasions to say the least.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
142
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
143 What to expect next? Well this is still a rough draft. I've only had the chance to update a few chapters. However, I've
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
144 been getting the feeling that people are starting to use my text and I owe them some updated material. My current tenative
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
145 plan is to edit one chapter every two weeks starting January 4th. It seems insane but my lower course load at college
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
146 should provide ample time. By Crypto'04 I plan to have a 2nd draft of the text polished and ready to hand out to as many
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
147 people who will take it.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
148
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
149 \begin{flushright} Tom St Denis \end{flushright}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
150
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
151 \newpage
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
152 I found the opportunity to work with Tom appealing for several reasons, not only could I broaden my own horizons, but also
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
153 contribute to educate others facing the problem of having to handle big number mathematical calculations.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
154
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
155 This book is Tom's child and he has been caring and fostering the project ever since the beginning with a clear mind of
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
156 how he wanted the project to turn out. I have helped by proofreading the text and we have had several discussions about
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
157 the layout and language used.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
158
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
159 I hold a masters degree in cryptography from the University of Southern Denmark and have always been interested in the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
160 practical aspects of cryptography.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
161
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
162 Having worked in the security consultancy business for several years in S\~{a}o Paulo, Brazil, I have been in touch with a
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
163 great deal of work in which multiple precision mathematics was needed. Understanding the possibilities for speeding up
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
164 multiple precision calculations is often very important since we deal with outdated machine architecture where modular
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
165 reductions, for example, become painfully slow.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
166
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
167 This text is for people who stop and wonder when first examining algorithms such as RSA for the first time and asks
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
168 themselves, ``You tell me this is only secure for large numbers, fine; but how do you implement these numbers?''
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
169
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
170 \begin{flushright}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
171 Mads Rasmussen
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
172
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
173 S\~{a}o Paulo - SP
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
174
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
175 Brazil
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
176 \end{flushright}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
177
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
178 \newpage
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
179 It's all because I broke my leg. That just happened to be at about the same time that Tom asked for someone to review the section of the book about
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
180 Karatsuba multiplication. I was laid up, alone and immobile, and thought ``Why not?'' I vaguely knew what Karatsuba multiplication was, but not
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
181 really, so I thought I could help, learn, and stop myself from watching daytime cable TV, all at once.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
182
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
183 At the time of writing this, I've still not met Tom or Mads in meatspace. I've been following Tom's progress since his first splash on the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
184 sci.crypt Usenet news group. I watched him go from a clueless newbie, to the cryptographic equivalent of a reformed smoker, to a real
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
185 contributor to the field, over a period of about two years. I've been impressed with his obvious intelligence, and astounded by his productivity.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
186 Of course, he's young enough to be my own child, so he doesn't have my problems with staying awake.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
187
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
188 When I reviewed that single section of the book, in its very earliest form, I was very pleasantly surprised. So I decided to collaborate more fully,
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
189 and at least review all of it, and perhaps write some bits too. There's still a long way to go with it, and I have watched a number of close
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
190 friends go through the mill of publication, so I think that the way to go is longer than Tom thinks it is. Nevertheless, it's a good effort,
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
191 and I'm pleased to be involved with it.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
192
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
193 \begin{flushright}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
194 Greg Rose, Sydney, Australia, June 2003.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
195 \end{flushright}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
196
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
197 \mainmatter
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
198 \pagestyle{headings}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
199 \chapter{Introduction}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
200 \section{Multiple Precision Arithmetic}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
201
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
202 \subsection{What is Multiple Precision Arithmetic?}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
203 When we think of long-hand arithmetic such as addition or multiplication we rarely consider the fact that we instinctively
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
204 raise or lower the precision of the numbers we are dealing with. For example, in decimal we almost immediate can
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
205 reason that $7$ times $6$ is $42$. However, $42$ has two digits of precision as opposed to one digit we started with.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
206 Further multiplications of say $3$ result in a larger precision result $126$. In these few examples we have multiple
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
207 precisions for the numbers we are working with. Despite the various levels of precision a single subset\footnote{With the occasional optimization.}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
208 of algorithms can be designed to accomodate them.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
209
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
210 By way of comparison a fixed or single precision operation would lose precision on various operations. For example, in
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
211 the decimal system with fixed precision $6 \cdot 7 = 2$.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
212
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
213 Essentially at the heart of computer based multiple precision arithmetic are the same long-hand algorithms taught in
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
214 schools to manually add, subtract, multiply and divide.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
215
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
216 \subsection{The Need for Multiple Precision Arithmetic}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
217 The most prevalent need for multiple precision arithmetic, often referred to as ``bignum'' math, is within the implementation
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
218 of public-key cryptography algorithms. Algorithms such as RSA \cite{RSAREF} and Diffie-Hellman \cite{DHREF} require
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
219 integers of significant magnitude to resist known cryptanalytic attacks. For example, at the time of this writing a
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
220 typical RSA modulus would be at least greater than $10^{309}$. However, modern programming languages such as ISO C \cite{ISOC} and
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
221 Java \cite{JAVA} only provide instrinsic support for integers which are relatively small and single precision.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
222
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
223 \begin{figure}[!here]
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
224 \begin{center}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
225 \begin{tabular}{|r|c|}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
226 \hline \textbf{Data Type} & \textbf{Range} \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
227 \hline char & $-128 \ldots 127$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
228 \hline short & $-32768 \ldots 32767$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
229 \hline long & $-2147483648 \ldots 2147483647$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
230 \hline long long & $-9223372036854775808 \ldots 9223372036854775807$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
231 \hline
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
232 \end{tabular}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
233 \end{center}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
234 \caption{Typical Data Types for the C Programming Language}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
235 \label{fig:ISOC}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
236 \end{figure}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
237
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
238 The largest data type guaranteed to be provided by the ISO C programming
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
239 language\footnote{As per the ISO C standard. However, each compiler vendor is allowed to augment the precision as they
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
240 see fit.} can only represent values up to $10^{19}$ as shown in figure \ref{fig:ISOC}. On its own the C language is
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
241 insufficient to accomodate the magnitude required for the problem at hand. An RSA modulus of magnitude $10^{19}$ could be
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
242 trivially factored\footnote{A Pollard-Rho factoring would take only $2^{16}$ time.} on the average desktop computer,
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
243 rendering any protocol based on the algorithm insecure. Multiple precision algorithms solve this very problem by
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
244 extending the range of representable integers while using single precision data types.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
245
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
246 Most advancements in fast multiple precision arithmetic stem from the need for faster and more efficient cryptographic
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
247 primitives. Faster modular reduction and exponentiation algorithms such as Barrett's algorithm, which have appeared in
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
248 various cryptographic journals, can render algorithms such as RSA and Diffie-Hellman more efficient. In fact, several
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
249 major companies such as RSA Security, Certicom and Entrust have built entire product lines on the implementation and
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
250 deployment of efficient algorithms.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
251
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
252 However, cryptography is not the only field of study that can benefit from fast multiple precision integer routines.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
253 Another auxiliary use of multiple precision integers is high precision floating point data types.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
254 The basic IEEE \cite{IEEE} standard floating point type is made up of an integer mantissa $q$, an exponent $e$ and a sign bit $s$.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
255 Numbers are given in the form $n = q \cdot b^e \cdot -1^s$ where $b = 2$ is the most common base for IEEE. Since IEEE
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
256 floating point is meant to be implemented in hardware the precision of the mantissa is often fairly small
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
257 (\textit{23, 48 and 64 bits}). The mantissa is merely an integer and a multiple precision integer could be used to create
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
258 a mantissa of much larger precision than hardware alone can efficiently support. This approach could be useful where
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
259 scientific applications must minimize the total output error over long calculations.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
260
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
261 Yet another use for large integers is within arithmetic on polynomials of large characteristic (i.e. $GF(p)[x]$ for large $p$).
19
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
262 In fact the library discussed within this text has already been used to form a polynomial basis library\footnote{See \url{http://poly.libtomcrypt.org} for more details.}.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
263
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
264 \subsection{Benefits of Multiple Precision Arithmetic}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
265 \index{precision}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
266 The benefit of multiple precision representations over single or fixed precision representations is that
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
267 no precision is lost while representing the result of an operation which requires excess precision. For example,
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
268 the product of two $n$-bit integers requires at least $2n$ bits of precision to be represented faithfully. A multiple
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
269 precision algorithm would augment the precision of the destination to accomodate the result while a single precision system
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
270 would truncate excess bits to maintain a fixed level of precision.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
271
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
272 It is possible to implement algorithms which require large integers with fixed precision algorithms. For example, elliptic
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
273 curve cryptography (\textit{ECC}) is often implemented on smartcards by fixing the precision of the integers to the maximum
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
274 size the system will ever need. Such an approach can lead to vastly simpler algorithms which can accomodate the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
275 integers required even if the host platform cannot natively accomodate them\footnote{For example, the average smartcard
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
276 processor has an 8 bit accumulator.}. However, as efficient as such an approach may be, the resulting source code is not
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
277 normally very flexible. It cannot, at runtime, accomodate inputs of higher magnitude than the designer anticipated.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
278
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
279 Multiple precision algorithms have the most overhead of any style of arithmetic. For the the most part the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
280 overhead can be kept to a minimum with careful planning, but overall, it is not well suited for most memory starved
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
281 platforms. However, multiple precision algorithms do offer the most flexibility in terms of the magnitude of the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
282 inputs. That is, the same algorithms based on multiple precision integers can accomodate any reasonable size input
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
283 without the designer's explicit forethought. This leads to lower cost of ownership for the code as it only has to
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
284 be written and tested once.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
285
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
286 \section{Purpose of This Text}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
287 The purpose of this text is to instruct the reader regarding how to implement efficient multiple precision algorithms.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
288 That is to not only explain a limited subset of the core theory behind the algorithms but also the various ``house keeping''
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
289 elements that are neglected by authors of other texts on the subject. Several well reknowned texts \cite{TAOCPV2,HAC}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
290 give considerably detailed explanations of the theoretical aspects of algorithms and often very little information
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
291 regarding the practical implementation aspects.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
292
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
293 In most cases how an algorithm is explained and how it is actually implemented are two very different concepts. For
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
294 example, the Handbook of Applied Cryptography (\textit{HAC}), algorithm 14.7 on page 594, gives a relatively simple
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
295 algorithm for performing multiple precision integer addition. However, the description lacks any discussion concerning
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
296 the fact that the two integer inputs may be of differing magnitudes. As a result the implementation is not as simple
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
297 as the text would lead people to believe. Similarly the division routine (\textit{algorithm 14.20, pp. 598}) does not
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
298 discuss how to handle sign or handle the dividend's decreasing magnitude in the main loop (\textit{step \#3}).
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
299
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
300 Both texts also do not discuss several key optimal algorithms required such as ``Comba'' and Karatsuba multipliers
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
301 and fast modular inversion, which we consider practical oversights. These optimal algorithms are vital to achieve
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
302 any form of useful performance in non-trivial applications.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
303
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
304 To solve this problem the focus of this text is on the practical aspects of implementing a multiple precision integer
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
305 package. As a case study the ``LibTomMath''\footnote{Available at \url{http://math.libtomcrypt.org}} package is used
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
306 to demonstrate algorithms with real implementations\footnote{In the ISO C programming language.} that have been field
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
307 tested and work very well. The LibTomMath library is freely available on the Internet for all uses and this text
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
308 discusses a very large portion of the inner workings of the library.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
309
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
310 The algorithms that are presented will always include at least one ``pseudo-code'' description followed
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
311 by the actual C source code that implements the algorithm. The pseudo-code can be used to implement the same
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
312 algorithm in other programming languages as the reader sees fit.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
313
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
314 This text shall also serve as a walkthrough of the creation of multiple precision algorithms from scratch. Showing
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
315 the reader how the algorithms fit together as well as where to start on various taskings.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
316
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
317 \section{Discussion and Notation}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
318 \subsection{Notation}
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
319 A multiple precision integer of $n$-digits shall be denoted as $x = (x_{n-1}, \ldots, x_1, x_0)_{ \beta }$ and represent
19
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
320 the integer $x \equiv \sum_{i=0}^{n-1} x_i\beta^i$. The elements of the array $x$ are said to be the radix $\beta$ digits
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
321 of the integer. For example, $x = (1,2,3)_{10}$ would represent the integer
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
322 $1\cdot 10^2 + 2\cdot10^1 + 3\cdot10^0 = 123$.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
323
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
324 \index{mp\_int}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
325 The term ``mp\_int'' shall refer to a composite structure which contains the digits of the integer it represents, as well
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
326 as auxilary data required to manipulate the data. These additional members are discussed further in section
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
327 \ref{sec:MPINT}. For the purposes of this text a ``multiple precision integer'' and an ``mp\_int'' are assumed to be
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
328 synonymous. When an algorithm is specified to accept an mp\_int variable it is assumed the various auxliary data members
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
329 are present as well. An expression of the type \textit{variablename.item} implies that it should evaluate to the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
330 member named ``item'' of the variable. For example, a string of characters may have a member ``length'' which would
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
331 evaluate to the number of characters in the string. If the string $a$ equals ``hello'' then it follows that
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
332 $a.length = 5$.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
333
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
334 For certain discussions more generic algorithms are presented to help the reader understand the final algorithm used
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
335 to solve a given problem. When an algorithm is described as accepting an integer input it is assumed the input is
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
336 a plain integer with no additional multiple-precision members. That is, algorithms that use integers as opposed to
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
337 mp\_ints as inputs do not concern themselves with the housekeeping operations required such as memory management. These
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
338 algorithms will be used to establish the relevant theory which will subsequently be used to describe a multiple
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
339 precision algorithm to solve the same problem.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
340
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
341 \subsection{Precision Notation}
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
342 The variable $\beta$ represents the radix of a single digit of a multiple precision integer and
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
343 must be of the form $q^p$ for $q, p \in \Z^+$. A single precision variable must be able to represent integers in
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
344 the range $0 \le x < q \beta$ while a double precision variable must be able to represent integers in the range
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
345 $0 \le x < q \beta^2$. The extra radix-$q$ factor allows additions and subtractions to proceed without truncation of the
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
346 carry. Since all modern computers are binary, it is assumed that $q$ is two.
19
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
347
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
348 \index{mp\_digit} \index{mp\_word}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
349 Within the source code that will be presented for each algorithm, the data type \textbf{mp\_digit} will represent
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
350 a single precision integer type, while, the data type \textbf{mp\_word} will represent a double precision integer type. In
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
351 several algorithms (notably the Comba routines) temporary results will be stored in arrays of double precision mp\_words.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
352 For the purposes of this text $x_j$ will refer to the $j$'th digit of a single precision array and $\hat x_j$ will refer to
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
353 the $j$'th digit of a double precision array. Whenever an expression is to be assigned to a double precision
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
354 variable it is assumed that all single precision variables are promoted to double precision during the evaluation.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
355 Expressions that are assigned to a single precision variable are truncated to fit within the precision of a single
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
356 precision data type.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
357
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
358 For example, if $\beta = 10^2$ a single precision data type may represent a value in the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
359 range $0 \le x < 10^3$, while a double precision data type may represent a value in the range $0 \le x < 10^5$. Let
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
360 $a = 23$ and $b = 49$ represent two single precision variables. The single precision product shall be written
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
361 as $c \leftarrow a \cdot b$ while the double precision product shall be written as $\hat c \leftarrow a \cdot b$.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
362 In this particular case, $\hat c = 1127$ and $c = 127$. The most significant digit of the product would not fit
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
363 in a single precision data type and as a result $c \ne \hat c$.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
364
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
365 \subsection{Algorithm Inputs and Outputs}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
366 Within the algorithm descriptions all variables are assumed to be scalars of either single or double precision
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
367 as indicated. The only exception to this rule is when variables have been indicated to be of type mp\_int. This
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
368 distinction is important as scalars are often used as array indicies and various other counters.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
369
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
370 \subsection{Mathematical Expressions}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
371 The $\lfloor \mbox{ } \rfloor$ brackets imply an expression truncated to an integer not greater than the expression
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
372 itself. For example, $\lfloor 5.7 \rfloor = 5$. Similarly the $\lceil \mbox{ } \rceil$ brackets imply an expression
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
373 rounded to an integer not less than the expression itself. For example, $\lceil 5.1 \rceil = 6$. Typically when
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
374 the $/$ division symbol is used the intention is to perform an integer division with truncation. For example,
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
375 $5/2 = 2$ which will often be written as $\lfloor 5/2 \rfloor = 2$ for clarity. When an expression is written as a
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
376 fraction a real value division is implied, for example ${5 \over 2} = 2.5$.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
377
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
378 The norm of a multiple precision integer, for example $\vert \vert x \vert \vert$, will be used to represent the number of digits in the representation
19
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
379 of the integer. For example, $\vert \vert 123 \vert \vert = 3$ and $\vert \vert 79452 \vert \vert = 5$.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
380
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
381 \subsection{Work Effort}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
382 \index{big-Oh}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
383 To measure the efficiency of the specified algorithms, a modified big-Oh notation is used. In this system all
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
384 single precision operations are considered to have the same cost\footnote{Except where explicitly noted.}.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
385 That is a single precision addition, multiplication and division are assumed to take the same time to
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
386 complete. While this is generally not true in practice, it will simplify the discussions considerably.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
387
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
388 Some algorithms have slight advantages over others which is why some constants will not be removed in
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
389 the notation. For example, a normal baseline multiplication (section \ref{sec:basemult}) requires $O(n^2)$ work while a
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
390 baseline squaring (section \ref{sec:basesquare}) requires $O({{n^2 + n}\over 2})$ work. In standard big-Oh notation these
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
391 would both be said to be equivalent to $O(n^2)$. However,
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
392 in the context of the this text this is not the case as the magnitude of the inputs will typically be rather small. As a
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
393 result small constant factors in the work effort will make an observable difference in algorithm efficiency.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
394
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
395 All of the algorithms presented in this text have a polynomial time work level. That is, of the form
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
396 $O(n^k)$ for $n, k \in \Z^{+}$. This will help make useful comparisons in terms of the speed of the algorithms and how
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
397 various optimizations will help pay off in the long run.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
398
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
399 \section{Exercises}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
400 Within the more advanced chapters a section will be set aside to give the reader some challenging exercises related to
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
401 the discussion at hand. These exercises are not designed to be prize winning problems, but instead to be thought
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
402 provoking. Wherever possible the problems are forward minded, stating problems that will be answered in subsequent
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
403 chapters. The reader is encouraged to finish the exercises as they appear to get a better understanding of the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
404 subject material.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
405
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
406 That being said, the problems are designed to affirm knowledge of a particular subject matter. Students in particular
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
407 are encouraged to verify they can answer the problems correctly before moving on.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
408
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
409 Similar to the exercises of \cite[pp. ix]{TAOCPV2} these exercises are given a scoring system based on the difficulty of
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
410 the problem. However, unlike \cite{TAOCPV2} the problems do not get nearly as hard. The scoring of these
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
411 exercises ranges from one (the easiest) to five (the hardest). The following table sumarizes the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
412 scoring system used.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
413
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
414 \begin{figure}[here]
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
415 \begin{center}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
416 \begin{small}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
417 \begin{tabular}{|c|l|}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
418 \hline $\left [ 1 \right ]$ & An easy problem that should only take the reader a manner of \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
419 & minutes to solve. Usually does not involve much computer time \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
420 & to solve. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
421 \hline $\left [ 2 \right ]$ & An easy problem that involves a marginal amount of computer \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
422 & time usage. Usually requires a program to be written to \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
423 & solve the problem. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
424 \hline $\left [ 3 \right ]$ & A moderately hard problem that requires a non-trivial amount \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
425 & of work. Usually involves trivial research and development of \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
426 & new theory from the perspective of a student. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
427 \hline $\left [ 4 \right ]$ & A moderately hard problem that involves a non-trivial amount \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
428 & of work and research, the solution to which will demonstrate \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
429 & a higher mastery of the subject matter. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
430 \hline $\left [ 5 \right ]$ & A hard problem that involves concepts that are difficult for a \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
431 & novice to solve. Solutions to these problems will demonstrate a \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
432 & complete mastery of the given subject. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
433 \hline
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
434 \end{tabular}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
435 \end{small}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
436 \end{center}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
437 \caption{Exercise Scoring System}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
438 \end{figure}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
439
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
440 Problems at the first level are meant to be simple questions that the reader can answer quickly without programming a solution or
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
441 devising new theory. These problems are quick tests to see if the material is understood. Problems at the second level
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
442 are also designed to be easy but will require a program or algorithm to be implemented to arrive at the answer. These
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
443 two levels are essentially entry level questions.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
444
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
445 Problems at the third level are meant to be a bit more difficult than the first two levels. The answer is often
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
446 fairly obvious but arriving at an exacting solution requires some thought and skill. These problems will almost always
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
447 involve devising a new algorithm or implementing a variation of another algorithm previously presented. Readers who can
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
448 answer these questions will feel comfortable with the concepts behind the topic at hand.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
449
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
450 Problems at the fourth level are meant to be similar to those of the level three questions except they will require
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
451 additional research to be completed. The reader will most likely not know the answer right away, nor will the text provide
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
452 the exact details of the answer until a subsequent chapter.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
453
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
454 Problems at the fifth level are meant to be the hardest
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
455 problems relative to all the other problems in the chapter. People who can correctly answer fifth level problems have a
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
456 mastery of the subject matter at hand.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
457
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
458 Often problems will be tied together. The purpose of this is to start a chain of thought that will be discussed in future chapters. The reader
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
459 is encouraged to answer the follow-up problems and try to draw the relevance of problems.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
460
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
461 \section{Introduction to LibTomMath}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
462
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
463 \subsection{What is LibTomMath?}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
464 LibTomMath is a free and open source multiple precision integer library written entirely in portable ISO C. By portable it
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
465 is meant that the library does not contain any code that is computer platform dependent or otherwise problematic to use on
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
466 any given platform.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
467
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
468 The library has been successfully tested under numerous operating systems including Unix\footnote{All of these
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
469 trademarks belong to their respective rightful owners.}, MacOS, Windows, Linux, PalmOS and on standalone hardware such
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
470 as the Gameboy Advance. The library is designed to contain enough functionality to be able to develop applications such
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
471 as public key cryptosystems and still maintain a relatively small footprint.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
472
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
473 \subsection{Goals of LibTomMath}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
474
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
475 Libraries which obtain the most efficiency are rarely written in a high level programming language such as C. However,
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
476 even though this library is written entirely in ISO C, considerable care has been taken to optimize the algorithm implementations within the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
477 library. Specifically the code has been written to work well with the GNU C Compiler (\textit{GCC}) on both x86 and ARM
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
478 processors. Wherever possible, highly efficient algorithms, such as Karatsuba multiplication, sliding window
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
479 exponentiation and Montgomery reduction have been provided to make the library more efficient.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
480
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
481 Even with the nearly optimal and specialized algorithms that have been included the Application Programing Interface
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
482 (\textit{API}) has been kept as simple as possible. Often generic place holder routines will make use of specialized
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
483 algorithms automatically without the developer's specific attention. One such example is the generic multiplication
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
484 algorithm \textbf{mp\_mul()} which will automatically use Toom--Cook, Karatsuba, Comba or baseline multiplication
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
485 based on the magnitude of the inputs and the configuration of the library.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
486
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
487 Making LibTomMath as efficient as possible is not the only goal of the LibTomMath project. Ideally the library should
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
488 be source compatible with another popular library which makes it more attractive for developers to use. In this case the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
489 MPI library was used as a API template for all the basic functions. MPI was chosen because it is another library that fits
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
490 in the same niche as LibTomMath. Even though LibTomMath uses MPI as the template for the function names and argument
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
491 passing conventions, it has been written from scratch by Tom St Denis.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
492
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
493 The project is also meant to act as a learning tool for students, the logic being that no easy-to-follow ``bignum''
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
494 library exists which can be used to teach computer science students how to perform fast and reliable multiple precision
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
495 integer arithmetic. To this end the source code has been given quite a few comments and algorithm discussion points.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
496
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
497 \section{Choice of LibTomMath}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
498 LibTomMath was chosen as the case study of this text not only because the author of both projects is one and the same but
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
499 for more worthy reasons. Other libraries such as GMP \cite{GMP}, MPI \cite{MPI}, LIP \cite{LIP} and OpenSSL
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
500 \cite{OPENSSL} have multiple precision integer arithmetic routines but would not be ideal for this text for
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
501 reasons that will be explained in the following sub-sections.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
502
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
503 \subsection{Code Base}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
504 The LibTomMath code base is all portable ISO C source code. This means that there are no platform dependent conditional
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
505 segments of code littered throughout the source. This clean and uncluttered approach to the library means that a
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
506 developer can more readily discern the true intent of a given section of source code without trying to keep track of
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
507 what conditional code will be used.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
508
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
509 The code base of LibTomMath is well organized. Each function is in its own separate source code file
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
510 which allows the reader to find a given function very quickly. On average there are $76$ lines of code per source
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
511 file which makes the source very easily to follow. By comparison MPI and LIP are single file projects making code tracing
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
512 very hard. GMP has many conditional code segments which also hinder tracing.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
513
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
514 When compiled with GCC for the x86 processor and optimized for speed the entire library is approximately $100$KiB\footnote{The notation ``KiB'' means $2^{10}$ octets, similarly ``MiB'' means $2^{20}$ octets.}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
515 which is fairly small compared to GMP (over $250$KiB). LibTomMath is slightly larger than MPI (which compiles to about
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
516 $50$KiB) but LibTomMath is also much faster and more complete than MPI.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
517
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
518 \subsection{API Simplicity}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
519 LibTomMath is designed after the MPI library and shares the API design. Quite often programs that use MPI will build
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
520 with LibTomMath without change. The function names correlate directly to the action they perform. Almost all of the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
521 functions share the same parameter passing convention. The learning curve is fairly shallow with the API provided
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
522 which is an extremely valuable benefit for the student and developer alike.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
523
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
524 The LIP library is an example of a library with an API that is awkward to work with. LIP uses function names that are often ``compressed'' to
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
525 illegible short hand. LibTomMath does not share this characteristic.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
526
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
527 The GMP library also does not return error codes. Instead it uses a POSIX.1 \cite{POSIX1} signal system where errors
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
528 are signaled to the host application. This happens to be the fastest approach but definitely not the most versatile. In
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
529 effect a math error (i.e. invalid input, heap error, etc) can cause a program to stop functioning which is definitely
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
530 undersireable in many situations.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
531
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
532 \subsection{Optimizations}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
533 While LibTomMath is certainly not the fastest library (GMP often beats LibTomMath by a factor of two) it does
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
534 feature a set of optimal algorithms for tasks such as modular reduction, exponentiation, multiplication and squaring. GMP
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
535 and LIP also feature such optimizations while MPI only uses baseline algorithms with no optimizations. GMP lacks a few
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
536 of the additional modular reduction optimizations that LibTomMath features\footnote{At the time of this writing GMP
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
537 only had Barrett and Montgomery modular reduction algorithms.}.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
538
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
539 LibTomMath is almost always an order of magnitude faster than the MPI library at computationally expensive tasks such as modular
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
540 exponentiation. In the grand scheme of ``bignum'' libraries LibTomMath is faster than the average library and usually
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
541 slower than the best libraries such as GMP and OpenSSL by only a small factor.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
542
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
543 \subsection{Portability and Stability}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
544 LibTomMath will build ``out of the box'' on any platform equipped with a modern version of the GNU C Compiler
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
545 (\textit{GCC}). This means that without changes the library will build without configuration or setting up any
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
546 variables. LIP and MPI will build ``out of the box'' as well but have numerous known bugs. Most notably the author of
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
547 MPI has recently stopped working on his library and LIP has long since been discontinued.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
548
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
549 GMP requires a configuration script to run and will not build out of the box. GMP and LibTomMath are still in active
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
550 development and are very stable across a variety of platforms.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
551
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
552 \subsection{Choice}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
553 LibTomMath is a relatively compact, well documented, highly optimized and portable library which seems only natural for
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
554 the case study of this text. Various source files from the LibTomMath project will be included within the text. However,
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
555 the reader is encouraged to download their own copy of the library to actually be able to work with the library.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
556
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
557 \chapter{Getting Started}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
558 \section{Library Basics}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
559 The trick to writing any useful library of source code is to build a solid foundation and work outwards from it. First,
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
560 a problem along with allowable solution parameters should be identified and analyzed. In this particular case the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
561 inability to accomodate multiple precision integers is the problem. Futhermore, the solution must be written
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
562 as portable source code that is reasonably efficient across several different computer platforms.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
563
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
564 After a foundation is formed the remainder of the library can be designed and implemented in a hierarchical fashion.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
565 That is, to implement the lowest level dependencies first and work towards the most abstract functions last. For example,
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
566 before implementing a modular exponentiation algorithm one would implement a modular reduction algorithm.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
567 By building outwards from a base foundation instead of using a parallel design methodology the resulting project is
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
568 highly modular. Being highly modular is a desirable property of any project as it often means the resulting product
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
569 has a small footprint and updates are easy to perform.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
570
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
571 Usually when I start a project I will begin with the header files. I define the data types I think I will need and
19
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
572 prototype the initial functions that are not dependent on other functions (within the library). After I
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
573 implement these base functions I prototype more dependent functions and implement them. The process repeats until
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
574 I implement all of the functions I require. For example, in the case of LibTomMath I implemented functions such as
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
575 mp\_init() well before I implemented mp\_mul() and even further before I implemented mp\_exptmod(). As an example as to
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
576 why this design works note that the Karatsuba and Toom-Cook multipliers were written \textit{after} the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
577 dependent function mp\_exptmod() was written. Adding the new multiplication algorithms did not require changes to the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
578 mp\_exptmod() function itself and lowered the total cost of ownership (\textit{so to speak}) and of development
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
579 for new algorithms. This methodology allows new algorithms to be tested in a complete framework with relative ease.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
580
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
581 FIGU,design_process,Design Flow of the First Few Original LibTomMath Functions.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
582
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
583 Only after the majority of the functions were in place did I pursue a less hierarchical approach to auditing and optimizing
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
584 the source code. For example, one day I may audit the multipliers and the next day the polynomial basis functions.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
585
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
586 It only makes sense to begin the text with the preliminary data types and support algorithms required as well.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
587 This chapter discusses the core algorithms of the library which are the dependents for every other algorithm.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
588
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
589 \section{What is a Multiple Precision Integer?}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
590 Recall that most programming languages, in particular ISO C \cite{ISOC}, only have fixed precision data types that on their own cannot
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
591 be used to represent values larger than their precision will allow. The purpose of multiple precision algorithms is
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
592 to use fixed precision data types to create and manipulate multiple precision integers which may represent values
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
593 that are very large.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
594
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
595 As a well known analogy, school children are taught how to form numbers larger than nine by prepending more radix ten digits. In the decimal system
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
596 the largest single digit value is $9$. However, by concatenating digits together larger numbers may be represented. Newly prepended digits
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
597 (\textit{to the left}) are said to be in a different power of ten column. That is, the number $123$ can be described as having a $1$ in the hundreds
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
598 column, $2$ in the tens column and $3$ in the ones column. Or more formally $123 = 1 \cdot 10^2 + 2 \cdot 10^1 + 3 \cdot 10^0$. Computer based
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
599 multiple precision arithmetic is essentially the same concept. Larger integers are represented by adjoining fixed
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
600 precision computer words with the exception that a different radix is used.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
601
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
602 What most people probably do not think about explicitly are the various other attributes that describe a multiple precision
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
603 integer. For example, the integer $154_{10}$ has two immediately obvious properties. First, the integer is positive,
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
604 that is the sign of this particular integer is positive as opposed to negative. Second, the integer has three digits in
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
605 its representation. There is an additional property that the integer posesses that does not concern pencil-and-paper
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
606 arithmetic. The third property is how many digits placeholders are available to hold the integer.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
607
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
608 The human analogy of this third property is ensuring there is enough space on the paper to write the integer. For example,
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
609 if one starts writing a large number too far to the right on a piece of paper they will have to erase it and move left.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
610 Similarly, computer algorithms must maintain strict control over memory usage to ensure that the digits of an integer
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
611 will not exceed the allowed boundaries. These three properties make up what is known as a multiple precision
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
612 integer or mp\_int for short.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
613
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
614 \subsection{The mp\_int Structure}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
615 \label{sec:MPINT}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
616 The mp\_int structure is the ISO C based manifestation of what represents a multiple precision integer. The ISO C standard does not provide for
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
617 any such data type but it does provide for making composite data types known as structures. The following is the structure definition
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
618 used within LibTomMath.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
619
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
620 \index{mp\_int}
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
621 \begin{figure}[here]
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
622 \begin{center}
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
623 \begin{small}
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
624 %\begin{verbatim}
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
625 \begin{tabular}{|l|}
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
626 \hline
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
627 typedef struct \{ \\
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
628 \hspace{3mm}int used, alloc, sign;\\
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
629 \hspace{3mm}mp\_digit *dp;\\
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
630 \} \textbf{mp\_int}; \\
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
631 \hline
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
632 \end{tabular}
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
633 %\end{verbatim}
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
634 \end{small}
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
635 \caption{The mp\_int Structure}
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
636 \label{fig:mpint}
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
637 \end{center}
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
638 \end{figure}
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
639
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
640 The mp\_int structure (fig. \ref{fig:mpint}) can be broken down as follows.
19
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
641
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
642 \begin{enumerate}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
643 \item The \textbf{used} parameter denotes how many digits of the array \textbf{dp} contain the digits used to represent
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
644 a given integer. The \textbf{used} count must be positive (or zero) and may not exceed the \textbf{alloc} count.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
645
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
646 \item The \textbf{alloc} parameter denotes how
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
647 many digits are available in the array to use by functions before it has to increase in size. When the \textbf{used} count
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
648 of a result would exceed the \textbf{alloc} count all of the algorithms will automatically increase the size of the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
649 array to accommodate the precision of the result.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
650
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
651 \item The pointer \textbf{dp} points to a dynamically allocated array of digits that represent the given multiple
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
652 precision integer. It is padded with $(\textbf{alloc} - \textbf{used})$ zero digits. The array is maintained in a least
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
653 significant digit order. As a pencil and paper analogy the array is organized such that the right most digits are stored
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
654 first starting at the location indexed by zero\footnote{In C all arrays begin at zero.} in the array. For example,
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
655 if \textbf{dp} contains $\lbrace a, b, c, \ldots \rbrace$ where \textbf{dp}$_0 = a$, \textbf{dp}$_1 = b$, \textbf{dp}$_2 = c$, $\ldots$ then
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
656 it would represent the integer $a + b\beta + c\beta^2 + \ldots$
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
657
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
658 \index{MP\_ZPOS} \index{MP\_NEG}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
659 \item The \textbf{sign} parameter denotes the sign as either zero/positive (\textbf{MP\_ZPOS}) or negative (\textbf{MP\_NEG}).
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
660 \end{enumerate}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
661
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
662 \subsubsection{Valid mp\_int Structures}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
663 Several rules are placed on the state of an mp\_int structure and are assumed to be followed for reasons of efficiency.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
664 The only exceptions are when the structure is passed to initialization functions such as mp\_init() and mp\_init\_copy().
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
665
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
666 \begin{enumerate}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
667 \item The value of \textbf{alloc} may not be less than one. That is \textbf{dp} always points to a previously allocated
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
668 array of digits.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
669 \item The value of \textbf{used} may not exceed \textbf{alloc} and must be greater than or equal to zero.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
670 \item The value of \textbf{used} implies the digit at index $(used - 1)$ of the \textbf{dp} array is non-zero. That is,
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
671 leading zero digits in the most significant positions must be trimmed.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
672 \begin{enumerate}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
673 \item Digits in the \textbf{dp} array at and above the \textbf{used} location must be zero.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
674 \end{enumerate}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
675 \item The value of \textbf{sign} must be \textbf{MP\_ZPOS} if \textbf{used} is zero;
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
676 this represents the mp\_int value of zero.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
677 \end{enumerate}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
678
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
679 \section{Argument Passing}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
680 A convention of argument passing must be adopted early on in the development of any library. Making the function
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
681 prototypes consistent will help eliminate many headaches in the future as the library grows to significant complexity.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
682 In LibTomMath the multiple precision integer functions accept parameters from left to right as pointers to mp\_int
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
683 structures. That means that the source (input) operands are placed on the left and the destination (output) on the right.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
684 Consider the following examples.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
685
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
686 \begin{verbatim}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
687 mp_mul(&a, &b, &c); /* c = a * b */
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
688 mp_add(&a, &b, &a); /* a = a + b */
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
689 mp_sqr(&a, &b); /* b = a * a */
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
690 \end{verbatim}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
691
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
692 The left to right order is a fairly natural way to implement the functions since it lets the developer read aloud the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
693 functions and make sense of them. For example, the first function would read ``multiply a and b and store in c''.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
694
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
695 Certain libraries (\textit{LIP by Lenstra for instance}) accept parameters the other way around, to mimic the order
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
696 of assignment expressions. That is, the destination (output) is on the left and arguments (inputs) are on the right. In
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
697 truth, it is entirely a matter of preference. In the case of LibTomMath the convention from the MPI library has been
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
698 adopted.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
699
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
700 Another very useful design consideration, provided for in LibTomMath, is whether to allow argument sources to also be a
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
701 destination. For example, the second example (\textit{mp\_add}) adds $a$ to $b$ and stores in $a$. This is an important
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
702 feature to implement since it allows the calling functions to cut down on the number of variables it must maintain.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
703 However, to implement this feature specific care has to be given to ensure the destination is not modified before the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
704 source is fully read.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
705
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
706 \section{Return Values}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
707 A well implemented application, no matter what its purpose, should trap as many runtime errors as possible and return them
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
708 to the caller. By catching runtime errors a library can be guaranteed to prevent undefined behaviour. However, the end
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
709 developer can still manage to cause a library to crash. For example, by passing an invalid pointer an application may
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
710 fault by dereferencing memory not owned by the application.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
711
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
712 In the case of LibTomMath the only errors that are checked for are related to inappropriate inputs (division by zero for
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
713 instance) and memory allocation errors. It will not check that the mp\_int passed to any function is valid nor
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
714 will it check pointers for validity. Any function that can cause a runtime error will return an error code as an
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
715 \textbf{int} data type with one of the following values (fig \ref{fig:errcodes}).
19
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
716
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
717 \index{MP\_OKAY} \index{MP\_VAL} \index{MP\_MEM}
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
718 \begin{figure}[here]
19
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
719 \begin{center}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
720 \begin{tabular}{|l|l|}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
721 \hline \textbf{Value} & \textbf{Meaning} \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
722 \hline \textbf{MP\_OKAY} & The function was successful \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
723 \hline \textbf{MP\_VAL} & One of the input value(s) was invalid \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
724 \hline \textbf{MP\_MEM} & The function ran out of heap memory \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
725 \hline
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
726 \end{tabular}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
727 \end{center}
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
728 \caption{LibTomMath Error Codes}
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
729 \label{fig:errcodes}
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
730 \end{figure}
19
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
731
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
732 When an error is detected within a function it should free any memory it allocated, often during the initialization of
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
733 temporary mp\_ints, and return as soon as possible. The goal is to leave the system in the same state it was when the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
734 function was called. Error checking with this style of API is fairly simple.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
735
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
736 \begin{verbatim}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
737 int err;
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
738 if ((err = mp_add(&a, &b, &c)) != MP_OKAY) {
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
739 printf("Error: %s\n", mp_error_to_string(err));
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
740 exit(EXIT_FAILURE);
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
741 }
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
742 \end{verbatim}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
743
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
744 The GMP \cite{GMP} library uses C style \textit{signals} to flag errors which is of questionable use. Not all errors are fatal
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
745 and it was not deemed ideal by the author of LibTomMath to force developers to have signal handlers for such cases.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
746
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
747 \section{Initialization and Clearing}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
748 The logical starting point when actually writing multiple precision integer functions is the initialization and
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
749 clearing of the mp\_int structures. These two algorithms will be used by the majority of the higher level algorithms.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
750
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
751 Given the basic mp\_int structure an initialization routine must first allocate memory to hold the digits of
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
752 the integer. Often it is optimal to allocate a sufficiently large pre-set number of digits even though
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
753 the initial integer will represent zero. If only a single digit were allocated quite a few subsequent re-allocations
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
754 would occur when operations are performed on the integers. There is a tradeoff between how many default digits to allocate
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
755 and how many re-allocations are tolerable. Obviously allocating an excessive amount of digits initially will waste
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
756 memory and become unmanageable.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
757
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
758 If the memory for the digits has been successfully allocated then the rest of the members of the structure must
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
759 be initialized. Since the initial state of an mp\_int is to represent the zero integer, the allocated digits must be set
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
760 to zero. The \textbf{used} count set to zero and \textbf{sign} set to \textbf{MP\_ZPOS}.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
761
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
762 \subsection{Initializing an mp\_int}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
763 An mp\_int is said to be initialized if it is set to a valid, preferably default, state such that all of the members of the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
764 structure are set to valid values. The mp\_init algorithm will perform such an action.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
765
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
766 \index{mp\_init}
19
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
767 \begin{figure}[here]
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
768 \begin{center}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
769 \begin{tabular}{l}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
770 \hline Algorithm \textbf{mp\_init}. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
771 \textbf{Input}. An mp\_int $a$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
772 \textbf{Output}. Allocate memory and initialize $a$ to a known valid mp\_int state. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
773 \hline \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
774 1. Allocate memory for \textbf{MP\_PREC} digits. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
775 2. If the allocation failed return(\textit{MP\_MEM}) \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
776 3. for $n$ from $0$ to $MP\_PREC - 1$ do \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
777 \hspace{3mm}3.1 $a_n \leftarrow 0$\\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
778 4. $a.sign \leftarrow MP\_ZPOS$\\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
779 5. $a.used \leftarrow 0$\\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
780 6. $a.alloc \leftarrow MP\_PREC$\\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
781 7. Return(\textit{MP\_OKAY})\\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
782 \hline
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
783 \end{tabular}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
784 \end{center}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
785 \caption{Algorithm mp\_init}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
786 \end{figure}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
787
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
788 \textbf{Algorithm mp\_init.}
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
789 The purpose of this function is to initialize an mp\_int structure so that the rest of the library can properly
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
790 manipulte it. It is assumed that the input may not have had any of its members previously initialized which is certainly
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
791 a valid assumption if the input resides on the stack.
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
792
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
793 Before any of the members such as \textbf{sign}, \textbf{used} or \textbf{alloc} are initialized the memory for
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
794 the digits is allocated. If this fails the function returns before setting any of the other members. The \textbf{MP\_PREC}
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
795 name represents a constant\footnote{Defined in the ``tommath.h'' header file within LibTomMath.}
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
796 used to dictate the minimum precision of newly initialized mp\_int integers. Ideally, it is at least equal to the smallest
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
797 precision number you'll be working with.
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
798
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
799 Allocating a block of digits at first instead of a single digit has the benefit of lowering the number of usually slow
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
800 heap operations later functions will have to perform in the future. If \textbf{MP\_PREC} is set correctly the slack
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
801 memory and the number of heap operations will be trivial.
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
802
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
803 Once the allocation has been made the digits have to be set to zero as well as the \textbf{used}, \textbf{sign} and
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
804 \textbf{alloc} members initialized. This ensures that the mp\_int will always represent the default state of zero regardless
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
805 of the original condition of the input.
19
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
806
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
807 \textbf{Remark.}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
808 This function introduces the idiosyncrasy that all iterative loops, commonly initiated with the ``for'' keyword, iterate incrementally
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
809 when the ``to'' keyword is placed between two expressions. For example, ``for $a$ from $b$ to $c$ do'' means that
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
810 a subsequent expression (or body of expressions) are to be evaluated upto $c - b$ times so long as $b \le c$. In each
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
811 iteration the variable $a$ is substituted for a new integer that lies inclusively between $b$ and $c$. If $b > c$ occured
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
812 the loop would not iterate. By contrast if the ``downto'' keyword were used in place of ``to'' the loop would iterate
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
813 decrementally.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
814
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
815 EXAM,bn_mp_init.c
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
816
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
817 One immediate observation of this initializtion function is that it does not return a pointer to a mp\_int structure. It
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
818 is assumed that the caller has already allocated memory for the mp\_int structure, typically on the application stack. The
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
819 call to mp\_init() is used only to initialize the members of the structure to a known default state.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
820
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
821 Here we see (line @23,[email protected]) the memory allocation is performed first. This allows us to exit cleanly and quickly
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
822 if there is an error. If the allocation fails the routine will return \textbf{MP\_MEM} to the caller to indicate there
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
823 was a memory error. The function XMALLOC is what actually allocates the memory. Technically XMALLOC is not a function
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
824 but a macro defined in ``tommath.h``. By default, XMALLOC will evaluate to malloc() which is the C library's built--in
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
825 memory allocation routine.
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
826
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
827 In order to assure the mp\_int is in a known state the digits must be set to zero. On most platforms this could have been
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
828 accomplished by using calloc() instead of malloc(). However, to correctly initialize a integer type to a given value in a
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
829 portable fashion you have to actually assign the value. The for loop (line @28,[email protected]) performs this required
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
830 operation.
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
831
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
832 After the memory has been successfully initialized the remainder of the members are initialized
19
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
833 (lines @29,[email protected] through @31,[email protected]) to their respective default states. At this point the algorithm has succeeded and
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
834 a success code is returned to the calling function. If this function returns \textbf{MP\_OKAY} it is safe to assume the
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
835 mp\_int structure has been properly initialized and is safe to use with other functions within the library.
19
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
836
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
837 \subsection{Clearing an mp\_int}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
838 When an mp\_int is no longer required by the application, the memory that has been allocated for its digits must be
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
839 returned to the application's memory pool with the mp\_clear algorithm.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
840
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
841 \begin{figure}[here]
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
842 \begin{center}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
843 \begin{tabular}{l}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
844 \hline Algorithm \textbf{mp\_clear}. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
845 \textbf{Input}. An mp\_int $a$ \\
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
846 \textbf{Output}. The memory for $a$ shall be deallocated. \\
19
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
847 \hline \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
848 1. If $a$ has been previously freed then return(\textit{MP\_OKAY}). \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
849 2. for $n$ from 0 to $a.used - 1$ do \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
850 \hspace{3mm}2.1 $a_n \leftarrow 0$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
851 3. Free the memory allocated for the digits of $a$. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
852 4. $a.used \leftarrow 0$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
853 5. $a.alloc \leftarrow 0$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
854 6. $a.sign \leftarrow MP\_ZPOS$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
855 7. Return(\textit{MP\_OKAY}). \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
856 \hline
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
857 \end{tabular}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
858 \end{center}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
859 \caption{Algorithm mp\_clear}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
860 \end{figure}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
861
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
862 \textbf{Algorithm mp\_clear.}
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
863 This algorithm accomplishes two goals. First, it clears the digits and the other mp\_int members. This ensures that
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
864 if a developer accidentally re-uses a cleared structure it is less likely to cause problems. The second goal
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
865 is to free the allocated memory.
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
866
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
867 The logic behind the algorithm is extended by marking cleared mp\_int structures so that subsequent calls to this
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
868 algorithm will not try to free the memory multiple times. Cleared mp\_ints are detectable by having a pre-defined invalid
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
869 digit pointer \textbf{dp} setting.
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
870
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
871 Once an mp\_int has been cleared the mp\_int structure is no longer in a valid state for any other algorithm
19
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
872 with the exception of algorithms mp\_init, mp\_init\_copy, mp\_init\_size and mp\_clear.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
873
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
874 EXAM,bn_mp_clear.c
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
875
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
876 The algorithm only operates on the mp\_int if it hasn't been previously cleared. The if statement (line @23,a->dp != [email protected])
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
877 checks to see if the \textbf{dp} member is not \textbf{NULL}. If the mp\_int is a valid mp\_int then \textbf{dp} cannot be
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
878 \textbf{NULL} in which case the if statement will evaluate to true.
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
879
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
880 The digits of the mp\_int are cleared by the for loop (line @25,[email protected]) which assigns a zero to every digit. Similar to mp\_init()
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
881 the digits are assigned zero instead of using block memory operations (such as memset()) since this is more portable.
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
882
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
883 The digits are deallocated off the heap via the XFREE macro. Similar to XMALLOC the XFREE macro actually evaluates to
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
884 a standard C library function. In this case the free() function. Since free() only deallocates the memory the pointer
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
885 still has to be reset to \textbf{NULL} manually (line @33,[email protected]).
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
886
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
887 Now that the digits have been cleared and deallocated the other members are set to their final values (lines @34,= [email protected] and @35,[email protected]).
19
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
888
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
889 \section{Maintenance Algorithms}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
890
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
891 The previous sections describes how to initialize and clear an mp\_int structure. To further support operations
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
892 that are to be performed on mp\_int structures (such as addition and multiplication) the dependent algorithms must be
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
893 able to augment the precision of an mp\_int and
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
894 initialize mp\_ints with differing initial conditions.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
895
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
896 These algorithms complete the set of low level algorithms required to work with mp\_int structures in the higher level
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
897 algorithms such as addition, multiplication and modular exponentiation.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
898
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
899 \subsection{Augmenting an mp\_int's Precision}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
900 When storing a value in an mp\_int structure, a sufficient number of digits must be available to accomodate the entire
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
901 result of an operation without loss of precision. Quite often the size of the array given by the \textbf{alloc} member
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
902 is large enough to simply increase the \textbf{used} digit count. However, when the size of the array is too small it
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
903 must be re-sized appropriately to accomodate the result. The mp\_grow algorithm will provide this functionality.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
904
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
905 \newpage\begin{figure}[here]
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
906 \begin{center}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
907 \begin{tabular}{l}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
908 \hline Algorithm \textbf{mp\_grow}. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
909 \textbf{Input}. An mp\_int $a$ and an integer $b$. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
910 \textbf{Output}. $a$ is expanded to accomodate $b$ digits. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
911 \hline \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
912 1. if $a.alloc \ge b$ then return(\textit{MP\_OKAY}) \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
913 2. $u \leftarrow b\mbox{ (mod }MP\_PREC\mbox{)}$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
914 3. $v \leftarrow b + 2 \cdot MP\_PREC - u$ \\
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
915 4. Re-allocate the array of digits $a$ to size $v$ \\
19
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
916 5. If the allocation failed then return(\textit{MP\_MEM}). \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
917 6. for n from a.alloc to $v - 1$ do \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
918 \hspace{+3mm}6.1 $a_n \leftarrow 0$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
919 7. $a.alloc \leftarrow v$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
920 8. Return(\textit{MP\_OKAY}) \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
921 \hline
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
922 \end{tabular}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
923 \end{center}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
924 \caption{Algorithm mp\_grow}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
925 \end{figure}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
926
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
927 \textbf{Algorithm mp\_grow.}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
928 It is ideal to prevent re-allocations from being performed if they are not required (step one). This is useful to
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
929 prevent mp\_ints from growing excessively in code that erroneously calls mp\_grow.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
930
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
931 The requested digit count is padded up to next multiple of \textbf{MP\_PREC} plus an additional \textbf{MP\_PREC} (steps two and three).
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
932 This helps prevent many trivial reallocations that would grow an mp\_int by trivially small values.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
933
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
934 It is assumed that the reallocation (step four) leaves the lower $a.alloc$ digits of the mp\_int intact. This is much
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
935 akin to how the \textit{realloc} function from the standard C library works. Since the newly allocated digits are
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
936 assumed to contain undefined values they are initially set to zero.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
937
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
938 EXAM,bn_mp_grow.c
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
939
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
940 A quick optimization is to first determine if a memory re-allocation is required at all. The if statement (line @23,[email protected]) checks
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
941 if the \textbf{alloc} member of the mp\_int is smaller than the requested digit count. If the count is not larger than \textbf{alloc}
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
942 the function skips the re-allocation part thus saving time.
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
943
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
944 When a re-allocation is performed it is turned into an optimal request to save time in the future. The requested digit count is
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
945 padded upwards to 2nd multiple of \textbf{MP\_PREC} larger than \textbf{alloc} (line @25, [email protected]). The XREALLOC function is used
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
946 to re-allocate the memory. As per the other functions XREALLOC is actually a macro which evaluates to realloc by default. The realloc
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
947 function leaves the base of the allocation intact which means the first \textbf{alloc} digits of the mp\_int are the same as before
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
948 the re-allocation. All that is left is to clear the newly allocated digits and return.
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
949
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
950 Note that the re-allocation result is actually stored in a temporary pointer $tmp$. This is to allow this function to return
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
951 an error with a valid pointer. Earlier releases of the library stored the result of XREALLOC into the mp\_int $a$. That would
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
952 result in a memory leak if XREALLOC ever failed.
19
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
953
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
954 \subsection{Initializing Variable Precision mp\_ints}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
955 Occasionally the number of digits required will be known in advance of an initialization, based on, for example, the size
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
956 of input mp\_ints to a given algorithm. The purpose of algorithm mp\_init\_size is similar to mp\_init except that it
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
957 will allocate \textit{at least} a specified number of digits.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
958
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
959 \begin{figure}[here]
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
960 \begin{small}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
961 \begin{center}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
962 \begin{tabular}{l}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
963 \hline Algorithm \textbf{mp\_init\_size}. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
964 \textbf{Input}. An mp\_int $a$ and the requested number of digits $b$. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
965 \textbf{Output}. $a$ is initialized to hold at least $b$ digits. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
966 \hline \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
967 1. $u \leftarrow b \mbox{ (mod }MP\_PREC\mbox{)}$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
968 2. $v \leftarrow b + 2 \cdot MP\_PREC - u$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
969 3. Allocate $v$ digits. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
970 4. for $n$ from $0$ to $v - 1$ do \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
971 \hspace{3mm}4.1 $a_n \leftarrow 0$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
972 5. $a.sign \leftarrow MP\_ZPOS$\\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
973 6. $a.used \leftarrow 0$\\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
974 7. $a.alloc \leftarrow v$\\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
975 8. Return(\textit{MP\_OKAY})\\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
976 \hline
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
977 \end{tabular}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
978 \end{center}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
979 \end{small}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
980 \caption{Algorithm mp\_init\_size}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
981 \end{figure}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
982
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
983 \textbf{Algorithm mp\_init\_size.}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
984 This algorithm will initialize an mp\_int structure $a$ like algorithm mp\_init with the exception that the number of
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
985 digits allocated can be controlled by the second input argument $b$. The input size is padded upwards so it is a
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
986 multiple of \textbf{MP\_PREC} plus an additional \textbf{MP\_PREC} digits. This padding is used to prevent trivial
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
987 allocations from becoming a bottleneck in the rest of the algorithms.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
988
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
989 Like algorithm mp\_init, the mp\_int structure is initialized to a default state representing the integer zero. This
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
990 particular algorithm is useful if it is known ahead of time the approximate size of the input. If the approximation is
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
991 correct no further memory re-allocations are required to work with the mp\_int.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
992
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
993 EXAM,bn_mp_init_size.c
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
994
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
995 The number of digits $b$ requested is padded (line @22,MP_[email protected]) by first augmenting it to the next multiple of
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
996 \textbf{MP\_PREC} and then adding \textbf{MP\_PREC} to the result. If the memory can be successfully allocated the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
997 mp\_int is placed in a default state representing the integer zero. Otherwise, the error code \textbf{MP\_MEM} will be
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
998 returned (line @27,[email protected]).
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
999
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 19
diff changeset
1000 The digits are allocated and set to zero at the same time with the calloc() function (line @25,[email protected]). The
19
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1001 \textbf{used} count is set to zero, the \textbf{alloc} count set to the padded digit count and the \textbf{sign} flag set
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1002 to \textbf{MP\_ZPOS} to achieve a default valid mp\_int state (lines @29,[email protected], @30,[email protected] and @31,[email protected]). If the function
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1003 returns succesfully then it is correct to assume that the mp\_int structure is in a valid state for the remainder of the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1004 functions to work with.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1005
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1006 \subsection{Multiple Integer Initializations and Clearings}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1007 Occasionally a function will require a series of mp\_int data types to be made available simultaneously.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1008 The purpose of algorithm mp\_init\_multi is to initialize a variable length array of mp\_int structures in a single
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1009 statement. It is essentially a shortcut to multiple initializations.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1010
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1011 \newpage\begin{figure}[here]
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1012 \begin{center}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1013 \begin{tabular}{l}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1014 \hline Algorithm \textbf{mp\_init\_multi}. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1015 \textbf{Input}. Variable length array $V_k$ of mp\_int variables of length $k$. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1016 \textbf{Output}. The array is initialized such that each mp\_int of $V_k$ is ready to use. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1017 \hline \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1018 1. for $n$ from 0 to $k - 1$ do \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1019 \hspace{+3mm}1.1. Initialize the mp\_int $V_n$ (\textit{mp\_init}) \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1020 \hspace{+3mm}1.2. If initialization failed then do \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1021 \hspace{+6mm}1.2.1. for $j$ from $0$ to $n$ do \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1022 \hspace{+9mm}1.2.1.1. Free the mp\_int $V_j$ (\textit{mp\_clear}) \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1023 \hspace{+6mm}1.2.2. Return(\textit{MP\_MEM}) \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1024 2. Return(\textit{MP\_OKAY}) \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1025 \hline
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1026 \end{tabular}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1027 \end{center}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1028 \caption{Algorithm mp\_init\_multi}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1029 \end{figure}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1030
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1031 \textbf{Algorithm mp\_init\_multi.}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1032 The algorithm will initialize the array of mp\_int variables one at a time. If a runtime error has been detected
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1033 (\textit{step 1.2}) all of the previously initialized variables are cleared. The goal is an ``all or nothing''
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1034 initialization which allows for quick recovery from runtime errors.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1035
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1036 EXAM,bn_mp_init_multi.c
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1037
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1038 This function intializes a variable length list of mp\_int structure pointers. However, instead of having the mp\_int
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1039 structures in an actual C array they are simply passed as arguments to the function. This function makes use of the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1040 ``...'' argument syntax of the C programming language. The list is terminated with a final \textbf{NULL} argument
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1041 appended on the right.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1042
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1043 The function uses the ``stdarg.h'' \textit{va} functions to step portably through the arguments to the function. A count
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1044 $n$ of succesfully initialized mp\_int structures is maintained (line @47,[email protected]) such that if a failure does occur,
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1045 the algorithm can backtrack and free the previously initialized structures (lines @27,[email protected] to @46,}@).
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1046
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1047
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1048 \subsection{Clamping Excess Digits}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1049 When a function anticipates a result will be $n$ digits it is simpler to assume this is true within the body of
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1050 the function instead of checking during the computation. For example, a multiplication of a $i$ digit number by a
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1051 $j$ digit produces a result of at most $i + j$ digits. It is entirely possible that the result is $i + j - 1$
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1052 though, with no final carry into the last position. However, suppose the destination had to be first expanded
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1053 (\textit{via mp\_grow}) to accomodate $i + j - 1$ digits than further expanded to accomodate the final carry.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1054 That would be a considerable waste of time since heap operations are relatively slow.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1055
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1056 The ideal solution is to always assume the result is $i + j$ and fix up the \textbf{used} count after the function
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1057 terminates. This way a single heap operation (\textit{at most}) is required. However, if the result was not checked
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1058 there would be an excess high order zero digit.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1059
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1060 For example, suppose the product of two integers was $x_n = (0x_{n-1}x_{n-2}...x_0)_{\beta}$. The leading zero digit
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1061 will not contribute to the precision of the result. In fact, through subsequent operations more leading zero digits would
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1062 accumulate to the point the size of the integer would be prohibitive. As a result even though the precision is very
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1063 low the representation is excessively large.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1064
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1065 The mp\_clamp algorithm is designed to solve this very problem. It will trim high-order zeros by decrementing the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1066 \textbf{used} count until a non-zero most significant digit is found. Also in this system, zero is considered to be a
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1067 positive number which means that if the \textbf{used} count is decremented to zero, the sign must be set to
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1068 \textbf{MP\_ZPOS}.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1069
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1070 \begin{figure}[here]
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1071 \begin{center}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1072 \begin{tabular}{l}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1073 \hline Algorithm \textbf{mp\_clamp}. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1074 \textbf{Input}. An mp\_int $a$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1075 \textbf{Output}. Any excess leading zero digits of $a$ are removed \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1076 \hline \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1077 1. while $a.used > 0$ and $a_{a.used - 1} = 0$ do \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1078 \hspace{+3mm}1.1 $a.used \leftarrow a.used - 1$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1079 2. if $a.used = 0$ then do \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1080 \hspace{+3mm}2.1 $a.sign \leftarrow MP\_ZPOS$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1081 \hline \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1082 \end{tabular}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1083 \end{center}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1084 \caption{Algorithm mp\_clamp}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1085 \end{figure}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1086
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1087 \textbf{Algorithm mp\_clamp.}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1088 As can be expected this algorithm is very simple. The loop on step one is expected to iterate only once or twice at
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1089 the most. For example, this will happen in cases where there is not a carry to fill the last position. Step two fixes the sign for
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1090 when all of the digits are zero to ensure that the mp\_int is valid at all times.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1091
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1092 EXAM,bn_mp_clamp.c
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1093
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1094 Note on line @27,[email protected] how to test for the \textbf{used} count is made on the left of the \&\& operator. In the C programming
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1095 language the terms to \&\& are evaluated left to right with a boolean short-circuit if any condition fails. This is
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1096 important since if the \textbf{used} is zero the test on the right would fetch below the array. That is obviously
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1097 undesirable. The parenthesis on line @28,a->[email protected] is used to make sure the \textbf{used} count is decremented and not
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1098 the pointer ``a''.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1099
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1100 \section*{Exercises}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1101 \begin{tabular}{cl}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1102 $\left [ 1 \right ]$ & Discuss the relevance of the \textbf{used} member of the mp\_int structure. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1103 & \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1104 $\left [ 1 \right ]$ & Discuss the consequences of not using padding when performing allocations. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1105 & \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1106 $\left [ 2 \right ]$ & Estimate an ideal value for \textbf{MP\_PREC} when performing 1024-bit RSA \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1107 & encryption when $\beta = 2^{28}$. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1108 & \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1109 $\left [ 1 \right ]$ & Discuss the relevance of the algorithm mp\_clamp. What does it prevent? \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1110 & \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1111 $\left [ 1 \right ]$ & Give an example of when the algorithm mp\_init\_copy might be useful. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1112 & \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1113 \end{tabular}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1114
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1115
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1116 %%%
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1117 % CHAPTER FOUR
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1118 %%%
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1119
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1120 \chapter{Basic Operations}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1121
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1122 \section{Introduction}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1123 In the previous chapter a series of low level algorithms were established that dealt with initializing and maintaining
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1124 mp\_int structures. This chapter will discuss another set of seemingly non-algebraic algorithms which will form the low
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1125 level basis of the entire library. While these algorithm are relatively trivial it is important to understand how they
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1126 work before proceeding since these algorithms will be used almost intrinsically in the following chapters.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1127
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1128 The algorithms in this chapter deal primarily with more ``programmer'' related tasks such as creating copies of
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1129 mp\_int structures, assigning small values to mp\_int structures and comparisons of the values mp\_int structures
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1130 represent.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1131
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1132 \section{Assigning Values to mp\_int Structures}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1133 \subsection{Copying an mp\_int}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1134 Assigning the value that a given mp\_int structure represents to another mp\_int structure shall be known as making
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1135 a copy for the purposes of this text. The copy of the mp\_int will be a separate entity that represents the same
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1136 value as the mp\_int it was copied from. The mp\_copy algorithm provides this functionality.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1137
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1138 \newpage\begin{figure}[here]
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1139 \begin{center}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1140 \begin{tabular}{l}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1141 \hline Algorithm \textbf{mp\_copy}. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1142 \textbf{Input}. An mp\_int $a$ and $b$. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1143 \textbf{Output}. Store a copy of $a$ in $b$. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1144 \hline \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1145 1. If $b.alloc < a.used$ then grow $b$ to $a.used$ digits. (\textit{mp\_grow}) \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1146 2. for $n$ from 0 to $a.used - 1$ do \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1147 \hspace{3mm}2.1 $b_{n} \leftarrow a_{n}$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1148 3. for $n$ from $a.used$ to $b.used - 1$ do \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1149 \hspace{3mm}3.1 $b_{n} \leftarrow 0$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1150 4. $b.used \leftarrow a.used$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1151 5. $b.sign \leftarrow a.sign$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1152 6. return(\textit{MP\_OKAY}) \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1153 \hline
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1154 \end{tabular}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1155 \end{center}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1156 \caption{Algorithm mp\_copy}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1157 \end{figure}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1158
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1159 \textbf{Algorithm mp\_copy.}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1160 This algorithm copies the mp\_int $a$ such that upon succesful termination of the algorithm the mp\_int $b$ will
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1161 represent the same integer as the mp\_int $a$. The mp\_int $b$ shall be a complete and distinct copy of the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1162 mp\_int $a$ meaing that the mp\_int $a$ can be modified and it shall not affect the value of the mp\_int $b$.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1163
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1164 If $b$ does not have enough room for the digits of $a$ it must first have its precision augmented via the mp\_grow
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1165 algorithm. The digits of $a$ are copied over the digits of $b$ and any excess digits of $b$ are set to zero (step two
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1166 and three). The \textbf{used} and \textbf{sign} members of $a$ are finally copied over the respective members of
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1167 $b$.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1168
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1169 \textbf{Remark.} This algorithm also introduces a new idiosyncrasy that will be used throughout the rest of the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1170 text. The error return codes of other algorithms are not explicitly checked in the pseudo-code presented. For example, in
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1171 step one of the mp\_copy algorithm the return of mp\_grow is not explicitly checked to ensure it succeeded. Text space is
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1172 limited so it is assumed that if a algorithm fails it will clear all temporarily allocated mp\_ints and return
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1173 the error code itself. However, the C code presented will demonstrate all of the error handling logic required to
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1174 implement the pseudo-code.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1175
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1176 EXAM,bn_mp_copy.c
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1177
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1178 Occasionally a dependent algorithm may copy an mp\_int effectively into itself such as when the input and output
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1179 mp\_int structures passed to a function are one and the same. For this case it is optimal to return immediately without
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1180 copying digits (line @24,a == [email protected]).
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1181
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1182 The mp\_int $b$ must have enough digits to accomodate the used digits of the mp\_int $a$. If $b.alloc$ is less than
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1183 $a.used$ the algorithm mp\_grow is used to augment the precision of $b$ (lines @29,[email protected] to @33,}@). In order to
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1184 simplify the inner loop that copies the digits from $a$ to $b$, two aliases $tmpa$ and $tmpb$ point directly at the digits
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1185 of the mp\_ints $a$ and $b$ respectively. These aliases (lines @42,[email protected] and @45,[email protected]) allow the compiler to access the digits without first dereferencing the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1186 mp\_int pointers and then subsequently the pointer to the digits.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1187
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1188 After the aliases are established the digits from $a$ are copied into $b$ (lines @48,[email protected] to @50,}@) and then the excess
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1189 digits of $b$ are set to zero (lines @53,[email protected] to @55,}@). Both ``for'' loops make use of the pointer aliases and in
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1190 fact the alias for $b$ is carried through into the second ``for'' loop to clear the excess digits. This optimization
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1191 allows the alias to stay in a machine register fairly easy between the two loops.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1192
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1193 \textbf{Remarks.} The use of pointer aliases is an implementation methodology first introduced in this function that will
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1194 be used considerably in other functions. Technically, a pointer alias is simply a short hand alias used to lower the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1195 number of pointer dereferencing operations required to access data. For example, a for loop may resemble
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1196
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1197 \begin{alltt}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1198 for (x = 0; x < 100; x++) \{
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1199 a->num[4]->dp[x] = 0;
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1200 \}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1201 \end{alltt}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1202
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1203 This could be re-written using aliases as
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1204
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1205 \begin{alltt}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1206 mp_digit *tmpa;
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1207 a = a->num[4]->dp;
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1208 for (x = 0; x < 100; x++) \{
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1209 *a++ = 0;
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1210 \}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1211 \end{alltt}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1212
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1213 In this case an alias is used to access the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1214 array of digits within an mp\_int structure directly. It may seem that a pointer alias is strictly not required
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1215 as a compiler may optimize out the redundant pointer operations. However, there are two dominant reasons to use aliases.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1216
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1217 The first reason is that most compilers will not effectively optimize pointer arithmetic. For example, some optimizations
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1218 may work for the Microsoft Visual C++ compiler (MSVC) and not for the GNU C Compiler (GCC). Also some optimizations may
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1219 work for GCC and not MSVC. As such it is ideal to find a common ground for as many compilers as possible. Pointer
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1220 aliases optimize the code considerably before the compiler even reads the source code which means the end compiled code
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1221 stands a better chance of being faster.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1222
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1223 The second reason is that pointer aliases often can make an algorithm simpler to read. Consider the first ``for''
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1224 loop of the function mp\_copy() re-written to not use pointer aliases.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1225
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1226 \begin{alltt}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1227 /* copy all the digits */
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1228 for (n = 0; n < a->used; n++) \{
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1229 b->dp[n] = a->dp[n];
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1230 \}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1231 \end{alltt}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1232
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1233 Whether this code is harder to read depends strongly on the individual. However, it is quantifiably slightly more
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1234 complicated as there are four variables within the statement instead of just two.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1235
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1236 \subsubsection{Nested Statements}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1237 Another commonly used technique in the source routines is that certain sections of code are nested. This is used in
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1238 particular with the pointer aliases to highlight code phases. For example, a Comba multiplier (discussed in chapter six)
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1239 will typically have three different phases. First the temporaries are initialized, then the columns calculated and
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1240 finally the carries are propagated. In this example the middle column production phase will typically be nested as it
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1241 uses temporary variables and aliases the most.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1242
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1243 The nesting also simplies the source code as variables that are nested are only valid for their scope. As a result
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1244 the various temporary variables required do not propagate into other sections of code.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1245
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1246
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1247 \subsection{Creating a Clone}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1248 Another common operation is to make a local temporary copy of an mp\_int argument. To initialize an mp\_int
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1249 and then copy another existing mp\_int into the newly intialized mp\_int will be known as creating a clone. This is
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1250 useful within functions that need to modify an argument but do not wish to actually modify the original copy. The
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1251 mp\_init\_copy algorithm has been designed to help perform this task.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1252
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1253 \begin{figure}[here]
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1254 \begin{center}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1255 \begin{tabular}{l}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1256 \hline Algorithm \textbf{mp\_init\_copy}. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1257 \textbf{Input}. An mp\_int $a$ and $b$\\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1258 \textbf{Output}. $a$ is initialized to be a copy of $b$. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1259 \hline \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1260 1. Init $a$. (\textit{mp\_init}) \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1261 2. Copy $b$ to $a$. (\textit{mp\_copy}) \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1262 3. Return the status of the copy operation. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1263 \hline
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1264 \end{tabular}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1265 \end{center}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1266 \caption{Algorithm mp\_init\_copy}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1267 \end{figure}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1268
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1269 \textbf{Algorithm mp\_init\_copy.}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1270 This algorithm will initialize an mp\_int variable and copy another previously initialized mp\_int variable into it. As
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1271 such this algorithm will perform two operations in one step.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1272
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1273 EXAM,bn_mp_init_copy.c
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1274
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1275 This will initialize \textbf{a} and make it a verbatim copy of the contents of \textbf{b}. Note that
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1276 \textbf{a} will have its own memory allocated which means that \textbf{b} may be cleared after the call
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1277 and \textbf{a} will be left intact.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1278
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1279 \section{Zeroing an Integer}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1280 Reseting an mp\_int to the default state is a common step in many algorithms. The mp\_zero algorithm will be the algorithm used to
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1281 perform this task.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1282
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1283 \begin{figure}[here]
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1284 \begin{center}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1285 \begin{tabular}{l}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1286 \hline Algorithm \textbf{mp\_zero}. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1287 \textbf{Input}. An mp\_int $a$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1288 \textbf{Output}. Zero the contents of $a$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1289 \hline \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1290 1. $a.used \leftarrow 0$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1291 2. $a.sign \leftarrow$ MP\_ZPOS \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1292 3. for $n$ from 0 to $a.alloc - 1$ do \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1293 \hspace{3mm}3.1 $a_n \leftarrow 0$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1294 \hline
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1295 \end{tabular}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1296 \end{center}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1297 \caption{Algorithm mp\_zero}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1298 \end{figure}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1299
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1300 \textbf{Algorithm mp\_zero.}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1301 This algorithm simply resets a mp\_int to the default state.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1302
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1303 EXAM,bn_mp_zero.c
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1304
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1305 After the function is completed, all of the digits are zeroed, the \textbf{used} count is zeroed and the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1306 \textbf{sign} variable is set to \textbf{MP\_ZPOS}.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1307
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1308 \section{Sign Manipulation}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1309 \subsection{Absolute Value}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1310 With the mp\_int representation of an integer, calculating the absolute value is trivial. The mp\_abs algorithm will compute
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1311 the absolute value of an mp\_int.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1312
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1313 \newpage\begin{figure}[here]
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1314 \begin{center}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1315 \begin{tabular}{l}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1316 \hline Algorithm \textbf{mp\_abs}. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1317 \textbf{Input}. An mp\_int $a$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1318 \textbf{Output}. Computes $b = \vert a \vert$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1319 \hline \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1320 1. Copy $a$ to $b$. (\textit{mp\_copy}) \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1321 2. If the copy failed return(\textit{MP\_MEM}). \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1322 3. $b.sign \leftarrow MP\_ZPOS$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1323 4. Return(\textit{MP\_OKAY}) \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1324 \hline
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1325 \end{tabular}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1326 \end{center}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1327 \caption{Algorithm mp\_abs}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1328 \end{figure}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1329
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1330 \textbf{Algorithm mp\_abs.}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1331 This algorithm computes the absolute of an mp\_int input. First it copies $a$ over $b$. This is an example of an
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1332 algorithm where the check in mp\_copy that determines if the source and destination are equal proves useful. This allows,
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1333 for instance, the developer to pass the same mp\_int as the source and destination to this function without addition
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1334 logic to handle it.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1335
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1336 EXAM,bn_mp_abs.c
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1337
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1338 \subsection{Integer Negation}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1339 With the mp\_int representation of an integer, calculating the negation is also trivial. The mp\_neg algorithm will compute
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1340 the negative of an mp\_int input.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1341
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1342 \begin{figure}[here]
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1343 \begin{center}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1344 \begin{tabular}{l}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1345 \hline Algorithm \textbf{mp\_neg}. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1346 \textbf{Input}. An mp\_int $a$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1347 \textbf{Output}. Computes $b = -a$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1348 \hline \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1349 1. Copy $a$ to $b$. (\textit{mp\_copy}) \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1350 2. If the copy failed return(\textit{MP\_MEM}). \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1351 3. If $a.used = 0$ then return(\textit{MP\_OKAY}). \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1352 4. If $a.sign = MP\_ZPOS$ then do \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1353 \hspace{3mm}4.1 $b.sign = MP\_NEG$. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1354 5. else do \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1355 \hspace{3mm}5.1 $b.sign = MP\_ZPOS$. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1356 6. Return(\textit{MP\_OKAY}) \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1357 \hline
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1358 \end{tabular}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1359 \end{center}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1360 \caption{Algorithm mp\_neg}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1361 \end{figure}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1362
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1363 \textbf{Algorithm mp\_neg.}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1364 This algorithm computes the negation of an input. First it copies $a$ over $b$. If $a$ has no used digits then
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1365 the algorithm returns immediately. Otherwise it flips the sign flag and stores the result in $b$. Note that if
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1366 $a$ had no digits then it must be positive by definition. Had step three been omitted then the algorithm would return
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1367 zero as negative.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1368
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1369 EXAM,bn_mp_neg.c
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1370
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1371 \section{Small Constants}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1372 \subsection{Setting Small Constants}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1373 Often a mp\_int must be set to a relatively small value such as $1$ or $2$. For these cases the mp\_set algorithm is useful.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1374
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1375 \begin{figure}[here]
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1376 \begin{center}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1377 \begin{tabular}{l}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1378 \hline Algorithm \textbf{mp\_set}. \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1379 \textbf{Input}. An mp\_int $a$ and a digit $b$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1380 \textbf{Output}. Make $a$ equivalent to $b$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1381 \hline \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1382 1. Zero $a$ (\textit{mp\_zero}). \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1383 2. $a_0 \leftarrow b \mbox{ (mod }\beta\mbox{)}$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1384 3. $a.used \leftarrow \left \lbrace \begin{array}{ll}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1385 1 & \mbox{if }a_0 > 0 \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1386 0 & \mbox{if }a_0 = 0
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1387 \end{array} \right .$ \\
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1388 \hline
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1389 \end{tabular}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1390 \end{center}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1391 \caption{Algorithm mp\_set}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1392 \end{figure}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1393
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1394 \textbf{Algorithm mp\_set.}
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1395 This algorithm sets a mp\_int to a small single digit value. Step number 1 ensures that the integer is reset to the default state. The
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1396 single digit is set (\textit{modulo $\beta$}) and the \textbf{used} count is adjusted accordingly.
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1397
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1398 EXAM,bn_mp_set.c
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1399
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1400 Line @21,mp_[email protected] calls mp\_zero() to clear the mp\_int and reset the sign. Line @22,MP_[email protected] copies the digit
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1401 into the least significant location. Note the usage of a new constant \textbf{MP\_MASK}. This constant is used to quickly
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1402 reduce an integer modulo $\beta$. Since $\beta$ is of the form $2^k$ for any suitable $k$ it suffices to perform a binary AND with
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1403 $MP\_MASK = 2^k - 1$ to perform the reduction. Finally line @23,a->[email protected] will set the \textbf{used} member with respect to the
e1037a1e12e7 0.30 release of LibTomMath
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1404 digit actually set. This function will always make the integer positive.