소인수분해 구현: 루트 N 최적화 방법
소인수분해 문제
양의 정수 N이 주어졌을 때, 이를 소수들의 곱으로 분해하는 문제입니다.
예: 60 = 2 × 2 × 3 × 5
입력 조건
하나의 정수 N (2 ≤ N ≤ 1,000,000,000)
출력 조건
N의 소인수들을 오름차순으로 출력
예시
입력: 60
출력: 2 2 3 5
입력: 3
출력: 3
접근 방법
초보자들은 보통 2부터 N까지 반복문을 돌며 확인하지만, N이 최대 10억일 때는 시간 초과 ...
6월 20일 06:12에 게시됨
RSA 암호화에서의 특정 취약점 분석 및 해독
RSA 암호화 시스템에서 발생하는 몇 가지 흥미로운 취약점을 분석하고 이를 이용해 암호문을 해독하는 방법을 살펴보겠습니다. 특히, 소인수 $p$와 $q$가 매우 가까운 경우를 다루는 기법에 초점을 맞춥니다.
취약점 분석: $p$와 $q$의 근접성
RSA의 공개키는 모듈러스 $n$과 공개 지수 $e$로 구성됩니다. 여기서 $n = p \times q$이며, $p$와 $q$는 큰 소수입니다. 만약 $ ...
6월 10일 20:51에 게시됨
약수 관련: 약수의 개수
N = (p1c1) * (p2c2) * ... * (pk^ck) 형태로 표현될 때
N2 = (p1(c12)) * (p2^ (c22)) * ... * (pk^ (ck*2)) 형태가 됩니다.
약수의 개수 f[N] = (c1+1)(c2+1)...(ck+1)
배수를 이용한 약수 개수 구하기
이 문제에서는 공식을 사용하지 않고, 약수를 구하는 대신 배수를 이용해 해결합니다.
#include <cstdio>
#include <cstring>
#include <iostream>
...
6월 2일 20:24에 게시됨