Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
-
Until recently, the only known method of finding the roots of polynomials over prime power rings, other than fields, was brute force. One reason for this is the lack of a division algorithm, obstructing the use of greatest common divisors. Fix a prime integer p and f in (Z/pnZ)[x] any nonzero polynomial of degree d whose coefficients are not all divisible by p. For the case n=2, we prove a new efficient algorithm to count the roots of f in Z/p2Z within time (d+size(f)+log p),2+o(1), based on a formula conjectured by Cheng, Gao, Rojas, and Wan.more » « less
Full Text Available