타원곡선 DSA 디지털 서명 자료조사 DSA란? 디지털 서명 알고리즘(Digital Signature Algorithm, DSA)은 디지털 서명을 위한 표준이다. NIST가 1991년 8월 DSS라는 미국 전자서명 표준에서 이용하기 위해 정부용 전자서명 알고리즘으로 발표했으며, 현재는 DSA와 함께 ECDSA, RSA를 사용하고 있다. 디지털 서명 인증 방식 전자서명(디지털 서명)은 무결성, 인증, 부인방지를 만족해야한다. 전자서명에는 공개키 암호화 알고리즘이 쓰이며 크게 3가지 종류의 알고리즘이 있다. 합성수의 소인수분해문제가 어렵다는 데에 기초한 RSA형 알고리즘 유한체의 이산대수 문제가 어렵다는 데에 기초한 ElGamal형 알고리즘 타원곡선을 이용한 EC-DSA, EC-KCDSA DSA는 이 중 E..

Mutex와의 비교 코드 #include #include #include #include #include #include using namespace std; class Node { public: int value; Node* next; Node() : value(0) { next = NULL; } Node(int k_value) { next = NULL; value = k_value; } }; int node_n; //random 구현 random_device rd; mt19937 gen(rd()); uniform_int_distribution dis(0, 10); //출력을 위한 mutex mutex mut; class LFStack { private: Node * head; public: void ..

목차 문제 정의 lock free 구현 ABA 해결 int형 구현(+ Hazard pointer) Counter 그 외의 방법들 mutex lock(spin lock)과의 비교 Counter #include #include #include #include #include #include using namespace std; class Node { public: int value; Node* next; Node() : value(0) { next = NULL; } Node(int k_value) { next = NULL; value = k_value; } }; int node_n; //random 구현 random_device rd; mt19937 gen(rd()); uniform_int_distribut..

목차 문제 정의 lock free 구현 ABA 해결 int형 구현(+ Hazard pointer) Counter 그 외의 방법들 mutex lock(spin lock)과의 비교 Hazard Pointer https://m.blog.naver.com/PostView.nhn?blogId=jjoommnn&logNo=130127286459&proxyReferer=https:%2F%2Fwww.google.com%2F 를 참고하여 작성하였다. 문제점 먼저 delete를 이용하여 객체를 삭제하면, 해당 객체를 참조하고 있던 스레드에 문제가 생길 수도 있고 객체가 삭제된 주소에 다시 같은 객체가 할당되어 ABA 문제가 일어날 가능성이 있다. 새로 객체를 할당하는 것은 사용자가 관리하는 list가 아니다. 1번 문제를 ..

목차 문제 정의 lock free 구현 ABA 해결 int형 구현(+ Hazard pointer) Counter 그 외의 방법들 mutex lock(spin lock)과의 비교 ABA 해결 int형 구현 ABA 문제는 매개변수를 int형으로 구현하면 쉽게 해결할 수 있다. 하지만 문제점은 존재한다(뒷부분에 언급). 코드 #define _CRT_SECURE_NO_WARNINGS #define NULL_INT -1 // NULL 값 #include #include #include #include #include // #include #include using namespace std; struct Node { int data; Node* next_node; }; int node_n; atomic free_l..

목차 문제 정의 lock free 구현 ABA 해결 int형 구현(+ Hazard pointer) Counter 그 외의 방법들 mutex lock(spin lock)과의 비교 문제 정의 문제 Linked List 자료구조에서 push()와 pop() 연산을 구현한다. Linked List는 FreeList와 HeadList 두가지가 있으며 여러 스레드가 두 개의 List를 번갈아가며 push, pop 연산을 수행한다. 스레드들이 각각 연산을 수행하기 위해서는 List들에 대한 상호배제가 필요하다. 해석 상호 배제에는 여러가지 방법이 있지만, 크게 두가지로 나눌 수 있다. lock 변수의 조건을 체크하며 반복문을 돌고 있는 spin lock과, lock 변수 없이 계속 시도하면서 적절한 때에 동작을 수행..

https://www.algospot.com/judge/problem/read/TRIANGLEPATH 문제 6 1 2 3 7 4 9 4 1 7 2 7 5 9 4 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄로 내려가는 경로를 만들려고 합니다. 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있습니다. 이 때 모든 경로 중 포함된 숫자의 최대 합을 찾는 프로그램을 작성하세요. 입력 입력의 첫 줄에는 테스트 케이스의 수 C(C > C; while (C--) { cin >> n; int index = 0; for (int i = 0; i ..

세그먼트 트리 https://www.acmicpc.net/blog/view/9 백준님 글 배열 크기 결정 세그먼트 트리를 만들기 위해서 C++의 경우, vector 자료형을 사용하는데 python으로 구현할 것이기 때문에 배열을 사용하려고 한다. 배열의 크기가 얼마나 되어야 할지 가늠하기 위해 크기를 결정해보자. 2의 제곱 수가 리프 노드의 수(n)로 주어진다면 ( 분석해야할 data 갯수가 2의 제곱 수라면 ) 각 단계마다 1/2씩 줄어나가므로 log(n)이 필요한 총 단계(화살표)가 되고 전체 층의 갯수, 즉 높이(h)는 log(n)+1이 된다. 최상위 노드부터 2^(0)개의 노드로 시작하여 층이 증가할 수록 2의 지수 또한 증가하기 때문에 꽉찬 이중 트리(full binary tree)의 총 노드 ..