0
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • $\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$
    – Joshua Grochow
    Feb 24, 2018 at 19:39
  • $\begingroup$ @JoshuaGrochow $F$ is all strings of length $n$. Also probabilistic algorithms are fine. $\endgroup$
    – PyRulez
    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$
    – Joshua Grochow
    Feb 24, 2018 at 20:27
  • $\begingroup$ @JoshuaGrochow it's bijective, but I do not require the strings to be binary strings. $\endgroup$
    – PyRulez
    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

0

Reset to default

Your Answer

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