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.

#include <openssl/bn.h>


BN_mod_inverse ( a, b, c, ctx );
| improve this answer | |
  • 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 '14 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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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