Article

Polynomial time quantum algorithm for the computation of the unit group of a number field

Authors:

Arthur Schmidt,

Ulrich VollmerAuthors Info & Claims

STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing

Pages 475 - 480

https://doi.org/10.1145/1060590.1060661

Published: 22 May 2005 Publication History

Abstract

We present a quantum algorithm for the computation of the irrational period lattice of a function on Zⁿ which is periodic in a relaxed sense. This algorithm is applied to compute the unit group of finite extensions of Q. Execution time for fixed field degree over Q is polynomial in the discriminant of the field. Our algorithms generalize and improve upon Hallgren's work [9] for the one-dimensional case corresponding to real-quadratic fields.

References

[1]

W. Banaszczyk. New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen, 296:625--635, 1993.]]

[2]

D. Boneh and R. Lipton. Quantum cryptanalysis of hidden linear functions (extended abstract). In Don Coppersmith, editor, Advances in Cryptology - CRYPTO '95, volume 963 of Lecture Notes in Computer Science. Springer, 1995.]]

Digital Library

[3]

J. Buchmann. On the computation of units and class numbers by a generalization of Lagrange's algorithm. Journal of Number Theory, 26:8--30, 1987.]]

[4]

J. Buchmann. On the period length of the generalized Lagrange algorithm. Journal of Number Theory, 26:31--37, 1987.]]

[5]

Johannes Buchmann. Zur Komplexität der Berechnung von Einheiten und Klassenzahlen algebraischer Zahlkörper, 1987. Habilitationsschrift.]]

[6]

Johannes Buchmann. A subexponential algorithm for the determination of class groups and regulators of algebraic number fields. In Catherine Goldstein, editor, Séminaire de Théorie des Nombres, Paris 1988--1989, volume 91 of Progress in Mathematics, pages 27--41. Birkhäuser, 1990.]]

[7]

Johannes Buchmann, Max Jüntgen, and Michael Pohst. A practical version of the generalized lagrange algorithm. Exp. Math., (3):200--207, 1994.]]

[8]

Johannes Buchmann, Markus Maurer, and Bodo Möller. Cryptography based on number fields with large regulator. Technical Report TI-5/00, Technische Universität Darmstadt, Fachbereich Informatik, 2000. http://www.informatik.tu-darmstadt.de/TI/Veroeffentlichung/TR/.]]

[9]

Sean Hallgren. Polynomial-time quantum algorithms for pell's equation and the principal ideal problem. In Proceedings of the thiry-fourth annual ACM symposium on the theory of computing, pages 653--658. ACM Press, 2002.]]

Digital Library

[10]

Richard Jozsa. Quantum algorithms and the fourier transform. Proc Roy Soc Lond A, pages 323--337, 1998.]]

[11]

Alexei Kitaev. Quantum measurements and the abelian stabilizer problem. Electronic Colloquium on Computational Complexity (ECCC), 3(3), 1996.]]

[12]

Michele Mosca and Artur Ekert. The hidden subgroup problem and eigenvalue estimation on a quantum computer. Lecture Notes in Computer Science, 1509:174--188, 1999.]]

Digital Library

[13]

Peter W. Shor. Polynomial time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484--1509, 1997.]]

Digital Library

[14]

David R. Simon. On the power of quantum computation. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pages 116--123, Los Alamitos, CA, 1994. Institute of Electrical and Electronic Engineers Computer Society Press.]]

Digital Library

[15]

Christoph Thiel. On the complexity of some problems in algorithmic algebraic number theory. PhD thesis, Universität des Saarlandes, Saarbrücken, Germany, 1995.]]

Cited By

Cohen AD'Oliveira RYeh CGuerboukha HShrestha RFang ZW. Knightly EMédard MMittleman D(2023)Absolute Security in Terahertz Wireless LinksIEEE Journal of Selected Topics in Signal Processing10.1109/JSTSP.2023.330790617:4(819-833)Online publication date: Jul-2023
https://doi.org/10.1109/JSTSP.2023.3307906
Barbulescu RPoulalion A(2023)The Special Case of Cyclotomic Fields in Quantum Algorithms for Unit GroupsProgress in Cryptology - AFRICACRYPT 202310.1007/978-3-031-37679-5_10(229-251)Online publication date: 13-Jul-2023
https://doi.org/10.1007/978-3-031-37679-5_10
Cohen AD'Oliveira RYeh CGuerboukha HShrestha RFang ZKnightly EMedard MMittleman D(2022)Absolute Security in High-Frequency Wireless Links2022 IEEE Conference on Communications and Network Security (CNS)10.1109/CNS56114.2022.9947269(46-54)Online publication date: 3-Oct-2022
https://doi.org/10.1109/CNS56114.2022.9947269
Show More Cited By

