java - Calculating modulo inverse in java

Question

I was trying to figure out a way to calculate modulo inverse using java so I wrote this function to do it:

public static int privatekey(int primeprod, int e, int lambda)
{
    Random random = new Random();
    float d = 0;
    //extended euler's theorem is
    //d = (1 + x*lambda) / e
    //d is smaller than primeprod
    while(true)
    {
        int d = random.nextInt(200) + 1;
        System.out.println("seed: "+x);
        var = (1 + (x*lambda)) / e;
        System.out.println("var: "+d);
        if(isInteger(d) && d < primeprod)
        {
            break;
        }
    }
    int finalvar = (int)d;
    return finalvar;
}

I felt that it was going wrong so I reversed euclidean theorem extension I used above as follows

1 + x.lambda
------------- = d (this one is the equation to find out d when x is any integer)
     e
     

de = 1 + x.lambda

de - 1 = x.lambda

de - 1
------- = x (this one is to check whether the value obtained by the above equation is true or not by checking if x is the same value we had chosen for our calculation in the first place)
lambda

After doing this check I found that the value of x I obtained in the reversed equation I had solved to check for mistakes is not equal but approximate to the original random value which I had generated.

For example taking these values:

e = 327
lambda = 484
x = 76

We get d as 112.0

later We reverse The equation to find the value of x to confirm

we get:
x = 75.667355372 (Which is approximate to the original value)

I wasn't able to figure out where it was going wrong.

To look at the full program please visit this link.

Please tell me If I have done something wrong here.

Thank You in advance!

标签： javamodulo

Answer 1

Alright I got an answer to this problem. The Issue was I was performing arithmetic operations on integer so the value I got as result was an integer.

Instead of using integer I later used Double to do the same operation and I resolved the issue.

public static int privatekey(Double primeprod, Double e, Double lambda)
{
    Random random = new Random();
    float d = 0;
    //extended euler's theorem is
    //d = (1 + x*lambda) / e
    //d is smaller than primeprod
    while(true)
    {
        int d = random.nextInt(200) + 1;
        System.out.println("seed: "+x);
        var = (1 + (x*lambda)) / e;
        System.out.println("var: "+d);
        if(isInteger(d) && d < primeprod)
        {
            break;
        }
    }
    int finalvar = (int)d;
    return finalvar;
}

This resolved the issue.