crypto/ringlwe/FFT/FFT_433_35507.c
/*
We use Bluestein's trick and integer convoution by CRT.
*/
We use Bluestein's trick and integer convoution by CRT.
We use Bluestein ' s trick and integer convoution by CRT .
void FFT_forward_433_35507(FFTSHORT x[433]) {
        const FFTSHORT n = 433;
        const FFTSHORT q = 35507;
        const FFTSHORT N = 1024;
	FFTSHORT x0[1024], x1[1024];
	FFTSHORT i;
	FFTLONG x_crt[1024];
	const FFTSHORT q0 = 8816641, Ninvq0 = 8808031;	
	const FFTSHORT q1 = 17633281, Ninvq1 = 17616061;
	const FFTLONG h0 = 17633282UL, h1 = 17633281UL;
	const FFTLONG q0q1 = 155466308229121UL;
	for (i = 0; i < n; ++i) {
		MUL_MOD(x0[i], x[i], Bluestein_mul_433_35507[i], q);
	}
	memset((void *) (x0+n), 0, (N-n)*sizeof(FFTSHORT)); 
	memcpy((void *) x1, (void *) x0, N*sizeof(FFTSHORT)); 
	FFT_forward_1024_8816641(x0);
	FFT_forward_1024_17633281(x1);
	for (i = 0; i < N; ++i) {
		MUL_MOD(x0[i], x0[i], Bluestein_roots_fft_433_8816641[i], q0);
		MUL_MOD(x1[i], x1[i], Bluestein_roots_fft_433_17633281[i], q1);		
	}
	FFT_backward_1024_8816641(x0);
	FFT_backward_1024_17633281(x1);
	for (i = 0; i < N; ++i) {
		MUL_MOD(x0[i], x0[i], Ninvq0, q0); 
		MUL_MOD(x1[i], x1[i], Ninvq1, q1); 
		x_crt[i] = h1*x0[i] % q0q1;
		x_crt[i] = q0q1 - x_crt[i];
		x_crt[i] += h0*x1[i];
		x_crt[i] = x_crt[i] % q0q1; 
		x_crt[i] = x_crt[i] % q; 
	}
	x[0] = (FFTSHORT) x_crt[(N>>1)-1];
	for (i = 0; i < n-1; ++i) {
		MUL_MOD(x[i+1], x_crt[(N>>1)+i], Bluestein_mul_433_35507[i], q);
	}		
}
void FFT_forward_433_35507 ( FFTSHORT x [ 433 ] ) { const FFTSHORT n = 433 ; const FFTSHORT q = 35507 ; const FFTSHORT N = 1024 ; FFTSHORT x0 [ 1024 ] , x1 [ 1024 ] ; FFTSHORT i ; FFTLONG x_crt [ 1024 ] ; const FFTSHORT q0 = 8816641 , Ninvq0 = 8808031 ; const FFTSHORT q1 = 17633281 , Ninvq1 = 17616061 ; const FFTLONG h0 = 17633282UL , h1 = 17633281UL ; const FFTLONG q0q1 = 155466308229121UL ; for ( i = 0 ; i < n ; ++ i ) { MUL_MOD ( x0 [ i ] , x [ i ] , Bluestein_mul_433_35507 [ i ] , q ) ; } memset ( ( void * ) ( x0 + n ) , 0 , ( N - n ) * sizeof ( FFTSHORT ) ) ; memcpy ( ( void * ) x1 , ( void * ) x0 , N * sizeof ( FFTSHORT ) ) ; FFT_forward_1024_8816641 ( x0 ) ; FFT_forward_1024_17633281 ( x1 ) ; for ( i = 0 ; i < N ; ++ i ) { MUL_MOD ( x0 [ i ] , x0 [ i ] , Bluestein_roots_fft_433_8816641 [ i ] , q0 ) ; MUL_MOD ( x1 [ i ] , x1 [ i ] , Bluestein_roots_fft_433_17633281 [ i ] , q1 ) ; } FFT_backward_1024_8816641 ( x0 ) ; FFT_backward_1024_17633281 ( x1 ) ; for ( i = 0 ; i < N ; ++ i ) { MUL_MOD ( x0 [ i ] , x0 [ i ] , Ninvq0 , q0 ) ; MUL_MOD ( x1 [ i ] , x1 [ i ] , Ninvq1 , q1 ) ; x_crt [ i ] = h1 * x0 [ i ] % q0q1 ; x_crt [ i ] = q0q1 - x_crt [ i ] ; x_crt [ i ] += h0 * x1 [ i ] ; x_crt [ i ] = x_crt [ i ] % q0q1 ; x_crt [ i ] = x_crt [ i ] % q ; } x [ 0 ] = ( FFTSHORT ) x_crt [ ( N >> 1 ) - 1 ] ; for ( i = 0 ; i < n - 1 ; ++ i ) { MUL_MOD ( x [ i + 1 ] , x_crt [ ( N >> 1 ) + i ] , Bluestein_mul_433_35507 [ i ] , q ) ; } }
We use Bluestein's trick and integer convoution by CRT.
We use Bluestein ' s trick and integer convoution by CRT .
/*Setup Bluestein's method*/ /*Pad with 0's*/ /*Copy x0 into x1*/ /*Cyclic convolution*/ /*Apply the CRT*/ /*Scaling for the convolution*/ /*Scaling for the convolution*/ //Will now be the integer convolution /*Complete Bluestein's trick*/