小编min*_*max的帖子

我想用NTT实现多项式的乘法.我遵循数论变换(整数DFT),它似乎工作.

现在我想在有限域Z_p[x]上实现多项式的乘法,其中有限域p是任意素数.

p与之前的无界情况相比,它是否会改变系数现在受限制的任何东西？

特别是,原始NTT需要找到素数N作为工作模数,该工作模数大于(magnitude of largest element of input vector)^2 * (length of input vector) + 1结果永不溢出.如果结果将受到该p素数的限制,那么模数可以有多小？请注意,p - 1不必是形式(some positive integer) * (length of input vector).

编辑:我从上面的链接复制粘贴源来说明问题:

# 
# Number-theoretic transform library (Python 2, 3)
# 
# Copyright (c) 2017 Project Nayuki
# All rights reserved. Contact Nayuki for licensing.
# https://www.nayuki.io/page/number-theoretic-transform-integer-dft
#

import itertools, numbers

def find_params_and_transform(invec, minmod):
    check_int(minmod)
    mod = find_modulus(len(invec), …

的回答给出了计算下面的代码floor(sqrt(x))只使用整数.是否可以使用/修改它来返回ceil(sqrt(x))？或者,计算这种价值的首选方法是什么？

编辑:谢谢大家到目前为止我道歉,我应该让它更明确:我希望有更多的"自然"方式来做这个使用floor(sqrt(x)),可能加一个.该floor版本使用牛顿的方法从上面接近根,我认为可能从下面接近它或类似的做法.

例如,答案甚至提供了如何舍入到最接近的整数:只输入4*x算法.

我想尝试实现Yun的多项式无平方因子分解算法.来自维基百科(f是多项式):

a0 = gcd(f, f'); b1 = f/a0; c1 = f'/a0; d1 = c1 - b1'; i = 1
repeat
ai = gcd(bi, di); bi+1 = bi/ai; ci+1 = di/ai; i = i + 1; di = ci - bi'
until b = 1

但是,我不确定第二步.我想将它用于具有整数系数的多项式(不需要monic或primitive).是否有可能b1 = f/a0只使用整数实现除法？

我找到了合成分部的代码:

def extended_synthetic_division(dividend, divisor):
    '''Fast polynomial division by using Extended Synthetic Division. Also works with non-monic polynomials.'''
    # dividend and divisor are both polynomials, which …

我发现了一篇非常有趣的关于适用于就地FFT的位反转算法的论文:Urszula Rutkowska从1990年开始的"一种简单的位反转置换算法"(doi.org/10.1016/0165-1684(91)90008-7 ).

然而,她的算法G1不会出现.因为第一个迭代的结果是出界外的错误为工作N1 = L << 1和swap(a + 1, a + N1);.我假设L是指输入向量的长度.

请问,有没有人知道是否有纸张的勘误或如何修复算法？

论文的伪代码:

G1(L)
{int     i,j,L1
         N1,N2,a,b;
unsigned k;
j=0;    L1=L-1;
N1=L<<1;N2=N1+1;
for(i=0;i<L1;i++)
{if(i<j)
    { a=i<<1;
      b=j<<1;
      swap(a,b);
      swap(a+N2,b+N2);
      swap(a+1,b+N1);
      swap(b+1,a+N1);
    }
 else
    if(i==j)
    { a=i<<1;
      swap(a+1,a+N1);
    }
 k=L>>1;
 while(k<=j){ j=j-k;
              k=k>>1;
            }
 j+=k;
 }
 i<<=1;
 swap(i+1,i+N1);
}

论文截图: