Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Using partial smoothness of $ p-1$ for factoring polynomials modulo $ p$

Author: Bartosz Zrałek
Journal: Math. Comp. 79 (2010), 2353-2359
MSC (2010): Primary 11Y16; Secondary 11Y05
Published electronically: May 20, 2010
MathSciNet review: 2684368
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let an arbitrarily small positive constant $ \delta$ less than $ 1$ and a polynomial $ f$ with integer coefficients be fixed. We prove unconditionally that $ f$ modulo $ p$ can be completely factored in deterministic polynomial time if $ p-1$ has a $ (\ln p)^{O(1)}$-smooth divisor exceeding $ p^\delta$. We also address the issue of factoring $ f$ modulo $ p$ over finite extensions of the prime field $ \mathbb{F}_p$ and show that $ p-1$ can be replaced by $ p^k-1$ ( $ k\in\mathbb{N}$) for explicit classes of primes $ p$.

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

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y16, 11Y05

Retrieve articles in all journals with MSC (2010): 11Y16, 11Y05

Additional Information

Bartosz Zrałek
Affiliation: Institute of Mathematics, Warsaw University, 02-097 Warsaw, Poland

Keywords: Prime finite fields, factorization, polynomials, roots, derandomization
Received by editor(s): March 17, 2008
Received by editor(s) in revised form: July 2, 2009
Published electronically: May 20, 2010
Article copyright: © Copyright 2010 American Mathematical Society

American Mathematical Society