Let $F$ be a large finite field, where the elements are strings of length $n$. We require, addition, multiplication, and division to be efficient (polynomial in $n$).

We say that $F$ is searchable if for any $u \in F$ and string $x$, we can find efficiently find a string $s \in F$ such that

  • $x$ is a substring of $s \cdot u$
  • The number of lexicographically earlier strings $s' \in F$ with this property is $\mathcal o(n)$

We say that $F$ is regex-searchable if instead of requiring $x$ to be a substring of $s \cdot u$, we require $s \cdot u$ to satisfy the $x$ when interpreted as a regular expression.

For any $n$, can find a searchable field with strings of length $>n$? What about a regex-searchable field?

  • $\begingroup$ Do you want F itself to be efficiently constructible? As I recall, we only even know how to Co structure finite fields efficiently using GRH or using probabilistic algorithms. What kind of assumptions are you okay with? $\endgroup$ Feb 24, 2018 at 19:39
  • $\begingroup$ @JoshuaGrochow $F$ is all strings of length $n$. Also probabilistic algorithms are fine. $\endgroup$ Feb 24, 2018 at 19:42
  • $\begingroup$ Ah, okay. Is there a bijection between strings and field elements, so the field must have characteristic 2? Or can elements be represented by more than one string? $\endgroup$ Feb 24, 2018 at 20:27
  • $\begingroup$ @JoshuaGrochow it's bijective, but I do not require the strings to be binary strings. $\endgroup$ Feb 24, 2018 at 20:57
  • $\begingroup$ So you're saying that the field is actually some extension field of the form $GF(q^m)$ and the strings are over $GF(q)$. $\endgroup$
    – kodlu
    Feb 25, 2018 at 6:08


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.