#cakectf2021 from Crypto.Util.number import getStrongPrime, bytes_to_long p = getStrongPrime(512) q = getStrongPrime(512) r = getStrongPrime(512) n = p*q*r x = pow(p + q, r, n) y = pow(p + q*r, r, n) m = bytes_to_long(open("./flag.txt", "r…

#tetctf_2021 from collections import namedtuple from Crypto.Util.number import getPrime import random Complex = namedtuple("Complex", ["re", "im"]) def complex_mult(c1, c2, modulus): return Complex( (c1.re * c2.re - c1.im * c2.im) % modulu…

確率的素数判定法の一つ Fermat's little theorem: 素数 と互いに素な → 対偶を取ると と互いに素な→ならは素数でない ということで、判定したい値に対して適当にを持ってきて のとき は を約数に持つので合成数 のとき は合成数 と判断できる。のとき、そう…