On 04/04/2014, at 4:28 AM, Niels Möller wrote:
>> (1) the bit bounds for the coefficients get worse. For example if u =
>> 5 then f(x) = x^5 + x^4 + x + 1, so when you compute say a(x) b(x) mod
>> f(x) (in Z[x]), every coefficient in the result is a sum of up to
>> *five* terms from a(x) b(x). I
David Harvey writes:
> It is possible to do everything using the polynomial f(x) you suggest
> above (in this case the factorisation does lift to Z[x]), and I think
> this may have been what I tried first.
>
> But it has a few disadvantages:
>
> (1) the bit bounds for the coefficients get worse.
On 03/04/2014, at 4:53 PM, Niels Möller wrote:
>> I propose using a modulus of the form
>>
>> M = (B^{k u_1} + 1) (B^{k u_2 + 1) ... (B^{k u_s} + 1),
>>
>> where
>>
>> B = 2^64
>> k is some integer
>> u_1 > u_2 > ... > u_s is a decreasing sequence of powers of 2.
>
> Seems closely related to