A x B mod P на MCU?

Question

[sdxq]

Каким образом можно реализовать алгоритм на 32 битном микроконтроллере
A x B mod P
если A, B, P аргументы размером несколько сотен байт?

Answer 1

[Rsa97]

Базовые сложение, вычитание и сравнение реализуются стандартно для длинной целочисленной арифметики.
Далее, следует учесть, что
(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.

Answer 2

[Zolg]

Прекрасная C-библиотека для длиной математики:
https://www.libtom.net/LibTomMath/