1
$\begingroup$

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

static long ms[][4] = {  // 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[4]); i++) { 
  if (ms[i][0] < N || GCD(p, ms[i][1]) != 1) continue;
  long ordP = multOrd(p, ms[i][1]);
  long nSlots = ms[i][0]/ordP;
  if (d != 0 && ordP % d != 0) continue;
  if (nSlots < s) continue;

  m = ms[i][1];
  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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Hilder Vítor Lima Pereira Jun 13 '17 at 22:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.