Improved Arithmetic in the Ideal Class Group of Imaginary Quadratic Number Fields with an Application to Integer Factoring
Date
2013-06-14
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This thesis proposes practical improvements to arithmetic and exponentiation in the ideal class group of imaginary quadratic number fields for the Intel x64 architecture. This is useful in tabulating the class number and class group structure, but also as an application to a novel integer factoring algorithm called “SuperSPAR”. SuperSPAR builds upon SPAR using an idea from Sutherland, namely a bounded primorial steps search, as well as by using optimized double-based representations of exponents, and general improvements to arithmetic in the ideal class group.
Since the target architecture has 64 bit machine words, we specialize two implementations of ideal class arithmetic: one using 64 bit arithmetic, and the other using 128 bit arithmetic. In each case, our results show an improvement in the average performance of ideal class arithmetic over reference implementations. Since much of the effort of ideal class arithmetic is in computing the extended greatest common divisor, this thesis studies the average performance of several implementations of this and shows an improvement for some over reference implementations. Dimitrov and Cooklev propose the double base number system, and Imbert, Jacobson, and Schmidt propose a method of ideal class cubing. Using these ideas, we explore several techniques for exponentiation using 2,3 number systems and demonstrate an improvement in the average performance of exponentiation in the ideal class group over that of binary exponentiation. Lastly, each of these improvements are applied to our implementation of the SuperSPAR factoring algorithm, and our results show an improvement in the average time to factor integers 49 bits to 62 bits in size.
Description
Keywords
Computer Science
Citation
Sayles, M. (2013). Improved Arithmetic in the Ideal Class Group of Imaginary Quadratic Number Fields with an Application to Integer Factoring (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca. doi:10.11575/PRISM/26473