Отправлено andy_P 29 августа 2005 г. 16:34 В ответ на: Псевдослучайные последовательности: подскажите пожалуйста как вычисляется число М-последовательностей в ансамбле отправлено <font color=gray>seryoga</font> 29 августа 2005 г. 15:36

Размер ансамбля определяется кол-вом примитивных полиномов в поле GF(2) заданной длины и равно phi(N)/k. N -длина последовательности, N = 2^k-1, phi(N) -функция Эйлера (кол-во чисел меньших чем N и взаимно простых с N). Если N - простое, то phi(N) = N-1.

Это легко сообразить:

Любое взаимно простое число будучи представленным в двоичном виде сответствует примитивному полиному (регистр пробегает все возможные значения за N тактов). k циклических сдвигов полинома генерируют одну и ту же последовательность, те размер ансамбля - phi(N)/k.

• А если N не простое, то fi(N) вот эдак:-) — -=ВН=-   (31.08.2005 11:54 194.190.181.231, 202 байт)
• а метод представления простого числа в виде примитивного полинома не продемонстрируете? — yes   (30.08.2005 12:17 194.133.69.2, 24 байт)
  • Ответ: напишите его по битам. Получите полином над полем GF(2) — andy_P   (30.08.2005 13:19 80.82.63.185, пустое)
    • вот полиномы этого поля, каким числам они соответствуют? — yes   (30.08.2005 13:54 194.133.69.2, 171 байт)
      • Нет связи между простыми числами и примитивными полиномами в GF(2). — 729   (30.08.2005 19:52 80.253.9.6, пустое)
        • я знаю. но множества изоморфны(? или как это называется по науке) поэтому есть однозначное соответствие — yes   (31.08.2005 08:38 194.133.69.2, 78 байт)
          • В догонку - множество целых чисел полем не является. — 729   (31.08.2005 12:11 80.253.9.6, пустое)
            • ну естествено рассматривается множество целых по модулю (конечное) — yes   (31.08.2005 13:55 194.133.69.2, 67 байт)
              • Не будет: 1/А (А - целое) множеству целых не принадлежит. — 729   (31.08.2005 14:29 80.253.9.6, пустое)
                • деление - операция обратная умножению : 1/b=a, значит a*b=1 - например 2*4=1(mod 7) - 1/4=2, 1/2=4 — yes   (31.08.2005 16:40 194.133.69.2, пустое)
                • Ответ: Деление по модулю вроде бы определяется как инверсия умножения? — andy_P   (31.08.2005 14:50 80.82.63.185, пустое)
                  • Вы же поле определили, как GF(2). Модуль единственный и равен 2. — 729   (31.08.2005 15:05 80.253.9.6, пустое)
                    • а какие в этом поле полиномы? там только 2 элемента {0,1}. разговор про расширение поля GF(2^N) — yes   (31.08.2005 16:54 194.133.69.2, пустое)
                      • Полиномы любой степени можно считать в GF(2), генераторы ПСП на сдвиговых регистрах этим и занимаются. — 729   (31.08.2005 17:09 80.253.9.6, пустое)
                    • Ответ: Я про сравнение GF(2^n) и Z(2^n). — andy_P   (31.08.2005 15:08 80.82.63.185, пустое)
                      • В этом случае возвращаемся к вопросу yes (+) — 729   (31.08.2005 16:41 80.253.9.6, 348 байт)
                        • ОЧЕВИДНО, что соответствие не бинарное, но если рассматривать алгебру — yes   (31.08.2005 16:49 194.133.69.2, 183 байт)
                          • Соответствие-то установить можно, только теперь надо переопределить понятие простого числа (+) — 729   (31.08.2005 16:59 80.253.9.6, 200 байт)
                            • Ответ: Вот это точно :-(. Формула верная, это точно. Но почему тогда так ??? — andy_P   (31.08.2005 17:04 80.82.63.185, пустое)
                              • Скорее всего, что число простых чисел степени не больше N и число примитивных полиномов той же степени равны. Но почему, не знаю. — 729   (31.08.2005 17:07 80.253.9.6, пустое)
                                • Есть еще одна аналогия, но как за нее зацепиться непонятно+ — andy_P   (31.08.2005 17:19 80.82.63.185, 212 байт)
                          • Ответ: Похоже я въехал - Z(2^N) не является даже кольцом. Попробовал перебрать все элементы (для 2^5) и не получил мультипликативной группы. Для того, чтобы Z(N) было кольцом требуется, чтобы N было простым числом. — andy_P   (31.08.2005 16:55 80.82.63.185, пустое)
                            • с методом определения GF(2^N) на полиномах тоже фигурирует (x^N-1) -у меня здесь какой-то пробел в знаниях :) — yes   (31.08.2005 17:13 194.133.69.2, 85 байт)
                              • Ответ: Запостил про эту связь выше — andy_P   (31.08.2005 17:20 80.82.63.185, пустое)
                          • но чего-то кажется мне, что Z(2^N) и GF(2^N) не изоморфны — yes   (31.08.2005 16:52 194.133.69.2, пустое)
                            • Мне тоже так кажется, уж больно соответствие кривое получается. — 729   (31.08.2005 17:00 80.253.9.6, пустое)
                • Ответ: А вроде, если модуль простой то получим поле, иначе - кольцо? — andy_P   (31.08.2005 14:48 80.82.63.185, пустое)
                  • вроде так. при этом подгруппы (смежные классы) вроде поля. — yes   (31.08.2005 16:44 194.133.69.2, пустое)
          • Есть только подобие, но не соответствие. Множества даже разные, арифметика разная. В Вашем примере есть число 55, явно не простое, а полином примитевный. — 729   (31.08.2005 12:10 80.253.9.6, пустое)
            • Z(256) и GF(2^8) не подобные? арифметика может и разная, алгебра одинаковая — yes   (31.08.2005 13:52 194.133.69.2, пустое)
              • См. ответ выше. — 729   (31.08.2005 14:30 80.253.9.6, пустое)
  • Ответ: напишите его по битам. — andy_P   (30.08.2005 13:18 80.82.63.185, пустое)
• А что такое числа ВЗАИМНО простые с N? — seryoga   (30.08.2005 08:21 213.210.76.2, пустое)
  • Ответ: + — andy_P   (30.08.2005 09:58 80.82.63.185, 81 байт)
    • Спасибо за подсказку — seryoga   (30.08.2005 10:50 213.210.76.2, пустое)
• а не так phi(N) = (N-1)/2? — Victor®   (29.08.2005 19:31 212.67.84.229, пустое)
  • Ответ: - нет, не так. Подставьте в Вашу формулу простое чило N. Все чилса, меньшие чем N, будут с ним взаимно простыми, а Ваша формула говорит, что взаимно простыми с ним будет только половина чисел. — andy_P   (30.08.2005 10:01 80.82.63.185, пустое)