NTT(快速数论变换)用到的各种素数及原根
| NTT(快速数论变换)用到的各种素数及原根 |
|
|
|
| g是mod(r * 2 ^ k + 1)的原根 |
|
|
|
| r * 2 ^ k + 1 |
r |
k |
g |
| 3 |
1 |
1 |
2 |
| 5 |
1 |
2 |
2 |
| 17 |
1 |
4 |
3 |
| 97 |
3 |
5 |
5 |
| 193 |
3 |
6 |
5 |
| 257 |
1 |
8 |
3 |
| 7681 |
15 |
9 |
17 |
| 12289 |
3 |
12 |
11 |
| 40961 |
5 |
13 |
3 |
| 65537 |
1 |
16 |
3 |
| 786433 |
3 |
18 |
10 |
| 5767169 |
11 |
19 |
3 |
| 7340033 |
7 |
20 |
3 |
| 23068673 |
11 |
21 |
3 |
| 104857601 |
25 |
22 |
3 |
| 167772161 |
5 |
25 |
3 |
| 469762049 |
7 |
26 |
3 |
| 985661441 |
235 |
22 |
3 |
| 998244353 |
119 |
23 |
3 |
| 1004535809 |
479 |
21 |
3 |
| 2013265921 |
15 |
27 |
31 |
| 2281701377 |
17 |
27 |
3 |
| 3221225473 |
3 |
30 |
5 |
| 75161927681 |
35 |
31 |
3 |
| 77309411329 |
9 |
33 |
7 |
| 206158430209 |
3 |
36 |
22 |
| 2061584302081 |
15 |
37 |
7 |
| 2748779069441 |
5 |
39 |
3 |
| 6597069766657 |
3 |
41 |
5 |
| 39582418599937 |
9 |
42 |
5 |
| 79164837199873 |
9 |
43 |
5 |
| 263882790666241 |
15 |
44 |
7 |
| 1231453023109120 |
35 |
45 |
3 |
| 1337006139375610 |
19 |
46 |
3 |
| 3799912185593850 |
27 |
47 |
5 |
| 4222124650659840 |
15 |
48 |
19 |
| 7881299347898360 |
7 |
50 |
6 |
| 31525197391593400 |
7 |
52 |
3 |
| 180143985094819000 |
5 |
55 |
6 |
| 1945555039024050000 |
27 |
56 |
5 |
| 4179340454199820000 |
29 |
57 |
3 |
原文地址：https://www.cnblogs.com/artoriax/p/12246066.html