I've seen several variations on "modular inverse" but I can't seem to identify the proper way of utilizing it for C++. I'm not sure how this python code translates into c++:

def inverse(x, p):

Calculate the modular inverse of x ( mod p )
the modular inverse is a number such that:
(inverse(x, p) * x) % p == 1
you could think of this as: 1/x
inv1 = 1
inv2 = 0
while p != 1 and p!=0:
inv1, inv2 = inv2, inv1 - inv2 * (x / p)
x, p = p, x % p

return inv2

My current coding is here: http://coliru.stacked-crooked.com/a/74648b16c2692525

But it only shows like the first public key properly, after that it messes up.

2 Answers 2

#include <openssl/bn.h>


BN_mod_inverse ( a, b, c, ctx );
  • I downloaded that library, but I don't know what to do with your inverse. I'm only sending two variables to my inverse to be worked with. I think it works out to the number to be modding and the number being modded by.
    – Mine
    Jun 24, 2014 at 7:29

I'll take a shot, I don't code in C++ often. Mostly do Java, and I am completely unfamiliar with python. I have tested this code.

int inverse(int x,int p)
  int orig = p;
  int inv1 = 1;
  int inv2 = 0;
  while(p != 1 && p != 0)
    int temp = inv2;
    inv2 = inv1 - inv2 * (x/p);
    inv1 = temp;
    temp = p;
    p = x % p;
    x = temp;
  while(inv2 < 0)
    inv2 += orig;
  return inv2;

It turns out that python does % differently than C++. The while(inv2 < 0) statement corrects the sign error caused by the difference. There is probably a more elegant way of doing this, but this was quick and easy.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.