Lab 2.sagews

#################### EU and Extended EU Algorithm
# Euclidean Algorithm where a > b >= 0
def euclid(a, b):
    if a > b & b >= 0:
        r = a % b
        if r > 0:
            a = b
            b = r
        else:
            return b
    else:
        t = a
        a = b
        b = t
    return euclid(a, b)

# Tests 1
euclid(710, 310)
euclid(60, 24)
euclid(55, 22)


# Euclidean Algorithm without a > b >= 0
def new_euclidean(a, b):
    r = a % b
    if r > 0:
        a = b
        b = r
    else:
        return b
    return new_euclidean(a, b)

# Tests 2
new_euclidean(18, 12)
new_euclidean(12, 18)
new_euclidean(11, 10)
new_euclidean(10, 11)


# Extended Euclidean Algorithm where a > b >= 0
# ax + by = d = gcd(a, b)
def extended_euclid(a, b):
    if a > b & b >= 0:
        if b == 0:
            return a, 1, 0
        else:
            d, x, y = extended_euclid(b, a % b)
            return d, y , x - (a // b) * y
    else:
        t = a
        a = b
        b = t
    return extended_euclid(a, b)

# Tests 3
extended_euclid(42, 30)
extended_euclid(11, 10)
extended_euclid(18, 12)


# Extended Euclidean Algorithm where a > b >= 0
# ax + by = d = gcd(a, b)
def new_extended_euclidean(a, b):
    if b == 0:
        return a, 1, 0
    else:
        d, x, y = extended_euclid(b, a % b)
        return d, y , x - (a // b) * y

# Tests 4
new_extended_euclidean(1759, 550)
new_extended_euclidean(42, 30)
new_extended_euclidean(624, 36)


#################### Finite Fields
gf = GF(17)
gf(13) - gf(16)
gf(11) + gf(10)
gf(3) * gf(8)
gf(5^(-1))


big_gf=GF(503777509)
big_gf(987654321^(-1))


#################### Built-in GCD and XGCD Functions
gcd(24, 300)
gcd(4567, 4731907)
gcd(100, 1015)

10 12 11 6 6 1 1 (6, -2, 3) (1, 1, -1) (6, 1, -1) (1, -111, 355) (6, -2, 3) (12, 1, -17) 14 4 7 7 184455016 12 1 5

xgcd(36, 624)
xgcd(4321, 9226177)
xgcd(45, 12345)

(12, -17, 1) (1, -3407771, 1596) (15, -274, 1)

divisors(101001)

[1, 3, 131, 257, 393, 771, 33667, 101001]

divisors(101004)

[1, 2, 3, 4, 6, 12, 19, 38, 57, 76, 114, 228, 443, 886, 1329, 1772, 2658, 5316, 8417, 16834, 25251, 33668, 50502, 101004]

gcd(101001, 101004)

3