[CryptoHack] Modular Arithmetic (1)

 

 

 

Modular Arithmetic Course

 

 

 

 

 

Greatest Common Divisor

 

 

 

 

 

from math import *

print(gcd(12,8))
print(gcd(66528,52920))

 

 

 

 

 

Greatest Common Divisor flag

 

 

 

 

 

Extended GCD

 

 

 

 

 

https://web.archive.org/web/20230511143526/http://www-math.ucdenver.edu/~wcherowi/courses/m5410/exeucalg.html

Extended Euclidean Algorithm

 

 

 

 

 

위의 문서에서는 유클리드 호제법과 확장 유클리드 호제법에 대해 설명하고 있습니다. 문서를 읽으면서 최대한 이해하기 위해 노력해봅니다.

 

 

 

 

 

def egcd(a, b):
    if a == 0:
        return b, 0, 1

    gcd, x1, y1 = egcd(b % a, a)

    x = y1 - (b//a) * x1
    y = x1
    return gcd, x, y

print(egcd(26513,32321))

 

 

 

 

 

Extended GCD flag

 

 

 

 

 

Modular Arithmetic 1

 

 

 

 

 

print(8146798528947%17)

 

Modular Arithmetic 1 flag

 

 

 

 

 

Modular Arithmetic 2

 

 

 

 

 

print(pow(273246787654,65536,65537))

 

Modular Arithmetic 2 flag

 

 

 

 

 

Modular Inverting

 

 

 

 

 

q = 0

while (13*q+1)%3!=0:
        q+=1
print((13*q+1)//3)

 

Modular Inverting flag