при полном периоде, за исключением больших d. Большие значения d соответствуют низкому потенциалу. (Уже известно, что генераторы с низким потенциалом нежелательны).

Следующая теорема дает более точные условия выбора а и с. Рассмотрим критерий сериальной корреляции, применяемый на полно.м периоде. Величина С, определенная в разделе 3.3.2 (формула (23)), равна

0<з;<га 0<х<т / V 0<х<т 0<з;<т

Пусть х - такой элемент, что s{x) = 0. Тогда

.(x)=m(())4.f[x.]. (15)

Формулы, которые необходимо получить, лучше всего выразить с помощью суммы

.,M..) = .2E((i))(()). (-)

0<j<k

важной функции, возникающей в некоторых математических задачах. Ее называют обобщенной суммой Дедекинда, так как Ричард Дедекинд (Dedekind) ввел функцию a{h, к, 0) в 1876 году, когда комментировал неоконченную рукопись Римана. [См. работу В. Riemann, Gesammelte math. Werke, 2nd ed. (1892), 466-478.] Используя достаточно известные формулы

Em(m-l) 2 m(m-i)(m-l)

и y: -3-

0<x<ra 0<x<TT!

можно легко преобразовать (14) в

т.а{а,т,с)-3 + 6{т.-х -с) - 1

(см. упр. 5). Так как т обычно очень большое, можно отбросить члены порядка 1/т и получить приближенную формулу

С « <7(a,m,c)/m (18)

с погрешностью по абсолютной величине, меньшей, чем 6/т.

Критерий сериальной корреляции сейчас сводится к определению значения суммы Дедекинда а{а, т, с). Вычислять а{а, т, с) непосредственно из определения (16) не легче непосредственного вычисления коэффициента корреляции, но, к счастью, существуют простые методы быстрого подсчета сумм Дедекинда.

Лемма В ("Закон взаимности" для сумм Дедекинда). Пусть h, к и с - целые числа. Если 0<с<к,0<Н<ки если Ник - взаимно простые числа, то

c,(h,k,c)o(k,h,c) = lll-6

-Se(h,c), (19)

e(/i,c) = [c = 0] + [cmod/i70]. (20)

Доказательство. Оставляем читателю доказательство того, что при наших предположениях имеет место равенство

6с с

a{h,к,с) + о{к,h,с) = a{h,к,0) + а{к, h,0) + -г-г - Q г

flrC L.tl.

-3e(/i,c) + 3 (21)

(см. упр. 6). Теперь докажем лемму только для с = 0.

Приведенное ниже доказательство, в котором используются комплексные корни из единицы, по существу, принадлежит Л. Карлицу (L. Carlitz). Это действительно более простое доказательство, чем доказательство с использованием элементарных преобразований сумм (см. упр. 7), но для следующего метода необходимо больше математических понятий, чем требуется обычно для задач такого типа, поэтому он более поучителен.

Пусть f{x) и д{х) - полиномы, определенные следующим образом:

fix) = 1 + х + --- + х- = (х* - 1)/{х - 1),

д{х)=х + 2х + --- + {к-1)х- (22)

= xfix) = fcxV(x - 1) - х(х= - 1)/(х - 1)2.

Если 6J - комплексный к-й корень из единицы е, то из формул 1.2.9-(13) получим

giiх) = rx если О < г < fc. (23)

0<j«:

Положим X = 1, тогда g{ujx) = k/{uj - 1), если j ф О, иначе это выражение равно fc(fc - 1)/2. Поэтому

г mod fc = ---h(fc -1), если г целое.

o<j<k ~

(Равенство (23) показывает, что правая часть равна г, когда О < г < fc, и она не изменяется при прибавлении к г числа, кратного fc.) Следовательно,

Эта важная формула, которая справедлива для всех целых г, позволяет свести .многие вычисления, включающие {{г/к)), к суммам, содержащим fc-й корень единицы. Она предоставляет новые возможности для вычислений. В частности, получим следующую формулу, когда h 1 к:

0<r<fc 0<i<fc 0<j<<:

Правая ее часть может быть упрощена, если просуммировать ее по г. Получим Io<r<fc" = f{uj) - О, если smodfc ф 0. Равенство (25) сведется к

Аналогичная формула получена для а{к, h,0) с ( = е/ вместо ш.

Не ясно, что делать с суммой (26), однако существует элегантный метод ее преобразования, основанный на том факте, что каждый член суммы является функцией от ш, где О < j < fc. Следовательно, суммы, в сущности, берутся по fc-м корням из единицы, отличным от 1. Когда xi, Х2, ..., Хп - различные комплексные числа, получаем равенство

У" I

1 {3 -Xl)... (xj - Xj-i){x - Xj){Xj - Xj+i) ...{xj- Xn)

= ix-xi)...{x-x„)

которое можно вывести в результате применения обычного метода разложения на элементарные дроби в правой части этого равенства. Кроме того, если q{x) = {х - yi){x - Уг)... (а; - Ут), справедливо

9iyj) = {yj - yi) • • • (yj - Уз-1){Уз - Уз+t) • (Уз " УшУ, (28)

это тождество часто используется для упрощения выражений, подобных левой части (27). Когда Ник - взаимно простые, все числа ..., С, С, • • • > С" различны. Поэтому можно рассмотреть формулу (27) в частном случае для полинома {х-ш)... (a;-w*-)(ж-C). •. {x-C~) = {х - l){x - 1)/{х - 1), получив следующее тождество для х:

1 С(С-1) 1 изНш-1) {х-1)

*о/.(*-1)(-) (х-1)(х*-1)

Оно имеет много интересных следствий и позволяет получить многочисленные формулы для сумм наподобие (26). Например, если (29) дважды продифференцировать по а; и устремить а; - 1, получится

2 j4£jz})l ,2 у. uj{uj - l)

~ 6\к h hk) 2 2h 2fc"

Заменим j на /i - j и на fc - j в этой сумме и используем (26), чтобы получить равенство

lfh к 1 \ 1 1 1

~ eU /I /ifcy 2 2h 2fc

эквивалентное желаемому результату.

Лемма В дает явно заданную функцию f{h,k,c), такую, что

<T{h,k,c) = f{h,k,c)-(7{k,h,c), (30)

какими бы ни были взаимно простые числа /i и fc, такие, что 0</i<fc, 0<c<fc. Из определения (16) следует, что

(T(fc,/i, с) = cr(fcmod/i,/i, cmod/i). (31)