Any interest in multi-threaded code?

Niels Möller nisse at
Mon May 7 19:37:39 UTC 2018

Victor Shoup <shoup at> writes:

> Then I found out about .bootstrap...that doesn't work either
> (no aclocal-1.8).  Tried editing .bootstrap to remove "-1.8"...errors.

The ./.bootstrap script used to work back in the day. It lists the
needed steps, and it might work with more recent versions of the tools,
otherwise might need to be renamed to and
updated according to any error messages from autoconf and automake.

> And while I'm at it, is there a brief statement about 
> what exactly the function mpn_fourier_transform_ct actually does?
> I mean, questions like: are the inputs/outputs in standard order
> or bit-reverse order?

I'm fairly sure inputs are expected in standard order (viewed as
coefficients of a polynomial, ordered by increasing powers of the
variable), and outputs in bit reversed order, same as
mpn_fourier_transform_truncated. I don't remember the layout of the
padding, but that might be clear from the definition of SPFFT_PAD_INDEX.
Except for padding (and any inputs related to twidde factors), I think
inputs and outputs should be identical to

Inputs and outputs are also not necessarily a power of two. I think the
size of the underlying fft is 2^k.

Input size is xn, with implicit zero padding up to 2^k.

Output size l. The last 2^k - values (last *in bit reversed indices*)
are not computed, since it's a truncated fft.

It's required that 2^{k-1} < l < 2^k, and xn <= l.

I think it's best to first ensure that the no-_ct versions of the
transform functions are working properly, before digging into the _ct
versions. Logic to enable ct is in fourier_params.c, starting at line

Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.

More information about the gmp-devel mailing list