{"id":{"repo_id":"usf","oai_identifier":"oai:digitalcommons.usf.edu:etd-11750"},"canonical_url":"https://search.ndltd.org/etd/usf/oai:digitalcommons.usf.edu:etd-11750","repository":{"repo_id":"usf","name":"University of South Florida","base_url":"https://digitalcommons.usf.edu/do/oai/"},"display":{"title":"Recovering generators of principal ideals using subfield structure and applications to cryptography","abstract":"The principal ideal problem (PIP) is the problem of determining if a given ideal of a number field is principal, and if so, of finding a generator.Algorithms for resolving the PIP can be efficiently adapted to solve many hard problems in algebraic number theory, such as the computation of the class group, unit group, or $S$-unit group of a number field. The PIP is also connected to the search for approximate short vectors, known as the $\\gamma$-Shortest Vector Problem ($\\gamma$-SVP), in certain structured lattices called ideal lattices, which are prevalent in cryptography. We present an algorithm for resolving the PIP that leverages the norm relation techniques of Biasse, Fieker, Hofmann, and Page to efficiently reduce the PIP in a non-cyclic number field to instances of the PIP in subfields. Our algorithm is focused on practical performance and we demonstrate its viability by resolving instances of the PIP in cyclotomic fields of degree up to 1800. We further adapt this technique to the problem of finding mildly short vectors, solutions to $\\gamma$-SVP for $\\gamma = 2^{\\tilde{O}(\\sqrt{n})}$, in an ideal lattice of a cyclotomic field. Cramer, Ducas, and Wesolowski show that the search for mildly short vectors in such a lattice reduces efficiently to the PIP on a quantum computer. We describe a classical variant of this reduction that applies to non-cyclic cyclotomic fields. We show that there are infinite families of cyclotomic fields where this approach achieves a superpolynomial improvement over the state of the art.","abstract_html":"The principal ideal problem (PIP) is the problem of determining if a given ideal of a number field is principal, and if so, of finding a generator.Algorithms for resolving the PIP can be efficiently adapted to solve many hard problems in algebraic number theory, such as the computation of the class group, unit group, or $S$-unit group of a number field. The PIP is also connected to the search for approximate short vectors, known as the <span class=\"etd-inline-math\">&gamma;</span>-Shortest Vector Problem (<span class=\"etd-inline-math\">&gamma;</span>-SVP), in certain structured lattices called ideal lattices, which are prevalent in cryptography. We present an algorithm for resolving the PIP that leverages the norm relation techniques of Biasse, Fieker, Hofmann, and Page to efficiently reduce the PIP in a non-cyclic number field to instances of the PIP in subfields. Our algorithm is focused on practical performance and we demonstrate its viability by resolving instances of the PIP in cyclotomic fields of degree up to 1800. We further adapt this technique to the problem of finding mildly short vectors, solutions to <span class=\"etd-inline-math\">&gamma;</span>-SVP for <span class=\"etd-inline-math\">&gamma; = 2<sup>\\tilde{O}(\\sqrt{n})</sup></span>, in an ideal lattice of a cyclotomic field. Cramer, Ducas, and Wesolowski show that the search for mildly short vectors in such a lattice reduces efficiently to the PIP on a quantum computer. We describe a classical variant of this reduction that applies to non-cyclic cyclotomic fields. We show that there are infinite families of cyclotomic fields where this approach achieves a superpolynomial improvement over the state of the art.","abstract_has_math":true,"creators":["Youmans, William"],"institution":"University of South Florida","degree_name":"Doctor of Philosophy (Ph.D.)","degree_level":"Dissertation","degree_discipline":"Mathematics and Statistics","degree_department":null,"school":null,"contributors":["Jean-Francois Biasse, Ph.D.","Dmytro Savchuk, Ph.D.","Natasa Jonoska, Ph.D.","Giacomo Micheli, Ph.D.","Attila Yavuz, Ph.D."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023-03-31T07:00:00Z","date_published":"2023-03-31T07:00:00Z","updated_at":"2026-11-19T08:50:23Z","subjects":["Ideal Lattice","Cyclotomic Field","Approximate Short Vector Problem","Ideal Class Group","S-unit Group","Mathematics"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.usf.edu/etd/10463","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.usf.edu/etd/10463","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.usf.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.usf.edu%3Aetd-11750","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Jean-Francois Biasse, Ph.D.","Dmytro Savchuk, Ph.D.","Natasa Jonoska, Ph.D.","Giacomo Micheli, Ph.D.","Attila Yavuz, Ph.D."]},{"key":"dc:creator","label":"Author","values":["Youmans, William"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2023-03-31T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics and Statistics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation","Ph.D."]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy (Ph.D.)"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of South Florida"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Ideal Lattice","Cyclotomic Field","Approximate Short Vector Problem","Ideal Class Group","S-unit Group","Mathematics"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.usf.edu/etd/10463"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["The principal ideal problem (PIP) is the problem of determining if a given ideal of a number field is principal, and if so, of finding a generator.Algorithms for resolving the PIP can be efficiently adapted to solve many hard problems in algebraic number theory, such as the computation of the class group, unit group, or $S$-unit group of a number field. The PIP is also connected to the search for approximate short vectors, known as the $\\gamma$-Shortest Vector Problem ($\\gamma$-SVP), in certain structured lattices called ideal lattices, which are prevalent in cryptography. We present an algorithm for resolving the PIP that leverages the norm relation techniques of Biasse, Fieker, Hofmann, and Page to efficiently reduce the PIP in a non-cyclic number field to instances of the PIP in subfields. Our algorithm is focused on practical performance and we demonstrate its viability by resolving instances of the PIP in cyclotomic fields of degree up to 1800. We further adapt this technique to the problem of finding mildly short vectors, solutions to $\\gamma$-SVP for $\\gamma = 2^{\\tilde{O}(\\sqrt{n})}$, in an ideal lattice of a cyclotomic field. Cramer, Ducas, and Wesolowski show that the search for mildly short vectors in such a lattice reduces efficiently to the PIP on a quantum computer. We describe a classical variant of this reduction that applies to non-cyclic cyclotomic fields. We show that there are infinite families of cyclotomic fields where this approach achieves a superpolynomial improvement over the state of the art."]},{"key":"dc:title","label":"Title","values":["Recovering generators of principal ideals using subfield structure and applications to cryptography"]}]}],"canonical_facts":{"dc:contributor":["Jean-Francois Biasse, Ph.D.","Dmytro Savchuk, Ph.D.","Natasa Jonoska, Ph.D.","Giacomo Micheli, Ph.D.","Attila Yavuz, Ph.D."],"dc:creator":["Youmans, William"],"dc:date":["2023-03-31T07:00:00Z"],"dc:description":["The principal ideal problem (PIP) is the problem of determining if a given ideal of a number field is principal, and if so, of finding a generator.Algorithms for resolving the PIP can be efficiently adapted to solve many hard problems in algebraic number theory, such as the computation of the class group, unit group, or $S$-unit group of a number field. The PIP is also connected to the search for approximate short vectors, known as the $\\gamma$-Shortest Vector Problem ($\\gamma$-SVP), in certain structured lattices called ideal lattices, which are prevalent in cryptography. We present an algorithm for resolving the PIP that leverages the norm relation techniques of Biasse, Fieker, Hofmann, and Page to efficiently reduce the PIP in a non-cyclic number field to instances of the PIP in subfields. Our algorithm is focused on practical performance and we demonstrate its viability by resolving instances of the PIP in cyclotomic fields of degree up to 1800. We further adapt this technique to the problem of finding mildly short vectors, solutions to $\\gamma$-SVP for $\\gamma = 2^{\\tilde{O}(\\sqrt{n})}$, in an ideal lattice of a cyclotomic field. Cramer, Ducas, and Wesolowski show that the search for mildly short vectors in such a lattice reduces efficiently to the PIP on a quantum computer. We describe a classical variant of this reduction that applies to non-cyclic cyclotomic fields. We show that there are infinite families of cyclotomic fields where this approach achieves a superpolynomial improvement over the state of the art."],"dc:identifier":["https://digitalcommons.usf.edu/etd/10463"],"dc:subject":["Ideal Lattice","Cyclotomic Field","Approximate Short Vector Problem","Ideal Class Group","S-unit Group","Mathematics"],"dc:title":["Recovering generators of principal ideals using subfield structure and applications to cryptography"],"thesis:degree_discipline":["Mathematics and Statistics"],"thesis:degree_level":["Dissertation","Ph.D."],"thesis:degree_name":["Doctor of Philosophy (Ph.D.)"],"thesis:institution_name":["University of South Florida"]},"updated_at":"2026-11-19T08:50:23Z"}