# Why use Phi(m) divide Order(p, m) to get slot number in HElib?

I am reading HElib source code, and have a confusion about FindM function:

static long ms[] = {  // pre-computed values of [phi(m),m,d]
//phi(m), m, ord(2),c_m*1000 (not used anymore)
{ 1176,  1247, 28,  3736}, // gens=5(42)
......
};
for (i=0; i<sizeof(ms)/sizeof(long); i++) {
if (ms[i] < N || GCD(p, ms[i]) != 1) continue;
long ordP = multOrd(p, ms[i]);
long nSlots = ms[i]/ordP;
if (d != 0 && ordP % d != 0) continue;
if (nSlots < s) continue;

m = ms[i];
break;
}


What I can't understand is why use Phi(m) to divide Order(p, m) to get the slot number? Is there special requirement of getting slot number?

• I know that if the m-th cyclotomic polynomial $\Phi_m(x)$ factors mod $p$, then, it is a product of polynomials of equal degree (let's say, this degree is $d$). Also, the degree of $\Phi_m(x)$ is $\varphi(m)$. Therefore, if $\Phi_m(x)$ is a product of $k$ polynomials, we have that $k = \frac{\varphi(m)}{d}$. So, what remains here is to check why $d$ equals Order(p,m)... Note the $k$ is the number of slots. – Hilder Vítor Lima Pereira Jun 13 '17 at 22:13