相关疑难解决方法(0)

为了加快我的bignum除数,我需要加速y = x^2bigints的操作,bigints被表示为无符号DWORD的动态数组.要明确:

DWORD x[n+1] = { LSW, ......, MSW };

• 其中n + 1是使用的DWORD的数量
• 所以数量的价值 x = x[0]+x[1]<<32 + ... x[N]<<32*(n)

问题是:如何在y = x^2没有精度损失的情况下尽快计算？ - 使用C++和整数算术(32位带Carry)处理.

我目前的方法是应用乘法y = x*x并避免多次乘法.

例如:

x = x[0] + x[1]<<32 + ... x[n]<<32*(n)

为简单起见,让我重写一下:

x = x0+ x1 + x2 + ... + xn

其中index表示数组内的地址,因此:

y = x*x
y = (x0 + x1 + x2 + ...xn)*(x0 + x1 + x2 + ...xn)
y = x0*(x0 …

I wanted to use NTT for fast squaring (see Fast bignum square computation), but the result is slow even for really big numbers .. more than 12000 bits.

So my question is:

1. Is there a way to optimize my NTT transform? I did not mean to speed it by parallelism (threads); this is low-level layer only.
2. Is there a way to speed up my modular arithmetics?

This is my (already optimized) source code in C++ for NTT (it's complete …