HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMinor

Extended Euclidean algorithm and modular multiplicative inverse element

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
inverseeuclideanextendedmodularalgorithmelementandmultiplicative

Problem

After my first exercise here is another. Again, this is exactly that: Exercise, which means that the output doesn't necessarily need to be beautifully formatted, etc. I probably have some variable naming issues around and also more general issues.

# coding=utf-8

"""Basic usage:
$ python xggt.py 3343 77
(1, -12, 521)
65
"""

import argparse

###############################################################################

def main():
    """Prints out the results of xggt().
    xggt() takes two non-optional integers as arguments.
    """

    parser = argparse.ArgumentParser()
    parser.add_argument('num_1', type=int)
    parser.add_argument('num_2', type=int)
    args = parser.parse_args()

    if (args.num_1 == 0) and (args.num_2 == 0):
        print("Please enter two positive integers.")
    else:
        print(xggt(args.num_1, args.num_2))
        print(modinv(args.num_1, args.num_2))

###############################################################################

def xggt(num_1, num_2):
    """Implements the Extended Euclidean algorithm.
    Returns the greatest common divisor of two integers > 0.
    Also returns the coefficients of Bézout’s identity.
    """

    if num_1 % num_2 == 0:
        return(num_2, 0, 1)
    else:
        gcd, lin_fact_1, lin_fact_2 = xggt(num_2, num_1 % num_2)

        lin_fact_1 = lin_fact_1 - num_1 // num_2 * lin_fact_2

        return(gcd, lin_fact_2, lin_fact_1)

###############################################################################

def modinv(num_1, num_2):
    """Returns the modular multiplicative inverse of two integers > 0
    """

    gcd, lin_fact_1, _ = xggt(num_1, num_2)

    if gcd != 1:
        return None
    else:
        return lin_fact_1 % num_2

###############################################################################

if __name__ == '__main__':
    main()

Solution

This looks like a bug in the input validation:

if (args.num_1 == 0) and (args.num_2 == 0):
    print("Please enter two positive integers.")
else:
    print(xggt(args.num_1, args.num_2))
    print(modinv(args.num_1, args.num_2))


The message "Please enter two positive integers." contradicts with the condition:
if both numbers are 0. I think you meant more like this:

if args.num_1 > 0 and args.num_2 > 0:
    print(xggt(args.num_1, args.num_2))
    print(modinv(args.num_1, args.num_2))
else:
    print("Please enter two positive integers.")


I also removed redundant parentheses.

You had redundant parentheses in other places too:

return(num_2, 0, 1)
    # ...
    return(gcd, lin_fact_2, lin_fact_1)


These are all unnecessary, so I recommend to remove them.

You can simplify x = x - ... with x -= ..., for example here:

# instead of this:
# lin_fact_1 = lin_fact_1 - num_1 // num_2 * lin_fact_2
lin_fact_1 -= num_1 // num_2 * lin_fact_2


Other than these minor issues, I think this is good and clean code! The names seem quite fine to me.

Code Snippets

if (args.num_1 == 0) and (args.num_2 == 0):
    print("Please enter two positive integers.")
else:
    print(xggt(args.num_1, args.num_2))
    print(modinv(args.num_1, args.num_2))
if args.num_1 > 0 and args.num_2 > 0:
    print(xggt(args.num_1, args.num_2))
    print(modinv(args.num_1, args.num_2))
else:
    print("Please enter two positive integers.")
return(num_2, 0, 1)
    # ...
    return(gcd, lin_fact_2, lin_fact_1)
# instead of this:
# lin_fact_1 = lin_fact_1 - num_1 // num_2 * lin_fact_2
lin_fact_1 -= num_1 // num_2 * lin_fact_2

Context

StackExchange Code Review Q#69991, answer score: 3

Revisions (0)

No revisions yet.