Модульное обратное - кодирование Java

Question

Пожалуйста, помогите.Я работал над этим без остановки и не могу понять это правильно.У меня проблема в том, что вывод, который я получаю для обратного, всегда равен 1.

Это мой код (он вычисляет GCD и пытается изменить, чтобы он также вычислял ^ -1):

import java.util.Scanner;

public class scratchwork
{


    public static void main (String[] args)
    {
        Scanner keyboard = new Scanner(System.in);

        long n, a, on, oa;
        long gcd = 0;

        System.out.println("Please enter your dividend:");
        n= keyboard.nextLong();

        System.out.println("Please enter your divisor:");
        a= keyboard.nextLong();

        on= n;
        oa= a;

        while (a!= 0)
                {gcd=a;
                    a= n% a;
                    n= gcd;
        }

        System.out.println("Results: GCD(" + odd + ", " + odr + ") = " + gcd);

        long vX; vS; vT; vY; q; vR; vZ; m; b;

        vX = n; vY=a;
        vS = 0; vT = 1; m=0; b=0;
        while (a != 0)
        {
            m=vT;;
                b=vX;
                q = n / a;
                vR = vS - q*vT;
                tZ = n - q*a;
                vS = vT; n = da;
                vT = tY; dY = vZ;

        }

         if (d>1) System.out.println("Inverse does not exist.");
        else System.out.println("The inverse of "+oa+" mod "+on+" is "+vT);
    } 
}

Answer 1

Вот решение на Python, которое должно быть легко переведено на Java:

def euclid(x, y):
    """Given x < y, find a and b such that a * x + b * y = g where, g is the
    gcd of x and y.  Returns (a,b,g)."""
    assert x < y
    assert x >= 0
    assert y > 0

    if x == 0:
        # gcd(0,y) = y
        return (0, 1, y)
    else:
        # Write y as y = dx + r
        d = y/x
        r = y - d*x

        # Compute for the simpler problem.
        (a, b, g) = euclid(r, x)

        # Then ar + bx = g     -->
        #      a(y-dx) + bx = g    -->
        #      ay - adx + bx = g    -->
        #      (b-ad)x + ay = g
        return (b-a*d, a, g)

def modinv(x, n):
    (a, b, g) = euclid(x%n, n)
    assert g == 1

    # a * x + b * n = 1 therefore
    # a * x = 1 (mod n)
    return a%n

Он использует стек, но алгоритм Евклида использует O (log n) шагов, поэтому у вас не будет переполнения стека, если тольковаши цифры астрономически высоки.Можно также перевести его в нерекурсивную версию с некоторыми усилиями.

Answer 2

Код, который вы разместили, не объявляет большинство переменных, которые он использует, и поэтому сборы не компилируются.Наиболее важно то, что переменная v, которую она использует для вывода результата, не определена и не назначена нигде в размещенном коде - что бы она ни содержала, не имеет ничего общего с вычислением.

Answer 3

@ Джастин, Благодарю. Мне удалось выяснить, как распечатать переменные в каждом цикле. Мне в основном пришлось замкнуть цикл с GCD ... вот и все. 2 недели работы, и мне нужно было просто переместиться туда, где была петля.

Это работает! Извините, но я делаю счастливый танец здесь.

Answer 4

Можем ли мы увидеть объявление переменных?Если вы смешаете целое число с двойным, ваши числа могут быть округлены.В любом случае, если вы хотите использовать только обратное, просто используйте Math.pow(a, -1);

Кроме того, во втором цикле вы никогда не установите «a», поэтому он будет повторяться вечно:

while (a != 0)
        {
            m=vT;;
                b=vX;
                q = n / a;
                vR = vS - q*vT;
                tZ = n - q*a;
                vS = vT; n = da;
                vT = tY; dY = vZ;

        }