Detecting squarefree numbers
We present an algorithm, based on the explicit formula for L-functions and conditional on the generalized Riemann hypothesis, for proving that a given integer is squarefree with little or no knowledge of its factorization. We analyze the algorithm both theoretically and practically and use it to pro...
| Huvudupphovsmän: | , , |
|---|---|
| Materialtyp: | Journal article |
| Publicerad: |
Duke University Press
2015
|
| _version_ | 1826288462856192000 |
|---|---|
| author | Booker, A Hiary, G Keating, J |
| author_facet | Booker, A Hiary, G Keating, J |
| author_sort | Booker, A |
| collection | OXFORD |
| description | We present an algorithm, based on the explicit formula for L-functions and conditional on the generalized Riemann hypothesis, for proving that a given integer is squarefree with little or no knowledge of its factorization. We analyze the algorithm both theoretically and practically and use it to prove that several RSA challenge numbers are not squarefull. |
| first_indexed | 2024-03-07T02:14:04Z |
| format | Journal article |
| id | oxford-uuid:a19fd25e-363c-4967-9fee-dbc475779897 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T02:14:04Z |
| publishDate | 2015 |
| publisher | Duke University Press |
| record_format | dspace |
| spelling | oxford-uuid:a19fd25e-363c-4967-9fee-dbc4757798972022-03-27T02:14:36ZDetecting squarefree numbersJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:a19fd25e-363c-4967-9fee-dbc475779897Symplectic Elements at OxfordDuke University Press2015Booker, AHiary, GKeating, JWe present an algorithm, based on the explicit formula for L-functions and conditional on the generalized Riemann hypothesis, for proving that a given integer is squarefree with little or no knowledge of its factorization. We analyze the algorithm both theoretically and practically and use it to prove that several RSA challenge numbers are not squarefull. |
| spellingShingle | Booker, A Hiary, G Keating, J Detecting squarefree numbers |
| title | Detecting squarefree numbers |
| title_full | Detecting squarefree numbers |
| title_fullStr | Detecting squarefree numbers |
| title_full_unstemmed | Detecting squarefree numbers |
| title_short | Detecting squarefree numbers |
| title_sort | detecting squarefree numbers |
| work_keys_str_mv | AT bookera detectingsquarefreenumbers AT hiaryg detectingsquarefreenumbers AT keatingj detectingsquarefreenumbers |