如何在 Zp 中找到函式的係數XXx?
我是有限域算術的新手，在嘗試用程式語言實現基於橢圓曲線密碼的 ABE 方案時，我無法理解如何實現函式域。
我在有限域內得到了一個函式定義 $ p(i.e. Z_p[x]) $ 在哪裡 $ p $ 是一些大素數。我如何找到的係數 $ x^k $ 在擴大 $ f(x) $ ?
函式定義： $$ f(x)=\prod_{i=1}^3 (x+H(i))^i $$ 其中，H(k) 是一個單向雜湊函式，輸出較大。
Q1。由於函式定義在 $ Z_p[x] $ , 是否應該首先使用初等代數計算所有係數，然後取模 $ p $ ?
Q2。如果我們要計算 $ f(\alpha) $ ， 在哪裡 $ \alpha $ 是一些常數，我們可以使用上一步的最終函式多項式並將所有 x 替換為 $ \alpha $ 然後取一個模數 $ p $ 再次？
在這種情況下，您總是可以做的一件事是“將減量推遲到最後”。通過這個，我的意思是做你所有的計算 $ \mathbb{Z}[x] $ ，然後在最後“執行歸約，直到你不再可以”，您在其中進行的兩種歸約 $ \mathbb{Z}/p\mathbb{Z}[x] $ 是：
- 模組化減少（係數）： $ a\mapsto a\bmod p $
- 根據費馬小定理（如果工作模式）減少（變數） $ n $ 對於合數，請改用歐拉定理）： $ x^k\mapsto x^{k\bmod \varphi(p)}\bmod p = x^{k\bmod (p-1)} $
正如 kelalaka 指出的那樣，您可以先擴展 $ f(x) $ 作為 6 次多項式。作為 $ p $ 與度數相比很大（除非“大”是指 5 之類的東西），您不需要減少第二種類型，因此可以單獨減少 $ f(x) $ 反對 $ p $ .
如果您必須即時進行這些計算，這不是最有效的做法（作為初始計算 $ f(x) $ 與簡化版本相比，它可能具有非常大的表示，並且您可能必須在計算時使用非常大的數字進行算術運算），但它在**概念上很有用，並且在您需要預處理多項式時很好（如你現在做）。
本質上，多項式算術 $ \bmod n $ 可以拆分為（熟悉的）整數多項式算術，然後應用上述兩個歸約規則。
我如何找到的係數 $ x^k $ 在擴大 $ f(x) $ ?
$$ f(x)=\prod_{i=1}^3 (x+H(i))^i $$
使用 Wolfram Alpha線上嘗試
$$ f(x) = (H(1) + x) (H(2) + x)^2 (H(3) + x)^3 $$並在那裡查看擴展表格。
這是一次性的工作。如果 $ H $ 定義也可以縮短。這 $ H(i) $ 值應減少為 $ \pmod p $ 乘法前
$$ f(x) = (H(1) \bmod p+ x) (H(2) \bmod p + x)^2 (H(3) \bmod p+ x)^3 $$
這 $ x^k $ 在那邊。使用SageMath 符號係數，您也可以做到。（在這裡試試）
var('x,a,b,c') p = (x+a)*(x+b)^2*(x+c)^3 print(p.collect(x)) #Collect the coefficients into a group. coef = 5 print( "coeff x^", coef, " = ", p.coefficient(x^coef))Q1。因為，函式定義在 $ Z_p[x] $ ，是否應該首先使用初等代數計算所有係數，然後使用 p 取模？
不，沒必要，你只需要計算貢獻的那些 $ x^k $ .
Q2。如果我們要計算 $ f(\alpha) $ ， 在哪裡 $ \alpha $ 是一些常數，我們可以使用上一步的最終函式多項式並將所有 x 替換為 $ \alpha $ 然後取一個模數 $ p $ 再次？
首先，應用 $ \alpha $ ，那麼所有的都是數字，並在每一步取模來計算，以減少乘法時間，這就像模重複平方算法一樣常見。