Module net.luis.utils
Package net.luis.utils.math.algorithm

Class ExtendedEuclideanAlgorithm

java.lang.Object
net.luis.utils.math.algorithm.ExtendedEuclideanAlgorithm
public class ExtendedEuclideanAlgorithm extends Object
Implementation of the Extended Euclidean Algorithm (EEA).
The EEA is an extension of the Euclidean Algorithm and is used to find the greatest common divisor (GCD) of two integers.

  • Field Details

    • firstCoefficients

      private final List<BigInteger> firstCoefficients
      The first coefficients of the EEA.

    • secondCoefficients

      private final List<BigInteger> secondCoefficients
      The second coefficients of the EEA.

    • initialValue

      private final BigInteger initialValue
      The initial value of the EEA.

    • initialDivisor

      private final BigInteger initialDivisor
      The initial divisor of the EEA.

    • value

      private BigInteger value
      The current value of the EEA.

    • divisor

      private BigInteger divisor
      The current divisor of the EEA.

    • remainder

      private BigInteger remainder
      The current remainder of the EEA.

    • quotient

      private BigInteger quotient
      The current quotient of the EEA.

    • step

      private int step
      The number of steps the EEA has executed.

  • Constructor Details

    • ExtendedEuclideanAlgorithm

      public ExtendedEuclideanAlgorithm(int value, int divisor)
      Constructs a new EEA with the given value and divisor.
      Parameters:
      value - The value of the EEA
      divisor - The divisor of the EEA
      Throws:
      IllegalArgumentException - If the value or divisor is 0

    • ExtendedEuclideanAlgorithm

      public ExtendedEuclideanAlgorithm(long value, long divisor)
      Constructs a new EEA with the given value and divisor.
      Parameters:
      value - The value of the EEA
      divisor - The divisor of the EEA
      Throws:
      IllegalArgumentException - If the value or divisor is 0

    • ExtendedEuclideanAlgorithm

      public ExtendedEuclideanAlgorithm(@NotNull @NotNull BigInteger value, @NotNull @NotNull BigInteger divisor)
      Constructs a new EEA with the given value and divisor.
      Parameters:
      value - The value of the EEA
      divisor - The divisor of the EEA
      Throws:
      IllegalArgumentException - If the value or divisor is 0

  • Method Details

    • gcd

      public static int gcd(int value, int divisor)
      Calculates the greatest common divisor (GCD) of the given value and divisor using the EEA.
      Parameters:
      value - The value to calculate the GCD for
      divisor - The divisor to calculate the GCD for
      Returns:
      The GCD of the given value and divisor
      Throws:
      IllegalArgumentException - If the value or divisor is 0

    • gcd

      public static long gcd(long value, long divisor)
      Calculates the greatest common divisor (GCD) of the given value and divisor using the EEA.
      Parameters:
      value - The value to calculate the GCD for
      divisor - The divisor to calculate the GCD for
      Returns:
      The GCD of the given value and divisor
      Throws:
      IllegalArgumentException - If the value or divisor is 0

    • gcd

      @NotNull public static @NotNull BigInteger gcd(@NotNull @NotNull BigInteger value, @NotNull @NotNull BigInteger divisor)
      Calculates the greatest common divisor (GCD) of the given value and divisor using the EEA.
      Parameters:
      value - The value to calculate the GCD for
      divisor - The divisor to calculate the GCD for
      Returns:
      The GCD of the given value and divisor
      Throws:
      IllegalArgumentException - If the value or divisor is 0

    • isComplete

      public boolean isComplete()
      Checks if the EEA is complete.
      Returns:
      True, if the EEA is complete, otherwise false

    • getInitialValue

      @NotNull public @NotNull BigInteger getInitialValue()
      Returns the initial value of the EEA.
      Returns:
      The initial value

    • getInitialDivisor

      @NotNull public @NotNull BigInteger getInitialDivisor()
      Returns the initial divisor of the EEA.
      Returns:
      The initial divisor

    • getValue

      @NotNull public @NotNull BigInteger getValue()
      Returns the current value of the EEA.
      Returns:
      The current value

    • getDivisor

      @NotNull public @NotNull BigInteger getDivisor()
      Returns the current divisor of the EEA.
      Returns:
      The current divisor

    • getRemainder

      @NotNull public @NotNull BigInteger getRemainder()
      Returns the current remainder of the EEA.
      Returns:
      The current remainder

    • getQuotient

      @NotNull public @NotNull BigInteger getQuotient()
      Returns the current quotient of the EEA.
      Returns:
      The current quotient

    • getStep

      public int getStep()
      Returns the number of steps the EEA has executed.
      Returns:
      The number of steps

    • getFirstCoefficient

      @NotNull public @NotNull BigInteger getFirstCoefficient()
      Returns the first coefficient of the EEA.
      Returns:
      The first coefficient

    • getSecondCoefficient

      @NotNull public @NotNull BigInteger getSecondCoefficient()
      Returns the second coefficient of the EEA.
      Returns:
      The second coefficient

    • execute

      public void execute()
      Executes the EEA for a single step.

    • execute

      public void execute(int steps)
      Executes the EEA for the given number of steps.
      If the EEA is already completed the method will return immediately.
      Parameters:
      steps - The number of steps to execute

    • executeUntilComplete

      public void executeUntilComplete()
      Executes the EEA until it is complete.

    • getFirstCoefficient

      @NotNull private @NotNull BigInteger getFirstCoefficient(int step)
      Gets the first coefficient of the EEA.
      The number of steps is subtracted from the size of the first coefficients list to get the correct coefficient.
      Parameters:
      step - The number of steps to go back
      Returns:
      The first coefficient of the EEA

    • getSecondCoefficient

      @NotNull private @NotNull BigInteger getSecondCoefficient(int step)
      Gets the second coefficient of the EEA.
      The number of steps is subtracted from the size of the second coefficients list to get the correct coefficient.
      Parameters:
      step - The number of steps to go back
      Returns:
      The second coefficient of the EEA

    • executeStep

      private void executeStep()
      Executes a single step of the EEA.
      The values of the EEA are recalculated.
      See Also:

    • update

      private void update(@NotNull @NotNull BigInteger value, @NotNull @NotNull BigInteger divisor, @NotNull @NotNull BigInteger remainder, @NotNull @NotNull BigInteger quotient)
      Updates the values of the EEA.
      The first and second coefficients are calculated and added to their respective lists.
      The value, divisor, remainder, quotient and step are updated.
      Parameters:
      value - The new value
      divisor - The new divisor
      remainder - The new remainder
      quotient - The new quotient

    • equals

      public boolean equals(Object object)
      Overrides:
      equals in class Object

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • toString

      public String toString()
      Overrides:
      toString in class Object