Десять часов, вы ждёте пять, и становится три. Не пятнадцать. Никто не считает это странным, никто не должен был учить новое правило, и все делают этот расчёт с детства. Это именно та арифметика, в которой работает Bitcoin, от первого до последнего вычисления, и она имеет название: модульная арифметика.
Конечное поле — это множество с конечным количеством элементов, в котором четыре арифметические операции работают и никогда не производят ничего вне этого множества. В случае с Bitcoin, элементами являются целые числа от нуля до p минус один, и правило простое: делайте расчёт, как всегда, и оставьте остаток от деления на p.
Сложение, вычитание и умножение не представляют загадки. В поле с модулем 7, пять плюс четыре равно два, потому что девять делённое на семь оставляет остаток два. Три умножить на пять равно одному, потому что пятнадцать оставляет остаток один. Вычитание — это сложение противоположного: минус три то же самое, что четыре, так как три плюс четыре замыкают полный круг.
Деление требует новой идеи, и это самая важная идея урока. В конечном поле нет запятой, поэтому деление на a не может означать разделение на части. Оно означает умножение на обратное a — число, которое, умноженное на a, даёт ровно один. В модуле 7, обратное трёх — это пять, потому что пятнадцать оставляет остаток один. Деление на три там — это умножение на пять.
Теперь вопрос, который даёт ответ на заголовок: почему p должно быть простым? Потому что только так у каждого элемента есть обратное. Попробуйте на часах с модулем двенадцать: число четыре, умноженное на что угодно, даёт только кратные четырём, и ни один из них не оставляет остаток один. У четырёх нет обратного, деление на четыре невозможно, и множество перестаёт быть полем. Это происходит с любым числом, которое имеет общий делитель с модулем — а простой модуль не имеет общего делителя ни с кем ниже него.
На практике вычисление обратного делается двумя способами. Маленькая теорема Ферма, 1640 года, гарантирует, что a в степени p минус один оставляет остаток один; следовательно, a в степени p минус два — это обратное, и возведение в степень решает задачу. Ещё быстрее — это расширенный алгоритм Евклида, последовательность делений, известная грекам, которая возвращает обратное за несколько шагов. Каждый кошелёк в мире использует один из двух, тысячи раз в секунду, и никто этого не замечает.
p в Bitcoin — это: 2 в степени 256, минус 2 в степени 32, минус 977. Простое число с семьюдесятью восемью десятичными цифрами. Выбор не декоративный — оно было выбрано близко к степени двойки намеренно, потому что уменьшение числа по модулю, столь близкому к 2^256, делается с помощью сдвигов и сложений, без деления. Это разница между дорогой и дешёвой операцией, повторяемой миллиарды раз.
Последняя осторожность, которая предотвращает частую путаницу в дальнейшем. В истории есть два больших числа, и они разные. p — это размер поля, часы, в которых живут координаты точек. Существует также n, количество точек, которые достигает генератор, и это часы, в которых живут приватные ключи и числа подписи. Оба простые, оба имеют 256 бит, и оба находятся очень близко друг к другу — но путаница между ними приводит к расчётам, которые кажутся правильными, но результаты не сходятся.
С часами, установленными на месте, остаётся наложить кривую на них. В следующем уроке, y² = x³ + 7, точки, которые удовлетворяют этому уравнению, и правило, которое складывает две из них, чтобы получить третью.