计算多项式的逆元算法

Question

计算多项式的逆元算法

algorithmpolynomial-mathinversentruencrypt

7

我正在寻找一个算法（或代码）帮助我计算多项式的逆，我需要它来实现NTRUEncrypt。我更喜欢易于理解的算法，虽然有伪代码可以做到这一点，但它们仍然很困惑且难以实现，而且仅凭伪代码我无法真正理解过程。

是否有任何算法可以计算关于截断多项式环的多项式的逆？

- Mohammad Sepahvand

3

你想要哪种逆运算？是要求逆函数，解（即因式分解）多项式，还是要在由一些基本域和一个不可约多项式构成的商环中找到多项式乘法的逆元？NTRU代表“Number Theorists R Us”，如果我没记错的话，所以很难直观地了解需要什么数学知识。http://en.wikipedia.org/wiki/NTRUEncrypt上写着“加密和解密都只使用简单的多项式乘法”，因此该文章也没有告诉我你的意思。无论需要什么，这都可以成为一个MathOverflow问题。 - Steve Jessop

1

在这种情况下，仔细地逐步复制伪代码。当他们说像 f(X):=a(X) 这样的话时，他们的意思是 f 是你程序中的一个变量，a 是函数的输入，并且这两个东西的类型都是“多项式”。例如，f(X)/X 的意思是 x^2 + x + 0 -> x + 1。另一个棘手的部分是当你最终得到答案时，你必须将它对 X^N-1 取模。 - Steve Jessop

1

哦，还要为您的函数编写单元测试。您应该能够将输出乘以输入，对系数取模2，对结果多项式取模X^N-1，并获得多项式1（即，除了最后一个系数外，所有系数都为0）。 - Steve Jessop

1

非常感谢Steve，我正在非常仔细地逐行实现伪代码，这里有一个更清晰的扩展伪代码：http://www.wpi.edu/Pubs/ETD/Available/etd-0430102-111906/unrestricted/corourke.pdf，在第27页上，我正在仔细编码并使用NTRU给出的一些示例答案进行测试。我认为我在理解伪代码方面也受到了阻碍，在我的代码中，我给多项式f设置了固定长度和一组值，并且8-31的无限循环从未结束，感谢指出f是一个变量。还有什么需要注意的技巧吗？ - Mohammad Sepahvand

1

脑海里一时没有想法。在“步骤1：初始化”中列出的所有内容都是变量，并且会在某个地方被修改。您应该看到f和g（按其最高非零系数）变得越来越小，而b、c和k则实际上记录了您对f和g所做的操作。一旦f在第5步变得尽可能小（1），则在b和k中“建立”的内容将为您提供逆运算，您只需将这些信息组合在一起即可。作为实现细节，如果您将多项式存储为系数数组，则乘以或除以x只需将所有内容向左移动一位即可。 - Steve Jessop

显示剩余7条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- William Whyte · Accepted Answer

我在 Security Innovation 工作，该公司拥有 NTRU，很高兴看到这个问题受到关注。

IEEE 标准 1363.1-2008 指定了如何使用最新的参数集来实现 NTRUEncrypt。它给出了以下多项式反演的规范：

除法：

输入为两个多项式 a 和 b，其中 b 的次数为 N-1，b_N 是 b 的首项系数。输出为 q 和 r，使得 a = q*b + r 且 deg(r) < deg(b)。r_d 表示 r 的 d 次系数，即 r 的首项系数。

a)  Set r := a and q := 0
b)  Set u := (b_N)^–1 mod p
c)  While deg r >= N do
  1)    Set d := deg r(X)
  2)    Set v := u × r_d × X^(d–N)
  3)    Set r := r – v × b
  4)    Set q := q + v
d)  Return q, r

在这里，r_d 是d次项的系数。

扩展欧几里得算法：

a)  If b = 0 then return (1, 0, a)
b)  Set u := 1
c)  Set d := a 
d)  Set v1 := 0
e)  Set v3 := b
f)  While v3 ≠ 0 do
  1)    Use the division algorithm (6.3.3.1) to write d = v3 × q + t3 with deg t3 < deg v3
  2)    Set t1 := u – q × v1
  3)    Set u := v1
  4)    Set d := v3
  5)    Set v1 := t1
  6)    Set v3 := t3
g)  Set v := (d – a × u)/b  [This division is exact, i.e., the remainder is 0]
h)  Return (u, v, d)

在Z_p上的逆元，其中p是一个质数：

a)  Run the Extended Euclidean Algorithm with input a and (X^N – 1).  Let (u, v, d) be the output, such that a × u + (X^N – 1) × v = d = GCD(a, (X^N – 1)).
b)  If deg d = 0, return b = d^–1 (mod p) × u
c)  Else return FALSE

在 Z_p^e 中求逆元 / （M（X）为合适的多项式，例如 X^N-1，p为质数）

a)  Use the Inversion Algorithmto compute a polynomial b(X) ε R[X] that gives an inverse of a(X) in (R/pR)[X]/(M(X)). Return FALSE if the inverse does not exist. [The Inversion Algorithm may be applied here because R/pR is a field, and so (R/pR)[X] is a Euclidean ring.]
b)  Set n = p
c)  While n <= e do
  1)    b(X) = p × b(X) – a(X) × b(X)^2   (mod M(X)), with coefficients computed modulo p^n
  2)    Set n = p × n
d)  Return b(X) mod M(X) with coefficients computed modulo p^e.

如果你正在完整地实现NTRU，你应该看看是否可以让你的机构购买1363.1，因为原始的NTRU加密对抗主动攻击者并不安全，而1363.1描述了修复此问题的消息处理技术。

(更新2013-04-18: 感谢Sonel Sharam在以前版本中发现的一些错误)