[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/22145.22159acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
Article
Free access

Riemann hypothesis and finding roots over finite fields

Published: 01 December 1985 Publication History

Abstract

It is shown that assuming Generalized Riemann Hypothesis, the roots of ƒ(x) = O mod p, where p is a prime and f(x) is an integral Abilene polynomial can be found in deterministic polynomial time. The method developed for solving this problem is also applied to prime decomposition in Abelian number fields, and the following result is obtained: assuming Generalized Riemann Hypotheses, for Abelian number fields K of finite extension degree over the rational number field Q, the decomposition pattern of a prime p in K, i.e. the ramification index and the residue class degree, can be computed in deterministic polynomial time, providing p does not divide the extension degree of K over Q. It is also shown, as a theorem fundamental to our algorithm, that for q, p prime and m the order of p mod q, there is a q-th nonresidue in the finite field Fpm that can be written as ao + a1w + … + am-1wm-1, where |a1| ≤ cq2 log2(pq), c is an absolute effectively computable constant, and 1, w, …, wm-1 form a basis of Fpm over Fp. More explicitly, w is a root of the q-th cyclotomic polynomial over Fp. This result partially generalizes, to finite field extensions over Fp, a classical result in number theory stating that assuming Generalized Riemann Hypothesis, the least q-th nonresidue mod p for p,q prime and q dividing p - t is bounded by c log2p, where c is an absolute, effectively computable constant.

References

[1]
L.M. Adleman, K. Mander, and G. Miller: "On Taking Roots in Finite Fields", Proc. 18th IEEE Syrup. Foundations of Computer Sciences, (1977), pp. 175-178.
[2]
L.M. Adleman, C. Pomerance, and R. S. Rumely, "On Distinguishing Prime Numbers form Composite Numbers'', Annals o/Math., 117, (1953), pp. 173-206.
[3]
N.C. Ankeny, "The Least Quadratic Non Residue", Annals of Math., 55, (1952), pp. 65-72.
[4]
E. Artin and J. Tare, Class Field Theory, W.A. Benjamine (New York), 1967.
[5]
E. Bach: "Fast Algorithms under the Extended Riemann Hypothesis: A Concrete Estimate", Proc. 14th ACM S)'mp. on Theory of Computing, (1982), pp. 290-195.
[6]
E.R. Berlekamp, "Factoring Polynomials over Large Finite Fields", Math. Computing, 24 (1970), pp. 713-735.
[7]
J.W.S. Cassels and A. Frohlich, Algebraic Number Ttteor), Thompson (Washington, D.C.), 1967.
[8]
H, Davenport and D. }. lewis, "Character Sums and Primitive Roots in Finite Fi~.'lds*', Rend. Circolo Math. di Palermo, 12, (1963), pp. 129-136.
[9]
M.A. Huang, "Factorizatioa of Polynomials over Finite Fields and Factorization of Primes in Algebraic Number Fields", Proc. 16th,4CM $)'mp. on Theory of Computing, (1984), pp. 175-.182.
[10]
K. Iwasawa, "A Note on ja,:obi Sunrs". Symposia Math., 15, (1975), pp. 447-459.
[11]
S. Lang, Algebraic Number Theory, Addison-Wesley (Reading, Mass), 1970.
[12]
A.K. Lenstra, H.W. Lenstra, Jr., and L. Lovasz, "Factoring PolynomiaLs with Rational Coeeficiants", Math. Annal., 261, (1982), pp. 515-535.
[13]
J.C. Lagarias, H.L. Montgomery, and A.M. Odlyzko, "A Bound for the Least Prime !deal in the Chebotarev Density Theorem", ln~entions Math, 54, (1979), pp, 271-296.
[14]
J.C. Lagarias and A.M. Odlyzko, "Effective Versions of the Cheboterev Density Theorem", Algebraic Number Fields, Academic Press, 1977, 409-463.
[15]
M.O. Rabin, "Probabilistic Algorithnts in Finite Fields", SIAM J. Computing, Vol. 9, No. 2, (1980), pp. 273-280.

Cited By

View all
  • (2017)Irreducibility and Deterministic r-th Root Finding over Finite FieldsProceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3087604.3087620(37-44)Online publication date: 23-Jul-2017
  • (2015)On Solving Systems of Diagonal Polynomial Equations Over Finite FieldsFrontiers in Algorithmics10.1007/978-3-319-19647-3_12(125-137)Online publication date: 27-Jun-2015
  • (2013)CryptographyHandbook of Finite Fields10.1201/b15006-22(777-860)Online publication date: 17-Jun-2013
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computing
December 1985
484 pages
ISBN:0897911512
DOI:10.1145/22145
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: 01 December 1985

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

STOC85
Sponsor:
STOC85: Annual ACM Conference on Theory of Computing
May 6 - 8, 1985
Rhode Island, Providence, USA

Acceptance Rates

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

Upcoming Conference

STOC '25
57th Annual ACM Symposium on Theory of Computing (STOC 2025)
June 23 - 27, 2025
Prague , Czech Republic

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)52
  • Downloads (Last 6 weeks)5
Reflects downloads up to 31 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2017)Irreducibility and Deterministic r-th Root Finding over Finite FieldsProceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3087604.3087620(37-44)Online publication date: 23-Jul-2017
  • (2015)On Solving Systems of Diagonal Polynomial Equations Over Finite FieldsFrontiers in Algorithmics10.1007/978-3-319-19647-3_12(125-137)Online publication date: 27-Jun-2015
  • (2013)CryptographyHandbook of Finite Fields10.1201/b15006-22(777-860)Online publication date: 17-Jun-2013
  • (2010)Elliptic Gauss sums and applications to point countingJournal of Symbolic Computation10.1016/j.jsc.2010.01.00445:8(825-836)Online publication date: 1-Aug-2010
  • (2009)Permutation group approach to association schemesEuropean Journal of Combinatorics10.1016/j.ejc.2008.11.00530:6(1456-1476)Online publication date: 1-Aug-2009
  • (2005)Factorization of polynomials over finite fields in subexponential time under GRHAlgorithmic Number Theory10.1007/3-540-58691-1_58(209-219)Online publication date: 4-Jun-2005
  • (2005)A primality test using cyclotomic extensionsApplied Algebra, Algebraic Algorithms and Error-Correcting Codes10.1007/3-540-51083-4_68(310-323)Online publication date: 1-Jun-2005
  • (2005)Irreducible polynomials over finite fieldsFoundations of Software Technology and Theoretical Computer Science10.1007/3-540-17179-7_15(252-262)Online publication date: 28-May-2005
  • (2002)Models of Computation, Riemann Hypothesis, and Classical MathematicsSOFSEM’ 98: Theory and Practice of Informatics10.1007/3-540-49477-4_6(89-106)Online publication date: 24-Sep-2002
  • (2001)Solvability by radicals from an algorithmic point of viewProceedings of the 2001 international symposium on Symbolic and algebraic computation10.1145/384101.384125(175-182)Online publication date: 1-Jul-2001
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media