Function lbcrypto::ComputeDegreesPS

• Defined in File ckksrns-utils.cpp

Function Documentation

std::vector<uint32_t> lbcrypto::ComputeDegreesPS(uint32_t n)

Computes the values of the internal degrees k and m needed in the Paterson-Stockmeyer algorithm such that k(2^m - 1} > n and k close to sqrt(n/2).

Compute positive integers k,m such that n < k(2^m-1), k is close to sqrt(n/2) and the depth = ceil(log2(k))+m is minimized. Moreover, for that depth the number of homomorphic multiplications = k+2m+2^(m-1)-4 is minimized. Since finding these parameters involve testing many possible values, we hardcode them for commonly used degrees, and provide a heuristic which minimizes the number of homomorphic multiplications for the rest of the degrees.

Parameters

n – the degree of a polynomial.

Returns

a vector containing k and m.