# Prime modulus in CKKS Primes in CKKS have multiple uses in CKKS and each has it's own constraint to their possible value. Accuracy. prime size is the size of the scale of the scheme. The larger the prime - the more accurate the computation will be. Runtime. the primes used for RNS representation of large numbers (polynomial coefficients) s.t. each RNS component (modulo prime) is less than 64 bits. This enables "decomposing" large numbers to word-size elements where arithmetics is computed leveraging CPU level implementation for those operations. To furthermore improve runtime, the primes are used to support NTT representation of each RNS component. This constraint each prime $p$ to satisfy $n|p-1$ . > Note: primes are stored as uint64 types and so their size does not effect their runtime (as long as they are smaller than 64bits) Security. to maintain security - the total sum of prime's bit size is bounded above with different threshold for every $n$ i.e., choosing larger total will reduce the security level of the scheme[^1]. For example, for $n=2^{15}$, the total size of the primes is limited to maximum 880 bits. ## Summary of prime's constraints - $|p|< 64$ bits - $n|p-1$ - total size of primes is limited by security and depends on n e.g., n=16K then $\sum |p_i|< 880$ bits. - trade-off between accuracy (single prime size $|p_i|$) and multiplication depth $L$: fixed total size = $L\times |p_i|$ . Related: [[Miller-Rabin primality test]], [[Pollard's Rho factoring]] ## Created 2024-10-16 10:50 [^1]: [[@Homomorphic Encryption Standard]]