{
  "id": "1801.01055",
  "version": "v1",
  "published": "2018-01-03T15:42:54.000Z",
  "updated": "2018-01-03T15:42:54.000Z",
  "title": "Gaps between prime numbers and tensor rank of multiplication in finite fields",
  "authors": [
    "Hugues Randriam"
  ],
  "comment": "20 pages, submitted to special issue of Designs, Codes and Cryptography",
  "categories": [
    "math.NT",
    "cs.CC"
  ],
  "abstract": "We present effective upper bounds on the symmetric bilinear complexity of multiplication in extensions of a base finite field Fp2 of prime square order, obtained by combining estimates on gaps between prime numbers together with an optimal construction of auxiliary divisors for multiplication algorithms by evaluation-interpolation on curves. Most of this material dates back to a 2011 unpublished work of the author, but it still provides the best results on this topic at the present time. Then a few updates are given in order to take recent developments into account, including comparison with a similar work of Ballet and Zykin, generalization to classical bilinear complexity over Fp, and to short multiplication of polynomials, as well as a discussion of open questions on gaps between prime numbers or more generally values of certain arithmetic functions.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-01-03T15:42:54.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "12Y05",
      "11A41",
      "11T71",
      "14Q05"
    ],
    "keywords": [
      "prime numbers",
      "tensor rank",
      "multiplication",
      "base finite field fp2",
      "symmetric bilinear complexity"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}