-
RSA 원리와 구현
RSA란? 고전 암호와는 달리, RSA, ECC 등은 ‘어려운 문제’에 기반하여 암호화를 진행합니다. 이러한 ‘어려운 문제’는 컴퓨터를 이용하여도 정답(혹은 해)를 구하기 어려운 문제를 말하며, 소인수분해 문제, 이산 로그 문제 등이 대표적인 예시입니다. RSA는 그 중 소인수분해가 어려운 문제라는 점을 활용하는 암호화방식입니다. GNFS 등 빠른 소인수분해 알고리즘이 등장하였으나, 비트수에 대한 다항 시간 알고리즘은 알려져 있지 않아 큰 수를 소인수분해하는 것은 여전히 어려운 문제입니다. RSA는 1978년 로널드 라이베스트(Ron Rivest), 아디 샤미르(Adi Shamir), 레너드 애들먼(Leonard Adleman)의 연구에 의해 체계화되어,...
-
Tonelli-Shanks 알고리즘 구현
Tonelli-Shanks 알고리즘은 mod p에서 Quadratic Residue에 대해 그 제곱근을 구하는 알고리즘이다. def tonelli_shanks(n,p): def isQR(x,p): return pow(x,(p-1)//2,p)==1 if not isQR(n,p): return -1 Q,S=p-1,0 while Q%2==0: S+=1 Q//=2 z=None for x in range(2,p): if not isQR(x,p): z=x break M,c,t,R=S,pow(z,Q,p),pow(n,Q,p),pow(n,(Q+1)//2,p) while True: if t==0: return 0 elif t==1: return R k=t*t%p ii=None for i in range(1,M): if k==1: ii=i break k*=k k%=p b=pow(c,2**(M-i-1),p)%p M=ii%p c=b*b%p t=t*c%p R=R*b%p if __name__=='__main__': n,p=map(int,input().split()) print("STARTED") print(tonelli_shanks(n,p))
-
Caesar Cipher(시저 암호)
Caesar Cipher은 고대 로마 황제였던 카이사르(시저)가 사용했던 간단한 암호로써, 알파벳을 특정한 개수만큼 shift하는 것으로 decode할 수 있다. shift된 문자열이 encode되기 전의 원본인지 판별하는 것을 자동화하는 것은 쉽지 않으며, decode 결과로 가능한 문자열의 수는 많지 않으므로(26개) 다음은 가능한 모든 결과를 출력하는 함수의 구현이다. def decode_caesar(t): def nxtAlpha(x): if x=='z': return 'a' elif x=='Z': return 'A' else: return chr(ord(x)+1) import copy s=copy.deepcopy(t) res=[] for x in range(26): res.append(copy.deepcopy(s)) for y in range(len(s)): if s[y].isalpha(): s=s[:y]+nxtAlpha(s[y])+s[y+1:] return tuple(res)...
-
KOI 2020 1차대회 고등부 2교시 풀이
문제 링크 KOI 제공 PDF BOJ - 박 터트리기 BOJ - 햄버거 분배 BOJ - 조명등 1번 - 박 터트리기 BOJ - 박 터트리기 단순 수학입니다. $N < \frac{K(K+1)}{2}$라면 불가능하고, 아닐 경우에는 N%K의 값을 확인하여 적당히 처리해주면 됩니다. #include<bits/stdc++.h> using namespace std; int main(void){ ios::sync_with_stdio(0);cin.tie(0); int N,K; cin>>N>>K; if(K*(K+1)/2>N){ cout<<-1; return 0; } N-=K*(K+1)/2; cout<<K+(N%K?1:0)-1; } 2번 - 햄버거 분배 BOJ - 햄버거 분배 그리디입니다. 가능한 한 왼쪽에 있는 햄버거를 먹게끔 짜면 됩니다. 전체 시간복잡도는...
-
제 4회 생각하는 프로그래밍 대회 Open Contest 후기
딱히 열심히 할 생각이 없었는데 4등한 기념으로 리뷰글 씁니다. 우선, 난이도 배분이 상당히 적절하게 되어있었습니다. 간단한 입출력 문제부터, 어느 정도 심화적인 개념이 필요한 문제까지 고루 분포해있었다고 생각합니다. 다이아 이상의 문제들도 익숙하신 분이라면 아니겠지만, 플레티넘 정도의 문제를 연습하고 계신 분들까지라면 풀어보시는 것도 좋을 듯한 문제셋입니다. A. 고무오리 디버깅 문제의 컨셉과 풀이 모두 굉장히 아기자기한 문제입니다. 문제를 풀며 단 한 가지 걱정이 되었던 것은 한글 입출력인데, 영문자를 취급하듯 코드를 짜도 AC를 받을 수 있었습니다. 변수에 남은 문제의...