배낭 암호 (Knapsack cryptosystem)
배낭 암호 배낭의 무게가 N일때 a0~ak까지 물건의 무게의 합이 정확히 N일때를 찾아야함 오늘날의 표준 기준으로 보면 안전하지 않지만, 오늘날 사용하는 공개키 암호 시스템을 만드는 토대가 되었다. 정의 a=[a1,a2, ,,, ,ak], x=[x1,x2, ,,, ,xk], xi=0 또는 1 s=knapsackSum(a,x)=x1a1+x2a2+ ,,, + xkak이다. 주어진 a와 x로부터 s를 계산하는것은 아주 쉽다. 하지만 s와 a가 주어졌을때 x를 구하는 것은 어렵다. 초증가 순서짝 → ai ≥ a1+ a2+… +ai-1 인 경우를 말한다. 즉, a1을 제외한 각 원소가 그 이전의 모든 원소의 합보다 크거나 같을 때를 말한다. 예제 a = [17, 25, 46, 94, 201, 400] 이고 s =..
2022. 11. 11.
단축키
내 블로그
| 내 블로그 - 관리자 홈 전환 |
Q
Q
|
| 새 글 쓰기 |
W
W
|
블로그 게시글
| 글 수정 (권한 있는 경우) |
E
E
|
| 댓글 영역으로 이동 |
C
C
|
모든 영역
| 이 페이지의 URL 복사 |
S
S
|
| 맨 위로 이동 |
T
T
|
| 티스토리 홈 이동 |
H
H
|
| 단축키 안내 |
Shift + /
⇧ + /
|
* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.
