{
  "id": "2305.17425",
  "version": "v1",
  "published": "2023-05-27T09:19:29.000Z",
  "updated": "2023-05-27T09:19:29.000Z",
  "title": "Computing $e$-th roots in number fields",
  "authors": [
    "Olivier Bernard",
    "Andrea Lesavourey",
    "Pierre-Alain Fouque"
  ],
  "comment": "9 pages, 4 figures. Associated experimental code provided at https://github.com/ob3rnard/eth-roots",
  "categories": [
    "math.NT"
  ],
  "abstract": "We describe several algorithms for computing $e$-th roots of elements in a number field $K$, where $e$ is an odd prime-power integer. In particular we generalize Couveignes' and Thom\\'e's algorithms originally designed to compute square-roots in the Number Field Sieve algorithm for integer factorization. Our algorithms cover most cases of $e$ and $K$ and allow to obtain reasonable timings even for large degree number fields and large exponents $e$. The complexity of our algorithms is better than general root finding algorithms and our implementation compared well in performance to these algorithms implemented in well-known computer algebra softwares. One important application of our algorithms is to compute the saturation phase in the Twisted-PHS algorithm for computing the Ideal-SVP problem over cyclotomic fields in post-quantum cryptography.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-05-27T09:19:29.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "11Y40",
      "11Y16",
      "11R18",
      "11R29"
    ],
    "keywords": [
      "th roots",
      "well-known computer algebra softwares",
      "large degree number fields",
      "number field sieve algorithm",
      "general root finding algorithms"
    ],
    "tags": [
      "github project"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 9,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}