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

 Всем привет! Сейчас изучаю алгебру, а конкретно конечные поля и кольца. И все примеры и упражнения абстрактные. А какие существуют практические применения этих арифметик? В школе вот все задачи были про поезда или пироги, а здесь есть такие? 

 В криптографии просто куча применений. Всякие RSA, DH, эллиптические кривые - это все основано на свойствах некоторых особых конечных полей.  

  

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

  

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

  

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

  

Поля по модулю простых чисел еще можно, например, использовать для реализации быстрого преобразования фурье для быстрого умножения длинных чисел без использования операций с float, что требуется в стандартной реализации (она вообще с комплексными числами работает). И такая реализация быстрее и точнее. 

 У абстракций подобного уровня нет практических применений, но они позволяют упростить более простые задачи. Стандартное применение на практике выглядит так:  

1. Рассматриваем практическую систему чисел.  

2. Доказывает, что она является группой.  

3. Теперь мы можем использовать готовые свойства и формулы для нашей конкретной системы чисел. Т. е. мы пропустили несколько десятков страниц формул для нашей задачи. 

 Криптография. Биткоин строится на арифметике эллиптических кривых над конечными полями.