Базовые сложение, вычитание и сравнение реализуются стандартно для длинной целочисленной арифметики.
Далее, следует учесть, что
(A + B) mod P = ((A mod P) + (B mod P)) mod P
(A * B) mod P = ((A mod P) * (B mod P)) mod P
Тогда, реализовав умножение через операции сдвига (умножения на два) и сложения, можно получить результат, используя буфер всего на один бит (в реальной программе - на байт или слово) больше, чем длина P.