Index Terms

Polynomial time quantum algorithm for the computation of the unit group of a number field
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Number-theoretic computations

Recommendations

A quantum algorithm for computing the unit group of an arbitrary degree number field
STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing

Computing the group of units in a field of algebraic numbers is one of the central tasks of computational algebraic number theory. It is believed to be hard classically, which is of interest for cryptography. In the quantum setting, efficient algorithms ...
Fast quantum algorithms for computing the unit group and class group of a number field
STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing

Computing the unit group and class group of a number field are two of the main tasks in computational algebraic number theory. Factoring integers reduces to solving Pell's equation, which is a special case of computing the unit group, but a reduction in ...
Deterministic polynomial-time quantum algorithms for Simon's problem

D. R. Simon stated a problem, so-called Simon's problem, whose computational complexity is in the class BQP^φ but not in BPP^φ, where φ is the function or oracle given in the problem. This result indicates that BPP may be strictly included in its quantum ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing

May 2005

778 pages

ISBN:1581139608

DOI:10.1145/1060590

General Chair:
Hal Gabow
University of Colorado
,
Program Chair:
Ronald Fagin
IBM Almaden Research Center

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 May 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

STOC05

Sponsor:

STOC05: Symposium on Theory of Computing

May 22 - 24, 2005

MD, Baltimore, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
491
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)2

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cohen AD'Oliveira RYeh CGuerboukha HShrestha RFang ZW. Knightly EMédard MMittleman D(2023)Absolute Security in Terahertz Wireless LinksIEEE Journal of Selected Topics in Signal Processing10.1109/JSTSP.2023.330790617:4(819-833)Online publication date: Jul-2023
https://doi.org/10.1109/JSTSP.2023.3307906
Barbulescu RPoulalion A(2023)The Special Case of Cyclotomic Fields in Quantum Algorithms for Unit GroupsProgress in Cryptology - AFRICACRYPT 202310.1007/978-3-031-37679-5_10(229-251)Online publication date: 13-Jul-2023
https://doi.org/10.1007/978-3-031-37679-5_10
Cohen AD'Oliveira RYeh CGuerboukha HShrestha RFang ZKnightly EMedard MMittleman D(2022)Absolute Security in High-Frequency Wireless Links2022 IEEE Conference on Communications and Network Security (CNS)10.1109/CNS56114.2022.9947269(46-54)Online publication date: 3-Oct-2022
https://doi.org/10.1109/CNS56114.2022.9947269
Biasse JBonnetain XKirshanova ESchrottenloher ASong F(2022)Quantum algorithms for attacking hardness assumptions in classical and post‐quantum cryptographyIET Information Security10.1049/ise2.1208117:2(171-209)Online publication date: 29-Aug-2022
https://dl.acm.org/doi/10.1049/ise2.12081
Ye ZLi L(2022)Sample complexity of hidden subgroup problemTheoretical Computer Science10.1016/j.tcs.2022.04.014922:C(108-121)Online publication date: 24-Jun-2022
https://dl.acm.org/doi/10.1016/j.tcs.2022.04.014
Ye ZLi L(2022)Deterministic algorithms for the hidden subgroup problemInformation and Computation10.1016/j.ic.2022.104975289:PAOnline publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1016/j.ic.2022.104975
Cohen AD'Oliveira RSalamatian SMedard M(2021)Network Coding-Based Post-Quantum CryptographyIEEE Journal on Selected Areas in Information Theory10.1109/JSAIT.2021.30545982:1(49-64)Online publication date: Mar-2021
https://doi.org/10.1109/JSAIT.2021.3054598
Bae ELee S(2021)Quantum Algorithm for Solving the Continuous Hidden Symmetry Subgroup ProblemIEEE Access10.1109/ACCESS.2021.30927239(93248-93254)Online publication date: 2021
https://doi.org/10.1109/ACCESS.2021.3092723
de Boer KDucas LFehr S(2020)On the Quantum Complexity of the Continuous Hidden Subgroup ProblemAdvances in Cryptology – EUROCRYPT 202010.1007/978-3-030-45724-2_12(341-370)Online publication date: 10-May-2020
https://dl.acm.org/doi/10.1007/978-3-030-45724-2_12
Chen FZhang LZhang H(2019)Controlled SWAP attack and improved quantum encryption of arbitrated quantum signature schemesQuantum Information Processing10.1007/s11128-019-2265-y18:5(1-18)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1007/s11128-019-2265-y
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents