Improved Arithmetic in the Ideal Class Group of Imaginary Quadratic Number Fields with an Application to Integer Factoring

Simple item page
atmire.migration.oldid1044
dc.contributor.advisorJacobson, Michael John
dc.contributor.authorSayles, Maxwell
dc.date.accessioned2013-06-14T17:59:48Z
dc.date.available2013-11-12T08:00:12Z
dc.date.issued2013-06-14
dc.date.submitted2013en
dc.description.abstractThis 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.en_US
dc.identifier.citationSayles, 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/26473en_US
dc.identifier.doihttp://dx.doi.org/10.11575/PRISM/26473
dc.identifier.urihttp://hdl.handle.net/11023/752
dc.language.isoeng
dc.publisher.facultyGraduate Studies
dc.publisher.institutionUniversity of Calgaryen
dc.publisher.placeCalgaryen
dc.rightsUniversity of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission.
dc.subjectComputer Science
dc.subject.classificationIdeal Class Groupen_US
dc.subject.classificationQuadratic Fielden_US
dc.subject.classificationInteger Factoringen_US
dc.titleImproved Arithmetic in the Ideal Class Group of Imaginary Quadratic Number Fields with an Application to Integer Factoring
dc.typemaster thesis
thesis.degree.disciplineComputer Science
thesis.degree.grantorUniversity of Calgary
thesis.degree.nameMaster of Science (MSc)
ucalgary.item.requestcopytrue
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
ucalgary_2013_sayles_maxwell.pdf
Size:
1.48 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
2.65 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Open Theses and Dissertations