Вопрос по полю Галуа

@Lampard7 · Регистрация: 13.05.2009

Студворк — интернет-сервис помощи студентам

Здравствуйте.Созрел вопрос по конечному полю - полю Галуа.Разъясните пож-та как находится обратный элемент в поле GF (2⁸) ?????
По моему представлению a*a^-1=1 mod p (в нашем случае 2).Так вот по прикидкам,число 5 будет иметь обратное и 5 и 7 и бог знает еще сколько,ведь остаток от деления числа а и обратного = 1.
Объясните пож-та что к чему здесь.

@Lampard7 · 20.04.2012, 20:31 **[ТС]**

А как это у Вас получилось?? Я на калькуляторе и в hex и в бинарном виде умножаю.Получается вот -
100000101111110. Это первый вопрос.
Второй : как у них получается что (11111101111110 mod 100011011) = 1 ??? Этот остаток = 123 если проделать эту операцию в калькуляторе

@Buckminster · 20.04.2012, 21:26

сложение выполняется поразрядно по модулю 2:

11 + 01 = 12 = 10 (т.е. [1 1] + [0 1] = [1 2] = [1 0] mod 2)...

деление чисел сводится к вычитанию, а оно над PG(2) совпадает со сложением:

1011 : 110 ⇒ 1011 + 1100 = 0111 ⇒ 111 + 110 = 001 — остаток...

операция сдвига выполняется над восьмиразрядными числами:

(192 = 0xC0 = 1100 0000) shl << 1 = (1000 0000 = 0x80 = 128)...

по этой же причине достаточно добавить к результату только 0x1b (а не 0x11b)...

@Lampard7 · 20.04.2012, 21:56 **[ТС]**

Сообщение от Buckminster

сложение выполняется поразрядно по модулю 2:

11 + 01 = 12 = 10 (т.е. [1 1] + [0 1] = [1 2] = [1 0] mod 2)...

Вы имеете ввиду при сложении "столбиком" ?? Вы же говорите поразрядно.А там при сложении есть только 0 и 1.Как там появится 2 то??

Сообщение от Buckminster

деление чисел сводится к вычитанию, а оно над PG(2) совпадает со сложением:

1011 : 110 ⇒ 1011 + 1100 = 0111 ⇒ 111 + 110 = 001 — остаток...

операция сдвига выполняется над восьмиразрядными числами:

(192 = 0xC0 = 1100 0000) shl << 1 = (1000 0000 = 0x80 = 128)...

по этой же причине достаточно добавить к результату только 0x1b (а не 0x11b)...

Что-то я не понял как это Вы поделили 1011 на 110.1011+1100 дает 10111,а не 0111.И зачем Вы 111 плюсуете к 110???
Можете показать как находится вот это 11111101111110 mod 100011011 ??? Пошагово если можно

Добавлено через 14 минут
Насчет сложения поразрядно все понял.Берем таблицу истинности XOR и поразрядно плюсуем 0 и 1.
А вот по поводу этого чертового деления не пойму.

@Buckminster · 20.04.2012, 22:01

складываются не двоичные числа, а вектора, поэтому переноса разрядов нету:

1 + 1 = 2 = 0 mod 2; [1 1] + [1 0] = [2 1] = [0 1] mod 2

т.е. сложение — это побитовая операция XOR (даже "столбиком")...

поэтому 1011 + 1100 = 2111 = 0111

для нахождения остатка от деления достаточно поразрядно прибавлять к делимому сдвинутый на необходимое количество разрядов влево делитель...

Сообщение от Lampard7

Берем таблицу истинности XOR и поразрядно плюсуем 0 и 1

именно...

@Lampard7 · 20.04.2012, 22:12 **[ТС]**

Сообщение от Buckminster

для нахождения остатка от деления достаточно поразрядно прибавлять к делимому сдвинутый на необходимое количество разрядов влево делитель...

Тоесть вот так?? :
11111101111110
10001101100000
----------------
где красным добавленные биты сдвига
Но у нас же не получится 1 в данном случае

@Buckminster · 20.04.2012, 22:24

Сообщение от Lampard7

Тоесть вот так?? :
11111101111110
10001101100000
----------------
где красным добавленные биты сдвига

да...

Сообщение от Lampard7

Но у нас же не получится 1 в данном случае

к полученному результату снова прибавляем делитель, сдвинутый влево уже на разряд меньше, и т.д.

@Lampard7 · 20.04.2012, 22:40 **[ТС]**

О господи.А другого пути нету?? Поменьше

Добавлено через 14 минут

Сообщение от Buckminster

да...
к полученному результату снова прибавляем делитель, сдвинутый влево уже на разряд меньше, и т.д.

