Error detection in number theoretic algorithms
by
Troy Michael John Vasiga
A thesis
presented to the University of Waterloo
in ful lment of the
thesis requirement for the degree of
Doctor of Philosophy
in
Computer Science
Waterloo, Ontario, Canada, 2006
c
Troy Michael John Vasiga 2006
I hereby declare that I am the sole author of this thesis.
I authorize the University of Waterloo to lend this thesis to other institutions
or individuals for the purpose of scholarly research.
I further authorize the University of Waterloo to reproduce this thesis by pho-
tocopying or by other means, in total or in part, at the request of other institutions
or individuals for the purpose of scholarly research.
ii
The University of Waterloo requires the signatures of all persons using or pho-
tocopying this thesis. Please sign below, and give address and date.
iii
Abstract
CPU's are unreliable: at any point, a bit may be altered with some (small) proba-
bility. This probability may seem neglible, but for large calculations (i.e. weeks of
CPU time), the likelihood of an error being introduced becomings increasingly com-
mon. This thesis examines several number theoretic algorithms in this light, and
classi es them in terms of their soundness based on their execution on unreliable
CPU's.
iv
Acknowledgements
Everyone and anyone.
v
Trademarks
vi
Contents
1 Introduction and Motivation 1
1.1 Self-checking algorithms . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 A computational model . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Error model for computation . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Other Motivational areas . . . . . . . . . . . . . . . . . . . . . . . . 8
Bibliography 10
vii
List of Tables
viii
List of Figures
ix
Chapter 1
Introduction and Motivation
Computers currently are, and always have been, unreliable.
Historically, when \computers" were those people who calculated extensive
arithmetic formulae (sequences, factors of integers, logarithms of integers, etc.)
mistakes (such as an incorrectly written digit, or transposed digits) would invari-
ably occur.
For example, the French mathematician Edouard Lucas devoted some of his
computational energy towards determining perfect numbers. Recall that a perfect
number is a positive integer n such that
P
xjn
1 x