Coeffmodulu minimum support value

[Tangjacson]

I try to find the minimum support value for CKKS.
Interestingly, for N=2^15, coeffModulus = [17,20] can work successfully, but [18,20],[19,20] would raise error of ' failed to find enough prime'.

Why [17,20] work, but [18,20] can not. What's the problem with this or which verification rule related to.

[fionser]

• a prime p should be p = 1 mod 2N
• So I guess SEAL fails to find a 18, 19 bits prime such that p > 2^18 and p = 1 mod 2^16.

[Tangjacson]

Thanks for you answer.

If i am correct, I assume that p is of form k*(2^n)+1.
I looked into the SEAL's code, and i find the seleciting primes part as follows.

 vector<Modulus> get_primes(uint64_t factor, int bit_size, size_t count)
        {
#ifdef SEAL_DEBUG
            if (!count)
            {
                throw invalid_argument("count must be positive");
            }
            if (bit_size > SEAL_MOD_BIT_COUNT_MAX || bit_size < SEAL_MOD_BIT_COUNT_MIN)
            {
                throw invalid_argument("bit_size is invalid");
            }
#endif
            vector<Modulus> destination;

            // Start with (2^bit_size - 1) / factor * factor + 1
            uint64_t value = ((uint64_t(0x1) << bit_size) - 1) / factor * factor + 1;

            uint64_t lower_bound = uint64_t(0x1) << (bit_size - 1);
            while (count > 0 && value > lower_bound)
            {
                Modulus new_mod(value);
                if (new_mod.is_prime())
                {
                    destination.emplace_back(move(new_mod));
                    count--;
                }
                value -= factor;
            }
            if (count > 0)
            {
                throw logic_error("failed to find enough qualifying primes");
            }
            return destination;
        }

The case here seems like that it begins from 2^bits, and substracts 2^n in each loop. However, shouldn't it begin from 2^bits+1-2^n? Because it can only select value (2^(bits-1)+1,2^bit-1) and it should in form k*2^n+1.

[fionser]

The init value should be ok, because for each found prime, p it should not larger thatn 2^bit.

[Tangjacson]

I mean p should be in form of k*2^n+1. So it should start at the largest value in this form and also not lager than 2^bit. You see from the code that the step of loop is factor = 2^n (not 1).