Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Solvability of norm equations over cyclic number fields of prime degree

Author: Vincenzo Acciaro
Journal: Math. Comp. 65 (1996), 1663-1674
MSC (1991): Primary 11R37; Secondary 11Y40
MathSciNet review: 1351200
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let $L={\mathbb {Q}} [\alpha ]$ be an abelian number field of prime degree $q$, and let $a$ be a nonzero rational number. We describe an algorithm which takes as input $a$ and the minimal polynomial of $\alpha $ over ${\mathbb {Q}}$, and determines if $a$ is a norm of an element of $L$. We show that, if we ignore the time needed to obtain a complete factorization of $a$ and a complete factorization of the discriminant of $\alpha $, then the algorithm runs in time polynomial in the size of the input. As an application, we give an algorithm to test if a cyclic algebra $A=( E, \sigma , a )$ over ${\mathbb {Q}}$ is a division algebra.

References [Enhancements On Off] (What's this?)

  • 1. A.A. Albert, Structure of algebras, A.M.S. Colloquium Publications 24, 1961. MR 23:A912
  • 2. H. Cohen, A course in computational algebraic number theory, Springer-Verlag, Berlin, 1993. MR 94i:11105
  • 3. D.A. Cox, Primes of the form $x^2+ny^2$, John Wiley and Sons, New York, 1989. MR 90m:11016
  • 4. G. Ivanyos and L. Rónyai, Finding maximal orders in semisimple algebras over ${\mathbb {Q}} $, Comput. Complexity 3 (1993), 245--261. MR 95c:11154
  • 5. G.J. Janusz, Algebraic number fields, Academic Press, London, 1973. MR 51:3110
  • 6. N. Koblitz, $p$-adic Numbers, $p$-adic Analysis and Zeta Functions, Springer-Verlag, New York, 1984. MR 86c:11086
  • 7. S. Lang, Algebraic number theory, Addison-Wesley, Reading, Massachusetts, 1970. MR 44:181
  • 8. H.W. Lenstra, Jr., Algorithms in algebraic number theory, Bull. Amer. Math. Soc. 26 (1992), 211-244. MR 93g:11131
  • 9. K. Mahler, An inequality for the discriminant of a polynomial, Michigan Math. J. 11 (1964), 257-262. MR 29:3465
  • 10. I. Niven and H.S. Zuckerman, An Introduction to the Theory of Numbers, John Wiley and Sons, New York, 1980. MR 81g:10001
  • 11. R.S. Pierce, Associative Algebras, Springer-Verlag, Berlin, 1982. MR 84c:16001
  • 12. M.E. Pohst and H. Zassenhaus, Algorithmic algebraic number theory, Cambridge Univ. Press, Cambridge, 1989. MR 92b:11074
  • 13. L. Rónyai, Algorithmic properties of maximal orders in simple algebras over ${\mathbb {Q}} $, Comput. Complexity 2 (1992), 225--243. MR 94e:11143
  • 14. B.M. Urazbaev, On the discriminant of a cyclic field of prime degree, Izvestiya Akad. Nauk Kazah. SSR 97 (1950), Ser. Math. Meh. 4 (1950), 19-32. MR 15:403c
  • 15. B.L. van der Waerden, Algebra, Volume 1, Springer-Verlag, Berlin, 1991. MR 91h:00009a

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11R37, 11Y40

Retrieve articles in all journals with MSC (1991): 11R37, 11Y40

Additional Information

Vincenzo Acciaro
Affiliation: School of Computer Science, Carleton University, Ottawa, Ontario, K1S 5B6, Canada

Received by editor(s): March 30, 1995
Received by editor(s) in revised form: July 14, 1995
Article copyright: © Copyright 1996 American Mathematical Society

American Mathematical Society