Вот что получилось :
11111101111110
10001101100000
--------------
1110000011110
1000110110000
-------------
110110101110
100011011000
-------------
10101110110
10001101100
-----------
0100011010
1000110110
-----------
1100101100
0100011011
----------
1000110111
Красным конечный результат.Что дальше делать??

@Buckminster · 20.04.2012, 22:41

Не по теме:

т.е. нету ли царского пути в геометрию? :)

это пример ведь подробно расписан по приведённой выше ссылке

@Lampard7 · 20.04.2012, 22:50 **[ТС]**

Сообщение от Buckminster

Не по теме:

т.е. нету ли царского пути в геометрию? :)

это пример ведь подробно расписан по приведённой выше ссылке

Бог мой.А я думаю что это они там нарисовали.Скажите,а почему они проскакивают один этап (помечено красным)?? Вместо того,чтоб XORить 1000110110,они почему-то пропускают его и сразу XORят само число

11111101111110 (mod) 100011011
10001101100000
1110000011110
1000110110000
110110101110
100011011000
10101110110
10001101100
0100011010
000000000
100011010
100011011
00000001

@Buckminster · 20.04.2012, 22:51

Сообщение от Lampard7

а почему они проскакивают один этап

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

@Lampard7 · 20.04.2012, 23:02 **[ТС]**

Наконец-то все ясно и понятно.Но все равно программная реализация это будет

Тот код,что Вы показывали там я так понял нахождение остатка реализовано не как тут - XORя делитель,а как-то по другому ???

@Buckminster · 21.04.2012, 11:43

всё именно так:

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
gf.xtime = function(b) {
    var highbit = b & 0x80
    var shl = (b << 1) & 0xff
    return highbit == 0 ? shl : shl ^ 0x1b  
}
 
gf.mul = function(b1, b2) {
    var t = [b1]
    var r = 0
    
    for (var i = 1; i < 8; i++)
        t[i] = gf.xtime(t[i - 1])
    
    for (var i = 0; i < 8; i++) 
        if (b2 & (1 << i))
            r ^= t[i]   
    
    return r
}
 
gf.inv = function(b) {
    for (var i = 0; i < 256; i++)
        if (gf.mul(i, b) == 1)
            return i    
}

только вычитание применяется не к сумме, а к самим слагаемым...

Новые блоги и статьи Все статьи Все блоги /
Копировать Windows на новый диск на UEFI damix 17.10.2026 https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .

@Lampard7 4 / 4 / 0 Регистрация: 13.05.2009 Сообщений: 106

	Вопрос по полю Галуа 17.04.2012, 22:03. Показов 24142. Ответов 51 Метки нет (Все метки) Здравствуйте.Созрел вопрос по конечному полю - полю Галуа.Разъясните пож-та как находится обратный элемент в поле GF (2⁸) ????? По моему представлению a*a^-1=1 mod p (в нашем случае 2).Так вот по прикидкам,число 5 будет иметь обратное и 5 и 7 и бог знает еще сколько,ведь остаток от деления числа а и обратного = 1. Объясните пож-та что к чему здесь. 0

@Lampard7 4 / 4 / 0 Регистрация: 13.05.2009 Сообщений: 106
	20.04.2012, 20:31 [ТС]
	А как это у Вас получилось?? Я на калькуляторе и в hex и в бинарном виде умножаю.Получается вот - 100000101111110. Это первый вопрос. Второй : как у них получается что (11111101111110 mod 100011011) = 1 ??? Этот остаток = 123 если проделать эту операцию в калькуляторе 0

@Buckminster 1032 / 703 / 66 Регистрация: 30.01.2012 Сообщений: 714
	20.04.2012, 21:26
	сложение выполняется поразрядно по модулю 2: 11 + 01 = 12 = 10 (т.е. [1 1] + [0 1] = [1 2] = [1 0] mod 2)... деление чисел сводится к вычитанию, а оно над PG(2) совпадает со сложением: 1011 : 110 ⇒ 1011 + 1100 = 0111 ⇒ 111 + 110 = 001 — остаток... операция сдвига выполняется над восьмиразрядными числами: (192 = 0xC0 = 1100 0000) shl << 1 = (1000 0000 = 0x80 = 128)... по этой же причине достаточно добавить к результату только 0x1b (а не 0x11b)... 0

@Buckminster 1032 / 703 / 66 Регистрация: 30.01.2012 Сообщений: 714
	20.04.2012, 22:41
	Не по теме: т.е. нету ли царского пути в геометрию? :) это пример ведь подробно расписан по приведённой выше ссылке 0

@Lampard7 4 / 4 / 0 Регистрация: 13.05.2009 Сообщений: 106
	20.04.2012, 23:02 [ТС]
	Наконец-то все ясно и понятно.Но все равно программная реализация это будет Тот код,что Вы показывали там я так понял нахождение остатка реализовано не как тут - XORя делитель,а как-то по другому ??? Изображения 0