平方剰余 def legendre_symbol(a, p): ls = pow(a, (p - 1)//2, p) if ls == p - 1: return -1 return ls

和訳すると「平方剰余問題」？ ある が与えられたときに が の平方剰余か、すなわち、なるが存在するかを判定する問題。通常 で、不明 なんか難しいらしい。（直感的には平方剰余である数とそうでない数の数に偏りがあるような気がするが、その実1 : 1） 当…

#aeroctf2021 #good_challenges_2021 #!/usr/bin/env python3.8 from gmpy import next_prime from random import getrandbits def bytes_to_long(data): return int.from_bytes(data, 'big') class Wardrobe: @staticmethod def create_boggarts(fear, dang…

奇素数と整数に対して、 のときは mod pで平方剰余 のときそうでない 性質 で ※ になる場合として、もありうる。この場合は xは平方剰余ではないので注意（ここが legendre記号との違い 原理はよくわかってないが、次のプログラムででのjacobi 記号を求める…

#foobarCTF_2022 from Crypto.Util.number import getPrime, bytes_to_long, GCD from random import randint flag = bytes_to_long(b"#REDACTED") p = getPrime(1024) q = getPrime(1024) N= p*q e = 0x10001 x = 2052550534767342463354055254165398369484…

#corctf2021 from Crypto.Util.number import bytes_to_long, getStrongPrime from random import randrange from secret import flag LIMIT = 64 def gen(): p = getStrongPrime(512) g = randrange(1, p) return g, p def main(): g, p = gen() print("g:"…