Is there a modular inverse function in erlang? - Erlang

Question

Im trying to recreate an RSA encryption program I had already made in Java into Erlang. I cannot figure out how to generate the private key though. My original java code:

privateKey = publicKey.modInverse(phi);

I couldn't find any general algorithms to find the 'd' or private key online. most feature small simple equations that cannot be implemented in larger problems or the tutorial simply gives the private key without explaining the process. Can someone point me in a direction so I could learn to generate the private key? Or if there is a modular inverse function in Erlang, indicate what it is please.

Thank you in advance.

EDIT: the actual equation to solve is [e*d mod (phi) = 1], where e is the public key, and d is the private key, and phi = [p-1][q-1]. I pretty much want to solve for d when all the other variables are known

EDIT2: Wolframalpha.com returns multiple possible values for d. How does that work?

Answer 1

the following code do the job, what is missing in the wolfram page is that you have to choose the solution greater than 2 and smaller than phi, and then there is one single solution.

[edit] add a test to detect when M and C are not relative primes and then return an error tuple more explicit than the arithmetic error reported previously

-module (decod).

-export ([private/2]).

% In the key generation you start by choosing P and Q 2 big primes
% N = P*Q
% M = (P-1)*(Q-1)
% C a number smaller than M such as gcd(M,C) = 1
% the public key is made of {N,C}
% then lets find U and V such as C*U + M*V = 1 and 2 < U < M
% the private key is {U,N}
private(M,C) when is_integer(M), is_integer(C), M > C-> 
    P = private1({M,0},{C,1}),
    adjust(P,M).


private1(_,{1,P}) -> P;
private1(_,{0,_}) -> {error,gcd_not_1};
private1({R1,U1},{R2,U2}=A2) ->
    F = R1 div R2,
    private1(A2,{R1-R2*F,U1-U2*F}).

adjust(R,_) when is_tuple(R) -> 
    R;
adjust(P1,M) when P1 =< 2 ->
    K = (2 - P1) div M + 1,
    P1 + K * M;
adjust(P1,M) when P1 >= M ->
    K = (P1 - M) div M + 1,
    P1 - K * M;
adjust(P1,_) -> P1.