tommath.tex

tommath库

\documentclass[b5paper]{book}
\usepackage{hyperref}
\usepackage{makeidx}
\usepackage{amssymb}
\usepackage{color}
\usepackage{alltt}
\usepackage{graphicx}
\usepackage{layout}
\def\union{\cup}
\def\intersect{\cap}
\def\getsrandom{\stackrel{\rm R}{\gets}}
\def\cross{\times}
\def\cat{\hspace{0.5em} \| \hspace{0.5em}}
\def\catn{$\|$}
\def\divides{\hspace{0.3em} | \hspace{0.3em}}
\def\nequiv{\not\equiv}
\def\approx{\raisebox{0.2ex}{\mbox{\small $\sim$}}}
\def\lcm{{\rm lcm}}
\def\gcd{{\rm gcd}}
\def\log{{\rm log}}
\def\ord{{\rm ord}}
\def\abs{{\mathit abs}}
\def\rep{{\mathit rep}}
\def\mod{{\mathit\ mod\ }}
\renewcommand{\pmod}[1]{\ ({\rm mod\ }{#1})}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\def\Or{{\rm\ or\ }}
\def\And{{\rm\ and\ }}
\def\iff{\hspace{1em}\Longleftrightarrow\hspace{1em}}
\def\implies{\Rightarrow}
\def\undefined{{\rm ``undefined"}}
\def\Proof{\vspace{1ex}\noindent {\bf Proof:}\hspace{1em}}
\let\oldphi\phi
\def\phi{\varphi}
\def\Pr{{\rm Pr}}
\newcommand{\str}[1]{{\mathbf{#1}}}
\def\F{{\mathbb F}}
\def\N{{\mathbb N}}
\def\Z{{\mathbb Z}}
\def\R{{\mathbb R}}
\def\C{{\mathbb C}}
\def\Q{{\mathbb Q}}
\definecolor{DGray}{gray}{0.5}
\newcommand{\emailaddr}[1]{\mbox{$<${#1}$>$}}
\def\twiddle{\raisebox{0.3ex}{\mbox{\tiny $\sim$}}}
\def\gap{\vspace{0.5ex}}
\makeindex
\begin{document}
\frontmatter
\pagestyle{empty}
\title{Implementing Multiple Precision Arithmetic \\ ~ \\ Draft Edition }
\author{\mbox{
%\begin{small}
\begin{tabular}{c}
Tom St Denis \\
Algonquin College \\
\\
Mads Rasmussen \\
Open Communications Security \\
\\
Greg Rose \\
QUALCOMM Australia \\
\end{tabular}
%\end{small}
}
}
\maketitle
This text has been placed in the public domain.  This text corresponds to the v0.30 release of the 
LibTomMath project.

\begin{alltt}
Tom St Denis
111 Banning Rd
Ottawa, Ontario
K2L 1C3
Canada

Phone: [phone]
Email: [e-mail]
\end{alltt}

This text is formatted to the international B5 paper size of 176mm wide by 250mm tall using the \LaTeX{} 
{\em book} macro package and the Perl {\em booker} package.

\tableofcontents
\listoffigures
\chapter*{Prefaces to the Draft Edition}
I started this text in April 2003 to complement my LibTomMath library.  That is, explain how to implement the functions
contained in LibTomMath.  The goal is to have a textbook that any Computer Science student can use when implementing their
own multiple precision arithmetic.  The plan I wanted to follow was flesh out all the
ideas and concepts I had floating around in my head and then work on it afterwards refining a little bit at a time.  Chance
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
text.  

Choosing to not waste any time I dove right into the project even before my spring semester was finished.  I wrote a bit
off and on at first.  The moment my exams were finished I jumped into long 12 to 16 hour days.  The result after only
a couple of months was a ten chapter, three hundred page draft that I quickly had distributed to anyone who wanted
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
managed to grab a certain level of attention having people from around the world ask me for copies of the text was certain
rewarding.

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.  
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
finished yet.  I haven't given up on the project, only had some setbacks.  First O'Reilly declined to publish the text then
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
onto finishing the book not securing a contract.

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.  
Even the simplest introductory material has to be lined with references and figures.  A lot of the text has to be re-written
from point form to prose form to ensure an easier read.  Why am I doing all this work for free then?  Simple. My philosophy
is quite simply ``Open Source.  Open Academia.  Open Minds'' which means that to achieve a goal of open minds, that is,
people willing to accept new ideas and explore the unknown you have to make available material they can access freely 
without hinderance.  

I've been writing free software since I was about sixteen but only recently have I hit upon software that people have come
to depend upon.  I started LibTomCrypt in December 2001 and now several major companies use it as integral portions of their
software.  Several educational institutions use it as a matter of course and many freelance developers use it as
part of their projects.  To further my contributions I started the LibTomMath project in December 2002 aimed at providing
multiple precision arithmetic routines that students could learn from.  That is write routines that are not only easy
to understand and follow but provide quite impressive performance considering they are all in standard portable ISO C.  

The second leg of my philosophy is ``Open Academia'' which is where this textbook comes in.  In the end, when all is
said and done the text will be useable by educational institutions as a reference on multiple precision arithmetic.  

At this time I feel I should share a little information about myself.  The most common question I was asked at 
Crypto'03, perhaps just out of professional courtesy, was which school I either taught at or attended.  The unfortunate
truth is that I neither teach at or attend a school of academic reputation.  I'm currently at Algonquin College which 
is what I'd like to call ``somewhat academic but mostly vocational'' college.  In otherwords, job training.

I'm a 21 year old computer science student mostly self-taught in the areas I am aware of (which includes a half-dozen
computer science fields, a few fields of mathematics and some English).  I look forward to teaching someday but I am
still far off from that goal.  

Now it would be improper for me to not introduce the rest of the texts co-authors.  While they are only contributing 
corrections and editorial feedback their support has been tremendously helpful in presenting the concepts laid out
in the text so far.  Greg has always been there for me.  He has tracked my LibTom projects since their inception and even
sent cheques to help pay tuition from time to time.  His background has provided a wonderful source to bounce ideas off
of and improve the quality of my writing.  Mads is another fellow who has just ``been there''.  I don't even recall what
his interest in the LibTom projects is but I'm definitely glad he has been around.  His ability to catch logical errors
in my written English have saved me on several occasions to say the least.

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
been getting the feeling that people are starting to use my text and I owe them some updated material.  My current tenative
plan is to edit one chapter every two weeks starting January 4th.  It seems insane but my lower course load at college
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
people who will take it.

\begin{flushright} Tom St Denis \end{flushright}

\newpage
I found the opportunity to work with Tom appealing for several reasons, not only could I broaden my own horizons, but also 
contribute to educate others facing the problem of having to handle big number mathematical calculations.

This book is Tom's child and he has been caring and fostering the project ever since the beginning with a clear mind of 
how he wanted the project to turn out. I have helped by proofreading the text and we have had several discussions about 
the layout and language used.

I hold a masters degree in cryptography from the University of Southern Denmark and have always been interested in the 
practical aspects of cryptography. 

Having worked in the security consultancy business for several years in S\~{a}o Paulo, Brazil, I have been in touch with a 
great deal of work in which multiple precision mathematics was needed. Understanding the possibilities for speeding up 
multiple precision calculations is often very important since we deal with outdated machine architecture where modular 
reductions, for example, become painfully slow.

This text is for people who stop and wonder when first examining algorithms such as RSA for the first time and asks 
themselves, ``You tell me this is only secure for large numbers, fine; but how do you implement these numbers?''

\begin{flushright}
Mads Rasmussen

S\~{a}o Paulo - SP

Brazil
\end{flushright}

\newpage
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 
Karatsuba multiplication. I was laid up, alone and immobile, and thought ``Why not?'' I vaguely knew what Karatsuba multiplication was, but not 
really, so I thought I could help, learn, and stop myself from watching daytime cable TV, all at once.

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 
sci.crypt Usenet news group. I watched him go from a clueless newbie, to the cryptographic equivalent of a reformed smoker, to a real
contributor to the field, over a period of about two years. I've been impressed with his obvious intelligence, and astounded by his productivity. 
Of course, he's young enough to be my own child, so he doesn't have my problems with staying awake.

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, 
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 
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, 
and I'm pleased to be involved with it.

\begin{flushright}
Greg Rose, Sydney, Australia, June 2003. 
\end{flushright}

\mainmatter
\pagestyle{headings}
\chapter{Introduction}
\section{Multiple Precision Arithmetic}

\subsection{What is Multiple Precision Arithmetic?}
When we think of long-hand arithmetic such as addition or multiplication we rarely consider the fact that we instinctively
raise or lower the precision of the numbers we are dealing with.  For example, in decimal we almost immediate can 
reason that $7$ times $6$ is $42$.  However, $42$ has two digits of precision as opposed to one digit we started with.  
Further multiplications of say $3$ result in a larger precision result $126$.  In these few examples we have multiple 
precisions for the numbers we are working with.  Despite the various levels of precision a single subset\footnote{With the occasional optimization.}
 of algorithms can be designed to accomodate them.  

By way of comparison a fixed or single precision operation would lose precision on various operations.  For example, in
the decimal system with fixed precision $6 \cdot 7 = 2$.

Essentially at the heart of computer based multiple precision arithmetic are the same long-hand algorithms taught in