реализация библиотеки bignum для шифрования rsa

Вы можете подделать операции модуля с делением. Ваша операция модуля эквивалентна:

v = n - (n / m) * m

где n — делитель, m — модуль, а v — выходное значение (все произвольные числа точности)

Если вы застряли на делении, вы можете просто реализовать его, как если бы вы выполняли длинное деление вручную. (Вы должны были научиться делать это в средней школе с помощью умножения и вычитания. Достаточно легко перевести процесс в основание 2. Сделайте несколько на бумаге, если вы застряли. Если вам нужен более эффективный алгоритм, вы, вероятно, можете найдите его, выполнив поиск в Google по запросу «алгоритм деления произвольной точности»)

Когда у вас есть модуль, вы можете вычислить модульное возведение в степень с повторным возведением в квадрат. Наблюдайте, как мы вычисляем некоторое большое целое число X в степени 67 по модулю N:

v1  = X mod N         // X^1 mod N
v2  = v1  * v1  mod N // X^2 mod N
v4  = v2  * v2  mod N // X^4 mod N
v8  = v4  * v4  mod N
v16 = v8  * v8  mod N
v32 = v16 * v16 mod N
v64 = v32 * v32 mod N // X^64 mod N

v66 = v64 * v2  mod N // X^66 mod N
v67 = v66 * v1  mod N // X^67 mod N

Математически вы можете понять, почему это имеет смысл. Этот алгоритм является обычно выбираемым алгоритмом для вычисления модульных возведений в степень и работает во времени и пространстве логарифмически по размеру экспоненты и логарифмически по размеру основания (т.е. он быстр даже для огромных чисел)

P.S. Убедитесь, что вы сказали своему профессору, что он глуп из-за того, что не позволяет вам использовать внешние библиотеки. Одна из самых важных вещей, которую могут усвоить программисты, — это когда быть ленивым (т. е. когда найти и использовать библиотеку, чтобы что-то сделать, а не создавать собственное решение).