Counting Roots of Polynomials over $\mathbb{Z}/p^2\mathbb{Z}$ Article Swipe
Trajan Hammonds
,
Jeremy Johnson
,
Angela Patini
,
Robert M. Walker
·
YOU?
·
· 2017
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.1708.04713
YOU?
·
· 2017
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.1708.04713
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 $p \in \mathbb{Z}$ and $f \in ( \mathbb{Z}/p^n \mathbb{Z} ) [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 $\mathbb{Z}/p^2\mathbb{Z}$ within time polynomial in $(d+\operatorname{size}(f)+\log{p})$, and record a concise formula for the number of roots, formulated by Cheng, Gao, Rojas, and Wan.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/1708.04713
- https://arxiv.org/pdf/1708.04713
- OA Status
- green
- References
- 5
- Related Works
- 20
- OpenAlex ID
- https://openalex.org/W2748330348
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W2748330348Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.1708.04713Digital Object Identifier
- Title
-
Counting Roots of Polynomials over $\mathbb{Z}/p^2\mathbb{Z}$Work title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2017Year of publication
- Publication date
-
2017-08-15Full publication date if available
- Authors
-
Trajan Hammonds, Jeremy Johnson, Angela Patini, Robert M. WalkerList of authors in order
- Landing page
-
https://arxiv.org/abs/1708.04713Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/1708.04713Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/1708.04713Direct OA link when available
- Concepts
-
Degree (music), Combinatorics, Mathematics, Polynomial, Prime (order theory), Prime power, Discrete mathematics, Physics, Mathematical analysis, AcousticsTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- References (count)
-
5Number of works referenced by this work
- Related works (count)
-
20Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W2748330348 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.1708.04713 |
| ids.doi | https://doi.org/10.48550/arxiv.1708.04713 |
| ids.mag | 2748330348 |
| ids.openalex | https://openalex.org/W2748330348 |
| fwci | 0.0 |
| type | preprint |
| title | Counting Roots of Polynomials over $\mathbb{Z}/p^2\mathbb{Z}$ |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T11693 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9990000128746033 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1710 |
| topics[0].subfield.display_name | Information Systems |
| topics[0].display_name | Cryptography and Residue Arithmetic |
| topics[1].id | https://openalex.org/T11130 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9984999895095825 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1702 |
| topics[1].subfield.display_name | Artificial Intelligence |
| topics[1].display_name | Coding theory and cryptography |
| topics[2].id | https://openalex.org/T10061 |
| topics[2].field.id | https://openalex.org/fields/26 |
| topics[2].field.display_name | Mathematics |
| topics[2].score | 0.998199999332428 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/2608 |
| topics[2].subfield.display_name | Geometry and Topology |
| topics[2].display_name | Algebraic Geometry and Number Theory |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C2775997480 |
| concepts[0].level | 2 |
| concepts[0].score | 0.7290608882904053 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q586277 |
| concepts[0].display_name | Degree (music) |
| concepts[1].id | https://openalex.org/C114614502 |
| concepts[1].level | 1 |
| concepts[1].score | 0.6997629404067993 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[1].display_name | Combinatorics |
| concepts[2].id | https://openalex.org/C33923547 |
| concepts[2].level | 0 |
| concepts[2].score | 0.6913185119628906 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[2].display_name | Mathematics |
| concepts[3].id | https://openalex.org/C90119067 |
| concepts[3].level | 2 |
| concepts[3].score | 0.6286997199058533 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q43260 |
| concepts[3].display_name | Polynomial |
| concepts[4].id | https://openalex.org/C184992742 |
| concepts[4].level | 2 |
| concepts[4].score | 0.6271311044692993 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q7243229 |
| concepts[4].display_name | Prime (order theory) |
| concepts[5].id | https://openalex.org/C174072685 |
| concepts[5].level | 3 |
| concepts[5].score | 0.45593494176864624 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q1667469 |
| concepts[5].display_name | Prime power |
| concepts[6].id | https://openalex.org/C118615104 |
| concepts[6].level | 1 |
| concepts[6].score | 0.3373563885688782 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q121416 |
| concepts[6].display_name | Discrete mathematics |
| concepts[7].id | https://openalex.org/C121332964 |
| concepts[7].level | 0 |
| concepts[7].score | 0.21182477474212646 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q413 |
| concepts[7].display_name | Physics |
| concepts[8].id | https://openalex.org/C134306372 |
| concepts[8].level | 1 |
| concepts[8].score | 0.09907171130180359 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q7754 |
| concepts[8].display_name | Mathematical analysis |
| concepts[9].id | https://openalex.org/C24890656 |
| concepts[9].level | 1 |
| concepts[9].score | 0.0 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q82811 |
| concepts[9].display_name | Acoustics |
| keywords[0].id | https://openalex.org/keywords/degree |
| keywords[0].score | 0.7290608882904053 |
| keywords[0].display_name | Degree (music) |
| keywords[1].id | https://openalex.org/keywords/combinatorics |
| keywords[1].score | 0.6997629404067993 |
| keywords[1].display_name | Combinatorics |
| keywords[2].id | https://openalex.org/keywords/mathematics |
| keywords[2].score | 0.6913185119628906 |
| keywords[2].display_name | Mathematics |
| keywords[3].id | https://openalex.org/keywords/polynomial |
| keywords[3].score | 0.6286997199058533 |
| keywords[3].display_name | Polynomial |
| keywords[4].id | https://openalex.org/keywords/prime |
| keywords[4].score | 0.6271311044692993 |
| keywords[4].display_name | Prime (order theory) |
| keywords[5].id | https://openalex.org/keywords/prime-power |
| keywords[5].score | 0.45593494176864624 |
| keywords[5].display_name | Prime power |
| keywords[6].id | https://openalex.org/keywords/discrete-mathematics |
| keywords[6].score | 0.3373563885688782 |
| keywords[6].display_name | Discrete mathematics |
| keywords[7].id | https://openalex.org/keywords/physics |
| keywords[7].score | 0.21182477474212646 |
| keywords[7].display_name | Physics |
| keywords[8].id | https://openalex.org/keywords/mathematical-analysis |
| keywords[8].score | 0.09907171130180359 |
| keywords[8].display_name | Mathematical analysis |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:1708.04713 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/1708.04713 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/1708.04713 |
| locations[1].id | mag:2748330348 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | |
| locations[1].pdf_url | |
| locations[1].version | submittedVersion |
| locations[1].raw_type | |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | False |
| locations[1].raw_source_name | arXiv (Cornell University) |
| locations[1].landing_page_url | https://arxiv.org/pdf/1708.04713.pdf |
| locations[2].id | doi:10.48550/arxiv.1708.04713 |
| locations[2].is_oa | True |
| locations[2].source.id | https://openalex.org/S4306400194 |
| locations[2].source.issn | |
| locations[2].source.type | repository |
| locations[2].source.is_oa | True |
| locations[2].source.issn_l | |
| locations[2].source.is_core | False |
| locations[2].source.is_in_doaj | False |
| locations[2].source.display_name | arXiv (Cornell University) |
| locations[2].source.host_organization | https://openalex.org/I205783295 |
| locations[2].source.host_organization_name | Cornell University |
| locations[2].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[2].license | |
| locations[2].pdf_url | |
| locations[2].version | |
| locations[2].raw_type | article-journal |
| locations[2].license_id | |
| locations[2].is_accepted | False |
| locations[2].is_published | |
| locations[2].raw_source_name | |
| locations[2].landing_page_url | https://doi.org/10.48550/arxiv.1708.04713 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5040112976 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-8045-2191 |
| authorships[0].author.display_name | Trajan Hammonds |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Trajan Hammonds |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5068650358 |
| authorships[1].author.orcid | https://orcid.org/0000-0001-8333-5532 |
| authorships[1].author.display_name | Jeremy Johnson |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Jeremy Johnson |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5076922862 |
| authorships[2].author.orcid | |
| authorships[2].author.display_name | Angela Patini |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Angela Patini |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5102842106 |
| authorships[3].author.orcid | https://orcid.org/0000-0002-8517-8603 |
| authorships[3].author.display_name | Robert M. Walker |
| authorships[3].author_position | last |
| authorships[3].raw_author_name | Robert M. Walker |
| authorships[3].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/1708.04713 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Counting Roots of Polynomials over $\mathbb{Z}/p^2\mathbb{Z}$ |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T11693 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9990000128746033 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1710 |
| primary_topic.subfield.display_name | Information Systems |
| primary_topic.display_name | Cryptography and Residue Arithmetic |
| related_works | https://openalex.org/W3122414537, https://openalex.org/W3127594214, https://openalex.org/W2964084511, https://openalex.org/W2788534203, https://openalex.org/W2997192637, https://openalex.org/W3109176755, https://openalex.org/W2946452484, https://openalex.org/W3206784337, https://openalex.org/W2626280074, https://openalex.org/W2774752345, https://openalex.org/W1890483258, https://openalex.org/W2148349712, https://openalex.org/W2101466178, https://openalex.org/W3036359728, https://openalex.org/W2949469131, https://openalex.org/W2008307482, https://openalex.org/W2964114665, https://openalex.org/W2962870773, https://openalex.org/W2330523511, https://openalex.org/W2287334124 |
| cited_by_count | 0 |
| locations_count | 3 |
| best_oa_location.id | pmh:oai:arXiv.org:1708.04713 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/1708.04713 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/1708.04713 |
| primary_location.id | pmh:oai:arXiv.org:1708.04713 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/1708.04713 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/1708.04713 |
| publication_date | 2017-08-15 |
| publication_year | 2017 |
| referenced_works | https://openalex.org/W79040398, https://openalex.org/W1968936725, https://openalex.org/W3004208859, https://openalex.org/W3175367423, https://openalex.org/W2612606421 |
| referenced_works_count | 5 |
| abstract_inverted_index.( | 49 |
| abstract_inverted_index.) | 52 |
| abstract_inverted_index.a | 30, 41, 74, 93 |
| abstract_inverted_index.$f | 47 |
| abstract_inverted_index.$p | 43 |
| abstract_inverted_index.by | 66, 102 |
| abstract_inverted_index.in | 84, 89 |
| abstract_inverted_index.is | 26 |
| abstract_inverted_index.of | 6, 10, 29, 36, 57, 82, 99 |
| abstract_inverted_index.to | 78 |
| abstract_inverted_index.we | 72 |
| abstract_inverted_index.$d$ | 59 |
| abstract_inverted_index.$f$ | 83 |
| abstract_inverted_index.Fix | 40 |
| abstract_inverted_index.For | 68 |
| abstract_inverted_index.One | 22 |
| abstract_inverted_index.\in | 44, 48 |
| abstract_inverted_index.all | 64 |
| abstract_inverted_index.and | 46, 91, 106 |
| abstract_inverted_index.any | 54 |
| abstract_inverted_index.are | 62 |
| abstract_inverted_index.for | 24, 96 |
| abstract_inverted_index.new | 75 |
| abstract_inverted_index.not | 63 |
| abstract_inverted_index.the | 2, 8, 27, 34, 69, 80, 97 |
| abstract_inverted_index.use | 35 |
| abstract_inverted_index.was | 19 |
| abstract_inverted_index.$p$. | 67 |
| abstract_inverted_index.Gao, | 104 |
| abstract_inverted_index.Wan. | 107 |
| abstract_inverted_index.[x]$ | 53 |
| abstract_inverted_index.case | 70 |
| abstract_inverted_index.lack | 28 |
| abstract_inverted_index.only | 3 |
| abstract_inverted_index.over | 12 |
| abstract_inverted_index.than | 17 |
| abstract_inverted_index.this | 25 |
| abstract_inverted_index.time | 87 |
| abstract_inverted_index.Until | 0 |
| abstract_inverted_index.brute | 20 |
| abstract_inverted_index.count | 79 |
| abstract_inverted_index.known | 4 |
| abstract_inverted_index.other | 16 |
| abstract_inverted_index.power | 14 |
| abstract_inverted_index.prime | 13, 42 |
| abstract_inverted_index.prove | 73 |
| abstract_inverted_index.roots | 9, 81 |
| abstract_inverted_index.whose | 60 |
| abstract_inverted_index.$n=2$, | 71 |
| abstract_inverted_index.Cheng, | 103 |
| abstract_inverted_index.Rojas, | 105 |
| abstract_inverted_index.common | 38 |
| abstract_inverted_index.degree | 58 |
| abstract_inverted_index.force. | 21 |
| abstract_inverted_index.method | 5 |
| abstract_inverted_index.number | 98 |
| abstract_inverted_index.reason | 23 |
| abstract_inverted_index.record | 92 |
| abstract_inverted_index.rings, | 15 |
| abstract_inverted_index.roots, | 100 |
| abstract_inverted_index.within | 86 |
| abstract_inverted_index.concise | 94 |
| abstract_inverted_index.fields, | 18 |
| abstract_inverted_index.finding | 7 |
| abstract_inverted_index.formula | 95 |
| abstract_inverted_index.nonzero | 55 |
| abstract_inverted_index.division | 31 |
| abstract_inverted_index.greatest | 37 |
| abstract_inverted_index.algorithm | 77 |
| abstract_inverted_index.divisible | 65 |
| abstract_inverted_index.divisors. | 39 |
| abstract_inverted_index.efficient | 76 |
| abstract_inverted_index.recently, | 1 |
| abstract_inverted_index.\mathbb{Z} | 51 |
| abstract_inverted_index.algorithm, | 32 |
| abstract_inverted_index.formulated | 101 |
| abstract_inverted_index.polynomial | 56, 88 |
| abstract_inverted_index.\mathbb{Z}$ | 45 |
| abstract_inverted_index.obstructing | 33 |
| abstract_inverted_index.polynomials | 11 |
| abstract_inverted_index.coefficients | 61 |
| abstract_inverted_index.\mathbb{Z}/p^n | 50 |
| abstract_inverted_index.$\mathbb{Z}/p^2\mathbb{Z}$ | 85 |
| abstract_inverted_index.$(d+\operatorname{size}(f)+\log{p})$, | 90 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 4 |
| citation_normalized_percentile.value | 0.14736594 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |