Reverse modulaire - codage java

Question

Veuillez nous aider. J'ai travaillé sur ce non-stop et je ne peux pas le faire correctement. Le problème que j'ai est que la sortie que je reçois pour l'inverse est toujours 1.

C'est le code que j'ai (il calcule GCD et essaie de modifier ainsi il calcule aussi un^-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

Peut-on voir la déclaration des variables? Si vous mélangez l'entier avec le double, vos nombres peuvent être arrondis. Quoi qu'il en soit, si vous ne voulez que l'inverse, utilisez

juste Math.pow(a, -1);

En outre, dans la seconde boucle, vous ne réglez « un » il bouclera toujours:

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; 

     } 

Answer 2

Le code que vous avez posté ne déclare la plupart des variables qu'il utilise et donc ne compile pas les cotisations. Plus important encore, la variable v qu'il utilise pour produire le résultat n'est ni définie ni affectée à n'importe où dans le code affiché - tout ce qu'il contient n'a rien à voir avec le calcul.

Answer 3

@Justin, Merci. J'ai été capable de comprendre comment imprimer les variables dans chaque boucle. Je devais essentiellement mettre ma boucle avec la boucle GCD ... c'était tout. 2 semaines de travail et je devais me déplacer là où la boucle était.

Cela fonctionne! Je suis désolé mais je fais une bonne danse ici.

Answer 4

est ici une solution en Python qui devrait être facilement traduisible en 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 

Il utilise la pile, mais l'algorithme d'Euclide prend O (log n) étapes afin de ne pas avoir un débordement de pile à moins que votre les chiffres sont astronomiquement élevés. On pourrait aussi le traduire en une version non récursive avec quelques efforts.