@bozedai

Какие существуют практические примеры применения арифметики колец и полей?

Всем привет! Сейчас изучаю алгебру, а конкретно конечные поля и кольца. И все примеры и упражнения абстрактные. А какие существуют практические применения этих арифметик? В школе вот все задачи были про поезда или пироги, а здесь есть такие?
  • Вопрос задан
  • 179 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Математика
Разработчик на С++, экс-олимпиадник.
В криптографии просто куча применений. Всякие RSA, DH, эллиптические кривые - это все основано на свойствах некоторых особых конечных полей.

Но мне нравится такой пазл: есть таблица из лампочек-кнопок n x m. Какие-то горят, какие-то - нет. Можно нажать на какую-то лампочку и она переключится. Но вместе с ней переключатся и 4 соседние лампы (если нажали на угловую кнопку - то только 2). Нужно погасить все лампы за минимальное количество нажатий. Как ее вообще решать без полного или частичного перебора? Важно заметить, что 2 раза нажимать на лампу бессмысленно, потому что эти 2 нажатия просто отменят друг друга. Еще не важно, в каком порядке нажимать на лампы. Конечный результат будет одинаковый.

А дальше, подключается математика! Введем переменные x_ij - сколько раз мы нажимаем на лампочку в позиции i, j. Эти переменные - это элементы поля по модулю 2. Потому что 2 раза нажать на кнопку - то же самое, что и 0 раз нажать. Составляем линейные уравнения, что сумма нажатий на все кнопки, влияющие на данную лампу - дает 0 или 1 по модулю 2 (в зависимости от того, горит ли эта лампа изначально).

А дальше эту систему уравнений можно просто решать методом гаусса. Почему? Ведь он работает с вещественными числами? Но нет! Гауссу по-фигу над каким полем работать. Делаем все вычисления по модулю 2 - и получим решение в виде 0 и 1 для всех переменных.

Поля по модулю простых чисел еще можно, например, использовать для реализации быстрого преобразования фурье для быстрого умножения длинных чисел без использования операций с float, что требуется в стандартной реализации (она вообще с комплексными числами работает). И такая реализация быстрее и точнее.
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
uvelichitel
@uvelichitel
habrahabr.ru/users/uvelichitel
Криптография. Биткоин строится на арифметике эллиптических кривых над конечными полями.
Ответ написан
Griboks
@Griboks
У абстракций подобного уровня нет практических применений, но они позволяют упростить более простые задачи. Стандартное применение на практике выглядит так:
1. Рассматриваем практическую систему чисел.
2. Доказывает, что она является группой.
3. Теперь мы можем использовать готовые свойства и формулы для нашей конкретной системы чисел. Т. е. мы пропустили несколько десятков страниц формул для нашей задачи.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы