How zetas are computed in CRYSTALS-Kyber?

Question

As shown below it explains how generate zetas table and use it. But curious thing is that how KYBER_ROOT_OF_UNITY constant is generated ? I've tried multiple ways to generated it and cannot explain how it is found. Maybe I missed some little point. Let's says prime is 1073692673 how can I find also equivalent root_of_unity of this number ?

/* Code to generate zetas and zetas_inv used in the number-theoretic transform:

#define KYBER_ROOT_OF_UNITY 17

static const uint8_t tree[128] = {
  0, 64, 32, 96, 16, 80, 48, 112, 8, 72, 40, 104, 24, 88, 56, 120,
  4, 68, 36, 100, 20, 84, 52, 116, 12, 76, 44, 108, 28, 92, 60, 124,
  2, 66, 34, 98, 18, 82, 50, 114, 10, 74, 42, 106, 26, 90, 58, 122,
  6, 70, 38, 102, 22, 86, 54, 118, 14, 78, 46, 110, 30, 94, 62, 126,
  1, 65, 33, 97, 17, 81, 49, 113, 9, 73, 41, 105, 25, 89, 57, 121,
  5, 69, 37, 101, 21, 85, 53, 117, 13, 77, 45, 109, 29, 93, 61, 125,
  3, 67, 35, 99, 19, 83, 51, 115, 11, 75, 43, 107, 27, 91, 59, 123,
  7, 71, 39, 103, 23, 87, 55, 119, 15, 79, 47, 111, 31, 95, 63, 127
};

void init_ntt() {
  unsigned int i;
  int16_t tmp[128];

  tmp[0] = MONT;
  for(i=1;i<128;i++)
    tmp[i] = fqmul(tmp[i-1],MONT*KYBER_ROOT_OF_UNITY % KYBER_Q);

  for(i=0;i<128;i++) {
    zetas[i] = tmp[tree[i]];
    if(zetas[i] > KYBER_Q/2)
      zetas[i] -= KYBER_Q;
    if(zetas[i] < -KYBER_Q/2)
      zetas[i] += KYBER_Q;
  }
}
*/

Answer 1

If the prime is $p=1073692673,$ then the nonzero elements of the field $\mathbb{F}_p$ form a multiplicative group of order $$p-1=1073692672=2^{14}\cdot13\cdot71.$$

The roots of unity in this field have orders dividing $p-1$ so for example you could get an element of full order by randomly testing small integers and raising to the divisors of $p-1$. Once you get $\zeta$ of full order, then $\alpha=\zeta^u$ has order $(p-1)/u,$ whenever $u\mid p-1.$

See also this question for more specific details.