Pollard's Rho Algorithm
❗이 글에는 Miller-Rabin 소수판별법에 대한 선행 지식이 필요합니다. 혹 이에 대해 잘 모르는 독자들은 임한결 작가의 Miller-Rabin 소수판별법에 관한 글을 읽어보는 것을 추천합니다.
Introduction
소인수분해. 개념만 들어서는 중학교 1학년때 잠시 배우고 지나간, 굳이 수학의 길로 들어서지 않는다면 영원히 모르고 살아도 될 것 같은 느낌이 드는 개념이다. 혹여나 이런
Lee Sihoo
Pollard's Rho Algorithm - Answer Code
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
using namespace std;
typedef long long int lli;
lli mul(lli a, lli b, lli n) {
return (__int128)a*
2025 KSASF
Intro
2025 KSASF가 7월 첫째 주 동안 진행되었다. 도우미는 그 전 주부터 열심히(?) 준비했다. 이번 글에서는 그 2주간의 여정을 간략히 요약하고자 한다. KSASF에는 정말 많은 부서가 참여하고, 각 부서만의 특별한 일정과 과제들이 있었으므로 참가한 각 사람의 의견을 최대한 담고자 노력하였다.
-7일차 6.23 (월)
임한결
어제 한과영 도착. 오늘 까지는
String Matching Algorithms
1.Introduction
"나는 제발 제발 제발 제발 제발 자고 싶다"라는 문장에서 "제발"의 위치를 모두 찾아보자. "나"를 position \(0\)라고 했을때 \(3, 6, 9, 12, 15\)에 있다는 것을 알 수 있다.
위에는 농담이고, 아무튼 위와 같은 작업을 수행하는 것을 String Matching이라고
Shortest path problem
Introduction
Shortest path problem이란 무엇일까. 한글로 직역하면 최단거리 알고리즘이 되는 이 알고리즘은 이름 그대로 어떤 그래프에서 위치간의 최단 거리를 찾는 알고리즘이다. 말만 들어서는 체감하기 힘들지만, 최단거리 알고리즘은 우리의 내비게이션부터 네트워크 시스템, 물류 배송 등 여러 분야에서 이미 빠질 수 없는 필수 기술로 자리잡았다.
하지만 그렇다고 해서 최선의 최단거리 알고리즘을 구현하는
Shortest Path Problem - Answer code
나의 글 중 < Shortest Path Problem > 글에 대한 정답 코드들이다. 혹시 풀어보고 싶은 사람이 있을까봐 분리해둔다.
//17071
#include <stdio.h>
#include <tuple>
#include <queue>
#include <cstring>
using namespace std;
int dist[500001][2] = {};
int main(void) {
int n = 0;
int
RSA, and Bézout's Numbers
Introduction
최근 인터넷을 돌아다니다 보면 이런 뉴스를 심심찮게 볼수 있다
양자컴퓨터가 벌써 RSA 암호화 알고리즘을 깼다고?
RSA는 뭐고, 이건 양자컴퓨터랑 무슨 관련이 있는 것일까? 양자컴퓨터 부분은 담에 알아보고, 우선은 RSA가 뭔지, 이것은 어떻게 작동하는지를 알아보고 증명해보자.
암호화의 기본 원리
내가 10m 떨어진 친구한테 abcd라는 비밀, 즉 Secret를 전해야 한다고 생각하자.