{"id":{"repo_id":"vt","oai_identifier":"oai:vtechworks.lib.vt.edu:10919/103821"},"canonical_url":"https://search.dev.ndltd.org/etd/vt/oai:vtechworks.lib.vt.edu:10919/103821","repository":{"repo_id":"vt","name":"Virginia Tech","base_url":"https://vtechworks.lib.vt.edu/oai/request"},"display":{"title":"Computing the trace of an endomorphism of a supersingular elliptic curve","abstract":"We provide an explicit algorithm for computing the trace of an endomorphism of an elliptic curve which is given by a chain of small-degree isogenies. We analyze its complexity, determining that if the length of the chain, the degree of the isogenies, and the log of the field-size are all O(n), the trace of the endomorphism can be computed in O(n⁶) bit operations. This makes explicit a theorem of Kohel which states that such a polynomial time algorithm exists. The given procedure is based on Schoof's point-counting algorithm.","abstract_html":"We provide an explicit algorithm for computing the trace of an endomorphism of an elliptic curve which is given by a chain of small-degree isogenies. We analyze its complexity, determining that if the length of the chain, the degree of the isogenies, and the log of the field-size are all O(n), the trace of the endomorphism can be computed in O(n⁶) bit operations. This makes explicit a theorem of Kohel which states that such a polynomial time algorithm exists. The given procedure is based on Schoof's point-counting algorithm.","abstract_has_math":false,"creators":["Wills, Michael Thomas"],"institution":"Virginia Tech","degree_name":"Master of Science","degree_level":"masters","degree_discipline":"Mathematics","degree_department":"Mathematics","school":null,"contributors":[],"advisors":[],"committee_chairs":["Matthews, Gretchen L.","Morrison, Travis William"],"committee_members":["Shimozono, Mark M.","Orr, Daniel D."],"year":2021,"date_issued":"2021-06-10","date_published":"2021-06-10","updated_at":"2026-07-22T22:19:47Z","subjects":["elliptic curves","endomorphism rings","arithmetic geometry","supersingular elliptic curves"],"languages":[],"rights":["In Copyright"],"rights_urls":["http://rightsstatements.org/vocab/InC/1.0/"],"identifier_entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["vt_gsexam:31073"],"render_values":[{"text":"vt_gsexam:31073","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/10919/103821","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.committeechair","label":"Committee Chair","values":["Matthews, Gretchen L.","Morrison, Travis William"]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Shimozono, Mark M.","Orr, Daniel D."]},{"key":"dc:contributor.department","label":"Department","values":["Mathematics"]},{"key":"dc:creator","label":"Author","values":["Wills, Michael Thomas"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2021-06-12T08:01:15Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2021-06-12T08:01:15Z"]},{"key":"dc:date.issued","label":"Date","values":["2021-06-10"]},{"key":"dc:publisher","label":"Institution","values":["Virginia Tech"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Virginia Polytechnic Institute and State University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["elliptic curves","endomorphism rings","arithmetic geometry","supersingular elliptic curves"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["In Copyright"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://rightsstatements.org/vocab/InC/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["vt_gsexam:31073"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/10919/103821"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["We provide an explicit algorithm for computing the trace of an endomorphism of an elliptic curve which is given by a chain of small-degree isogenies. We analyze its complexity, determining that if the length of the chain, the degree of the isogenies, and the log of the field-size are all O(n), the trace of the endomorphism can be computed in O(n⁶) bit operations. This makes explicit a theorem of Kohel which states that such a polynomial time algorithm exists. The given procedure is based on Schoof's point-counting algorithm."]},{"key":"dc:description.abstractgeneral","label":"General Abstract","values":["The developing technology of quantum computers threatens to render current cryptographic systems (that is, systems for protecting stored or transmitted digital information from unauthorized third parties) ineffective. Among the systems proposed to ensure information security against attacks by quantum computers is a cryptographic scheme known as SIKE. In this thesis, we provide and analyze an algorithm that comprises one piece of a potential attack against SIKE by a classical computer. The given algorithm is also useful more generally in the field of arithmetic geometry."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Master of Science"]},{"key":"dc:format.medium","label":"Dc Format Medium","values":["ETD"]},{"key":"dc:title","label":"Title","values":["Computing the trace of an endomorphism of a supersingular elliptic curve"]}]}],"canonical_facts":{"dc:contributor.committeechair":["Matthews, Gretchen L.","Morrison, Travis William"],"dc:contributor.committeemember":["Shimozono, Mark M.","Orr, Daniel D."],"dc:contributor.department":["Mathematics"],"dc:creator":["Wills, Michael Thomas"],"dc:date.accessioned":["2021-06-12T08:01:15Z"],"dc:date.available":["2021-06-12T08:01:15Z"],"dc:date.issued":["2021-06-10"],"dc:description.abstract":["We provide an explicit algorithm for computing the trace of an endomorphism of an elliptic curve which is given by a chain of small-degree isogenies. We analyze its complexity, determining that if the length of the chain, the degree of the isogenies, and the log of the field-size are all O(n), the trace of the endomorphism can be computed in O(n⁶) bit operations. This makes explicit a theorem of Kohel which states that such a polynomial time algorithm exists. The given procedure is based on Schoof's point-counting algorithm."],"dc:description.abstractgeneral":["The developing technology of quantum computers threatens to render current cryptographic systems (that is, systems for protecting stored or transmitted digital information from unauthorized third parties) ineffective. Among the systems proposed to ensure information security against attacks by quantum computers is a cryptographic scheme known as SIKE. In this thesis, we provide and analyze an algorithm that comprises one piece of a potential attack against SIKE by a classical computer. The given algorithm is also useful more generally in the field of arithmetic geometry."],"dc:description.degree":["Master of Science"],"dc:format.medium":["ETD"],"dc:identifier.other":["vt_gsexam:31073"],"dc:identifier.uri":["http://hdl.handle.net/10919/103821"],"dc:publisher":["Virginia Tech"],"dc:rights":["In Copyright"],"dc:rights.uri":["http://rightsstatements.org/vocab/InC/1.0/"],"dc:subject":["elliptic curves","endomorphism rings","arithmetic geometry","supersingular elliptic curves"],"dc:title":["Computing the trace of an endomorphism of a supersingular elliptic curve"],"dc:type":["Thesis"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["masters"],"thesis:degree_name":["Master of Science"],"thesis:institution_name":["Virginia Polytechnic Institute and State University"]},"updated_at":"2026-07-22T22:19:47Z"}