指示功能的算術電路？
指標函式（或特徵函式）定義為 $ f_{t^}:\mathbb{Z}_q\to \mathbb{Z}q $ 滿足 $ f{t^}(t)=1 $ 如果 $ t^=t $ 和 $ f_{t^}(t)=0 $ ， 否則。（這裡 $ t^\in \mathbb{Z}_q $ 給出定義函式。）我正在處理將函式轉換為帶有加法門和乘法門的算術電路。我知道如果 $ t^, t\in {0,1} $ 那麼我們可以為這個函式使用一個與非門（在布爾代數中）。然而，使用算術電路，轉換似乎並不簡單。
你能幫我解決這個問題嗎？非常感謝！
更新：
（單變數）指示函式（或特徵函式）定義為 $ f_{t^}:\mathbb{Z}_q\to \mathbb{Z}q $ 滿足 $ f{t^}(t)=1 $ 如果 $ t=t^* $ 和 $ f_{t^}(t)=0 $ ， 否則。（這裡 $ t^\in \mathbb{Z}q $ 給出定義函式。）更一般地，在多變數的情況下，我們定義 $ f{t^}:\mathbb{Z}_q^d\to \mathbb{Z}q $ , $ f{t^}(t_1, \cdots, t_d)=1 $ 如果 $ \exists t_i $ 這樣 $ t_i=t^* $ 和 $ f_{t^*}(t_1, \cdots, t_d)=0 $ ， 否則。
我正在尋找可用於表示這些函式的多項式。到目前為止，我已經找到了一些單變數情況：
- 使用拉格朗日插值：如 $ t, t^* \in \mathbb{Z}q={0,1, \cdots, q-1 } $ 那麼這樣的多項式應該通過點 $ (0,0), (1,0), $ $ \cdots, $ $ (t^-1,0), (t^, 1), $ $ (t^*+1, 0), $ $ \cdots, $ $ (q-1,0) $ . 我們可以構造 $ f{t^}(t)=\frac{t(t-1)\cdots (t-t^+1)(t-t^-1)\cdots (t-q+1)}{t^(t^-1)\cdots (t^-t^+1)(t^-t^-1)\cdots (t^-q+1)} (\bmod q) $ 通過拉格朗日插值法。然而，多項式的度數為 $ q-1 $ 並且看起來分析起來很複雜。
- 使用費馬小定理：費馬小定理指出，如果 $ q $ 是一個素數，那麼對於任何整數 $ a $ 不能被 $ q $ ， 號碼 $ a^{q-1}=1 ~(\bmod q) $ . 然後我們可以構造 $ f_{t^}(t)=1-(t-t^)^{q-1}~ (\bmod q) $ ， 如果 $ q $ 是素數。這個多項式看起來更簡單，但在以下情況下可能仍然沒有幫助 $ q $ 是一個很大的整數。
問題是是否有比上述更簡單的多項式。當我試圖將論文第 4.2-4.3 節中的想法應用到指標函式時提出了這個問題： https ://www.iacr.org/archive/eurocrypt2014/84410298/84410298.pdf。
任何學位 $ d $ 多項式（在一個域上）至多有 $ d $ 根（除非它完全為零）。由於指標函式有 $ q-1 $ 根，人們知道它必須有度 $ \geq q-1 $ . 可以將其推廣到多元多項式（最著名的是Schwartz-Zippel）。您可能會嘗試推廣到非領域，但很快就會遇到奇怪的行為 — 說完 $ \mathbb{Z}/6\mathbb{Z} $ 線性函式 $ f(x) = 3x $ 有 $ \geq 1 $ 根。這是因為它雖然“在 CRT 組件中為零”，但我不知道如何進行適當的概括以避免此類問題。
問題中考慮的門可用於建構任何具有係數和變數的多項式 $ \mathbb Z_q $ . 什麼時候 $ q $ 是素數，多項式 $ P(x) $ 在 $ \mathbb Z_q $ 學位 $ k>0 $ 最多有 $ k $ 根，即點 $ x $ 在 $ \mathbb Z_q $ 和 $ P(x)=0 $ . 功能 $ f_{t^*} $ 有 $ q-1 $ 根並且不匹配任何常數多項式，因此我們至少需要一個次數多項式 $ q-1 $ 實施它。
一次多項式 $ q-1 $ 匹配 $ f_{t^*} $ 可以構造為 $$ P(x)=\begin{cases} (q-1)\displaystyle\prod_{i\in\mathbb Z_q,,i\ne t}(x+(q-i))&\text{ if }t\text{ is even}\ \quad\quad\quad,\displaystyle\prod_{i\in\mathbb Z_q,,i\ne t}(x+(q-i))&\text{ if }t\text{ is odd} \end{cases} $$ 可以用 $ q-1 $ 雙輸入加法門[如果少一個 $ t $ 是非零，因為其中之一 $ (q-i) $ 為零]，並且 $ q-1 $ 雙輸入乘法門 [如果 $ t $ 很奇怪]。
我無法證明這種構造在門方面是最小的猜想。