<p>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$).</p>

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

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

<p>We say that $F$ is <strong>regex-searchable</strong> 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.</p>

<p>For any $n$, can find a searchable field with strings of length $&gt;n$? What about a regex-searchable field?</p>

CC BY-SA 3.0
2018-02-24T19:39:37.997Z
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
CC BY-SA 3.0
2018-02-24T19:42:55.837Z
@JoshuaGrochow $F$ is all strings of length $n$. Also probabilistic algorithms are fine.
Christopher King
CC BY-SA 3.0
2018-02-24T20:27:13.373Z
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
CC BY-SA 3.0
2018-02-24T20:57:49.617Z
@JoshuaGrochow it's bijective, but I do not require the strings to be binary strings.
Christopher King
CC BY-SA 3.0
2018-02-25T06:08:58.610Z
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
CC BY-SA 3.0
2018-02-25T06:39:21.710Z
@kodlu the strings are just sequence of symbols. The number of symbols is $k$, for some prime power $k$, so that the field must be isomorphic to $GF(k^n)$.
Christopher King
<regular-expressions><search-problem><finite-fields><minimization>
Searchable finite field
Christopher King
# Searchable finite field

(Asked by: username_0 on 2018-02-24)

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?

**Tags:** regular-expressions, search-problem, finite-fields, minimization
> **Comments:**
> **username_1**: 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?  
> **username_0**: @JoshuaGrochow $F$ is all strings of length $n$. Also probabilistic algorithms are fine.  
> **username_1**: 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?  
> **username_0**: @JoshuaGrochow it's bijective, but I do not require the strings to be binary strings.  
> **username_2**: 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)$.  
> **username_0**: @kodlu the strings are just sequence of symbols. The number of symbols is $k$, for some prime power $k$, so that the field must be isomorphic to $GF(k^n)$.  

---

## 0 answers

