2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 
Сообщение18.10.2008, 14:12 
Модератор
Аватара пользователя


11/01/06
5660
вздымщик Цыпа писал(а):
Цитата:
Пусть $N=2^n$, рассмотрим $F=F(2^n)$ - поле из $2^n$ элементов. Утвержается, что в этом случае можно взять $M=N$.
То, что $F$ не является полем — это мелкий огрех, в дальнейшем не используется.

Что значит не является?! Конечное поле из $N=2^n$ элементов существует - его-то здесь и обозначают буквой $F$.
И тот факт, что это поле характеристики 2, еще как используется! См. ниже.

вздымщик Цыпа писал(а):
Цитата:
Элис и Боб каждой карточке (в порядке их следования) присваивают свой уникальный элемент $F: f_1, ..., f_N$.
Ничего не сказано, о том, что это за элементы, видимо произвольные.

Да, это произвольный (но фиксированный) порядок элементов поля.

вздымщик Цыпа писал(а):
Цитата:
Пусть зрители загадали число $k$ из $[1,N]$ и выложили карточки некоторым образом. Элис вычисляет сумму $B = \sum c(i)*f_i$, где $c(i)=0$ или $1$ - цвет $i$-ой карточки, и затем решает уравнение $B + X = f_k$ относительно $X$. Очевидно, что найдется такой индекс $j$, что $X=f_j$. Элис переворачивай $j$-ю карточку.
Это «очевидно» очевидно неверно. Если $X=f_j$, то $B = f_k - f_j$. Вариантов разностей $f_k - f_j$ не более $N^2$, а вариантов $B$$2^N$. Следовательно, решение будет далеко не всегда.

Во-первых, линейное уравнение $B + X = f_k$ в поле всегда разрешимо - его решение $X=B+f_k$ (напоминаю, что дело происходит в поле характеристики 2: плюс и минус здесь - это одна и та же операция).
Во-вторых, индекс $j$ такой, что $X=f_j$ найдется просто потому, что $f_1,f_2,\dots,f_N$ - это все элементы поля, и $X$ как элемент поля обязан быть одним из них.

Таким образом, Элис выбирает $j$ так, что выполняется соотношение: $B+f_j = f_k$ (как впрочем, и соотношение $B+f_k = f_j$).

вздымщик Цыпа писал(а):
Цитата:
Входит Боб, вычисляет ту же сумму $B' = \sum c'(i)*f_i$ и находит такое $k$, что $B'=f_k$. Это $k$ и есть загаданное зрителями число. Все.
Ну и в довершение такой $k$ вовсе необязательно будет. Хотя уже предыдущего пункта достаточно, чтоб дальше не читать.

Так как перевернута была карточка с номером $j$, то суммы вычисленные Элис и Бобом будут отличаться в точности на $f_j$. Поэтому $B'=B+f_j=f_k$ (согласно выбору $f_j$ - см. выше), где $k$ - это то самое загаданное число.

 Профиль  
                  
 
 
Сообщение18.10.2008, 14:28 


12/09/08

2262
maxal в сообщении #151534 писал(а):
Что значит не является?! Конечное поле из $2^N$ элементов существует - его-то здесь и обозначают буквой $F$.
И тот факт, что это поле характеристики 2, еще как используется! См. ниже.
Мнда, мой минус раз. (только, не $2^N$ элементов, а $N=2^n$ элементов)
maxal в сообщении #151534 писал(а):
Во-первых, линейное уравнение $B + X = f_k$ в поле всегда разрешимо - его решение $X=B+f_k$ (напоминаю, что дело происходит в поле характеристики 2).
Во-вторых, индекс $j$ такой, что $X=f_j$ найдется просто потому, что $f_1,f_2,\dots,f_N$ - это все элементы поля, и $X$ как элемент поля обязан быть одним из них.
Мой минус два. Постоянно в голове путаются $N=2^n$ и $2^N$ :(

Сознаюсь, наврал.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 17 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group