# Searchable finite field

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?

• 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? – Joshua Grochow Feb 24 '18 at 19:39
• @JoshuaGrochow $F$ is all strings of length $n$. Also probabilistic algorithms are fine. – PyRulez Feb 24 '18 at 19:42
• 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? – Joshua Grochow Feb 24 '18 at 20:27
• @JoshuaGrochow it's bijective, but I do not require the strings to be binary strings. – PyRulez Feb 24 '18 at 20:57
• 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)$. – kodlu Feb 25 '18 at 6:08