{"id":{"repo_id":"uwo","oai_identifier":"oai:uwo.scholaris.ca:20.500.14721/28127"},"canonical_url":"https://search.dev.ndltd.org/etd/uwo/oai:uwo.scholaris.ca:20.500.14721/28127","repository":{"repo_id":"uwo","name":"Western University","base_url":"https://uwo.scholaris.ca/server/oai/request"},"display":{"title":"Putting Fürer's Algorithm into Practice with the BPAS Library","abstract":"Fast algorithms for integer and polynomial multiplication play an important role in scientific computing as well as other disciplines. In 1971, Schönhage and Strassen designed an algorithm that improved the multiplication time for two integers of at most n bits to O(log n log log n). In 2007, Martin Fürer presented a new algorithm that runs in O (n log n · 2 ^O(log* n)) , where log*n is the iterated logarithm of n. We explain how we can put Fürer’s ideas into practice for multiplying polynomials over a prime field Z/pZ, which characteristic is a Generalized Fermat prime of the form p = r^k + 1 where k is a power of 2 and r is of machine word size. When k is at least 8, we show that multiplication inside such a prime field can be efficiently implemented via Fast Fourier Transform (FFT). Taking advantage of Cooley-Tukey tensor formula and the fact that r is a 2k-th primitive root of unity, we obtain an efficient implementation of FFT over Z/pZ. This implementation outperforms comparable implementations either using other encodings of Z/pZ or other ways to perform multiplication in Z/pZ.","abstract_html":"Fast algorithms for integer and polynomial multiplication play an important role in scientific computing as well as other disciplines. In 1971, Schönhage and Strassen designed an algorithm that improved the multiplication time for two integers of at most n bits to O(log n log log n). In 2007, Martin Fürer presented a new algorithm that runs in O (n log n · 2 ^O(log* n)) , where log*n is the iterated logarithm of n. We explain how we can put Fürer’s ideas into practice for multiplying polynomials over a prime field Z/pZ, which characteristic is a Generalized Fermat prime of the form p = r^k + 1 where k is a power of 2 and r is of machine word size. When k is at least 8, we show that multiplication inside such a prime field can be efficiently implemented via Fast Fourier Transform (FFT). Taking advantage of Cooley-Tukey tensor formula and the fact that r is a 2k-th primitive root of unity, we obtain an efficient implementation of FFT over Z/pZ. This implementation outperforms comparable implementations either using other encodings of Z/pZ or other ways to perform multiplication in Z/pZ.","abstract_has_math":false,"creators":["Wang, Linxiao"],"institution":"The University of Western Ontario","degree_name":"M Sc","degree_level":null,"degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":["Moreno Maza, Marc"],"committee_chairs":[],"committee_members":[],"year":2018,"date_issued":"2018-04-24","date_published":"2018-04-24","updated_at":"2026-07-27T21:56:11Z","subjects":["Furer's algorithm","Fast Fourier Transform","Generalized Fermat prime","Polynomial multiplication"],"languages":["en_ca"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/20.500.14721/28127","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Moreno Maza, Marc"]},{"key":"dc:creator","label":"Author","values":["Wang, Linxiao"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2025-07-10T16:07:51Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2025-07-10T16:07:51Z"]},{"key":"dc:date.issued","label":"Date","values":["2018-04-24"]},{"key":"dc:publisher","label":"Institution","values":["The University of Western Ontario"]},{"key":"dc:type","label":"Dc Type","values":["thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M Sc"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Furer's algorithm","Fast Fourier Transform","Generalized Fermat prime","Polynomial multiplication"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_ca"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/20.500.14721/28127"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["The thesis cover page in the PDF document includes references to Western University’s previous institutional repository platform, known as Scholarship@Western, and links to that platform (beginning with ir.lib.uwo.ca). In citing or referring to this thesis, use the DOI or handle from this page instead. Sample citation: Author name, \"Thesis title.\" (Year). Western University Open Repository. https://doi.org/10.71858/123456."]},{"key":"dc:description.abstract","label":"Abstract","values":["Fast algorithms for integer and polynomial multiplication play an important role in scientific computing as well as other disciplines. In 1971, Schönhage and Strassen designed an algorithm that improved the multiplication time for two integers of at most n bits to O(log n log log n). In 2007, Martin Fürer presented a new algorithm that runs in O (n log n · 2 ^O(log* n)) , where log*n is the iterated logarithm of n. We explain how we can put Fürer’s ideas into practice for multiplying polynomials over a prime field Z/pZ, which characteristic is a Generalized Fermat prime of the form p = r^k + 1 where k is a power of 2 and r is of machine word size. When k is at least 8, we show that multiplication inside such a prime field can be efficiently implemented via Fast Fourier Transform (FFT). Taking advantage of Cooley-Tukey tensor formula and the fact that r is a 2k-th primitive root of unity, we obtain an efficient implementation of FFT over Z/pZ. This implementation outperforms comparable implementations either using other encodings of Z/pZ or other ways to perform multiplication in Z/pZ."]},{"key":"dc:title","label":"Title","values":["Putting Fürer's Algorithm into Practice with the BPAS Library"]}]}],"canonical_facts":{"dc:contributor.advisor":["Moreno Maza, Marc"],"dc:creator":["Wang, Linxiao"],"dc:date.accessioned":["2025-07-10T16:07:51Z"],"dc:date.available":["2025-07-10T16:07:51Z"],"dc:date.issued":["2018-04-24"],"dc:description":["The thesis cover page in the PDF document includes references to Western University’s previous institutional repository platform, known as Scholarship@Western, and links to that platform (beginning with ir.lib.uwo.ca). In citing or referring to this thesis, use the DOI or handle from this page instead. Sample citation: Author name, \"Thesis title.\" (Year). Western University Open Repository. https://doi.org/10.71858/123456."],"dc:description.abstract":["Fast algorithms for integer and polynomial multiplication play an important role in scientific computing as well as other disciplines. In 1971, Schönhage and Strassen designed an algorithm that improved the multiplication time for two integers of at most n bits to O(log n log log n). In 2007, Martin Fürer presented a new algorithm that runs in O (n log n · 2 ^O(log* n)) , where log*n is the iterated logarithm of n. We explain how we can put Fürer’s ideas into practice for multiplying polynomials over a prime field Z/pZ, which characteristic is a Generalized Fermat prime of the form p = r^k + 1 where k is a power of 2 and r is of machine word size. When k is at least 8, we show that multiplication inside such a prime field can be efficiently implemented via Fast Fourier Transform (FFT). Taking advantage of Cooley-Tukey tensor formula and the fact that r is a 2k-th primitive root of unity, we obtain an efficient implementation of FFT over Z/pZ. This implementation outperforms comparable implementations either using other encodings of Z/pZ or other ways to perform multiplication in Z/pZ."],"dc:identifier.uri":["https://hdl.handle.net/20.500.14721/28127"],"dc:language.iso":["en_ca"],"dc:publisher":["The University of Western Ontario"],"dc:subject":["Furer's algorithm","Fast Fourier Transform","Generalized Fermat prime","Polynomial multiplication"],"dc:title":["Putting Fürer's Algorithm into Practice with the BPAS Library"],"dc:type":["thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_name":["M Sc"]},"updated_at":"2026-07-27T21:56:11Z"}