спектральный тест состоит из сравнения длины кратчайшего вектора в решетке, связанной с линейный конгруэнтный генератор с множителем $а$ и модуль $м$ максимально возможной длины кратчайшего вектора в любой решетке той же размерности.
В частности, показатель качества спектрального теста степени $д$ состоит из
$$
\frac{\nu_d}{\gamma_d^{1/2}m^{1/d}}\,,
$$
куда $\nu_d$ это $L_2$ норма кратчайшего вектора решетки, порожденной строками
$$
\begin{pматрица}
m&0&0&\dots&0\
а&1&0&\точки&0\
^ 2&0&1&\точки&0\
&&\точки&\
a^{d-1}&0&0&\dots&1
\end{pmatrix},
$$
и $\gamma_d$ является постоянная Эрмита для измерения $д$, или его приближение. Поскольку определитель этой решетки равен $м$, срок $\gamma_d^{1/2}м^{1/d}$ является точной верхней границей кратчайшего вектора для решетки размерности $д$. (Примечание: показатель качества, если степень $д$ обычно определяется как минимум всех баллов из $2$ вплоть до $д$; Я игнорирую это здесь для простоты).
Вычисление точного среднего значения этого показателя кажется довольно трудным. Однако мы можем немного ослабить проблему и сделать вид, что решетки вышеуказанного вида могут быть смоделированы как случайные решетки, и в этом случае мы можем использовать Гауссова эвристика и аппроксимировать ожидаемое значение кратчайшего вектора в размерности $д$ как
$$
\left(\frac{\pi^{d/2}}{\Gamma(1+d/2)}\right)^{-1/d} m^{1/d}\,,
$$
из которого мы можем получить средний балл спектрального теста для размерности $д$ как
$$
\frac{ \left(\frac{\pi ^{d/2}}{\Gamma(1+d/2)}\right)^{-1/d} }{\gamma_d^{1/2}} \,.
$$
Ниже приведены соответствующие приближения для размеров $2$ к $8$, где постоянная Эрмита известна точно. Обратите внимание, что мы совершаем здесь как минимум два греха:
- Обработка правильно структурированных решеток как решеток со случайной выборкой;
- Использование асимптотических приближений при довольно низких размерностях, что может быть не слишком точным.
| $д$ |
$\mathbf{E}\left[\frac{\nu_d}{\gamma_d^{1/2}m^{1/d}}\right]$ |
| 2 |
0.525 |
| 3 |
0.552 |
| 4 |
0.564 |
| 5 |
0.583 |
| 6 |
0.589 |
| 7 |
0.595 |
| 8 |
0.593 |
Как ни странно, оценка, определенная Кнутом (том 2, §3.3.4),
$$
\mu_d = \frac{\pi^{d/2}\nu_d^d}{(d/2)! м}\,,
$$
сравнивает структуру решетки LCG с этим ожидаемым средним значением, но с другим масштабированием. Согласно Кнуту, $\mu_d\ge 1$ является хорошей оценкой, означающей, что решетка LCG ведет себя как случайная решетка.
