В этой программе мы будем работать с fields (“конечное поле” или “поле Галуа”). Будем вычислять количество степеней двойки в простой факторизации входного числа “n”.
Для начала разберёмся, что такое “конечное поле”.
Это поле, состоящее из конечного числа элементов. Конечные поля получили широчайшее применение в криптографии. Главной работой в этой области считается статья Диффи и Хелмана по криптографии с открытым ключом, в которой был предложен протокол обмена ключами, в этом проекте использовались конечные поля определённого вида. Позже появилось множество криптопротоколов и сетей, основанных на применении конечных полей.
Для большего понимания о том, как можно проводить вычисления в конечных полях, можете прочитать учебно-методическое пособие.
Поля хорошо сочетаются с ограничивающими системами. Один из способов использования полей — вместо целых чисел для арифметики (это не всегда имеет смысл — зависит от конкретного случая). Такие программы будут создавать меньше ограничений, их дешевле запускать и проверять.
Непосредственно код:
Здесь мы принимаем field из файла inputs:
Это поле и подлежит дальнейшему анализу (является параметром в main)
В самом начале main мы создаём дубликат поля “n” и устанавливаем счётчик со значением 0.
Поскольку поле ints (7 строчка) имеет 253 бита или меньше, любое число в поле будет иметь не более 252 степеней двойки в своей простой факторизации.
В 8 строчке стоит проверка:
Мы определяем предикат is_even для полей следующим образом.
- Если n четное и ненулевое, то очевидно, что n/2 < n.
- Если n нечетно, то n-p — четное отрицательное число, эквивалентное полю, и
(n-p)/2 — эквивалентное полю отрицательное число ближе к 0, большее, чем n-p. - Если мы прибавим p к обоим этим отрицательным числам, то получим n/2 = (n-p)/2 + p = (n+p)/2 больше n и всё ещё меньше p.
Если проверка проходит, мы делим поле на степень двойки и обновляем счётчик.
Если программа составлена правильно, (из 13 строки) получим ответ:
