Необходимо написать алго вычисления
(1 / a) mod p, используя "Euclidean Inversion"
Условия:
* а и р тут 256 битные,
* р - константа ( p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F )
* нету ограничений на число циклов и разрядность машины, на которой это решается (пусть разрядность будет даже 256)
Обычно для имплементации очень больших чисел используются специальные
классы, позволяющие работать с массивами 32-х или 64-битных чисел как с одним числом. Если рассматривать, например, распространённый язык программирования JavaScript, который по умолчанию функционирует в интернет-браузерах, то можно применять следующие JS-библиотеки BigInteger и BigNumber, например:
https://github.com/silentmatt/javascript-biginteger/https://github.com/MikeMcl/bignumber.js/* ALU машины не умеет делать операции в floating point
* ALU машины не умеет делать деление (+ , - и умножение по-прежнему доступны)
mod p традиционным способом можно было бы сделать через итеративное вычитание и проверку условия (1/a) <= p, но как реализовать используя "Euclidean Inversion" непонятно, именно этот кейс не рассматривается в интернетах при описании
По всей видимости, Вам нужно расчитать число по формуле:
a-1 mod pВ общем-то, это стандартная функция, которая применяется в криптографии RSA и называется ModInverse. В протоколе Bitcoin эта криптография
не задействована, хотя при обилии недостатков и высокой ресурсоёмкости у RSA есть положительные характеристики.
Можете посмотреть реализацию Вашей задачи, например, здесь:
https://stackoverflow.com/questions/26985808/calculating-the-modular-inverse-in-javascriptВот более подробная статья на английской Википедии, но перевода на русский язык пока нет:
https://en.wikipedia.org/wiki/Modular_multiplicative_inverse
