find other parameter p for DGT an RNS

[DevinRen]

i want to use dgt and rns(crt) to build a polymul scheme. RNS needs several multiple modules, In your article ,only p=0xFFFFFFFF00000001. Can you tell me, Is there any other excellent parameter ,like p=0xFFFFFFFF00000001.

[jnortiz]

Hello @DevinRen! I hope this paper may help you: https://ieeexplore.ieee.org/document/5223368?arnumber=5223368 []'s

[DevinRen]

I read your paper "Efficient Polynomial Multiplication via Modified Discrete Galois Transform and Negacyclic Convolution"

The reader should make a distinction between the numbers p and q. Usually,q is a product of several “small” primes {p0, p1, . . . , pr−1}. However, in some implementations, the transforms are done in GF(ˆp) << pi, where ˆp is a specially chosen prime.

I found that I had made a mistake,, I used to think that ˆ p is one of the "small primes p0''.

In paper ,the condition of having the coefficients of input polynomials are in [0, q ≤ square root of(ˆp/(2n))].

So,i should find the “small” primes {p0, p1, . . . , pr−1} in [0, q ≤ (ˆp/(2n))(1/2)]，am I right？

[pdroalves]

Hi @DevinRen ,

0xFFFFFFFF00000001 is the Solinas prime 2^64-2^32+1. This class of primes, including Mersennas primes, are known to have very efficient modular reductions, which can be computed with integer additions and bitwise shifts. There are only a few integers with less than 64 bits that fit any of these classes, so we don't use to rely on them to implement the RNS.

[pdroalves]

The selection of coprimes for RNS depends on the context. You must select a set of coprimes such that the product of all elements is bigger than the maximum value you expect to represent in the RNS domain.

For instance, the base {3, 5, 7} has an upper bound 3 5 7 = 105, so you can only use it if you expect the numbers to be <= 104.