0Pricing
Cryptology Academy · 강의

소수와 인수분해

소수가 공개 키 암호의 근간인 이유를 배웁니다.

소수와 인수분해은(는) CoddyKit의 무료 Cryptology Academy 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Cryptology Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Cryptology Academy 강의에는 총 4개의 강의가 포함되어 있습니다.

환영합니다

소수는 1과 자기 자신으로만 나누어지는 수입니다. 소수는 곱셈의 원자이며 RSA, Diffie-Hellman 및 여러 암호 시스템의 토대입니다.

정의와 예

소수: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ... 어떤 수의 양의 약수가 1과 자기 자신뿐이면 그 수는 소수입니다. 관례상 1은 NOT 소수입니다.

산술의 기본 정리

1보다 큰 모든 정수는 소수의 곱으로 정확히 한 가지 방식으로 소인수분해할 수 있습니다(순서는 제외). 60 = 2² × 3 × 5입니다. 이러한 유일성이 소인수분해 기반 암호를 가능하게 합니다.

시행 나눗셈

def is_prime(n): if n < 2: return False for i in range(2, int(n**0.5)+1): if n % i == 0: return False return True √n까지 확인하면 충분합니다. √n보다 작은 곳에서 약수가 발견되지 않으면 n은 소수입니다.

에라토스테네스의 체

N까지의 모든 소수를 찾으려면 2..N의 수 목록에서 시작합니다. 2의 배수를 지운 다음 3, 5 등의 배수를 차례로 지웁니다. 남은 수가 소수입니다. 실행 시간은 O(N log log N)입니다.

소수성 검사: 밀러-라빈

큰 수(2048비트)에서는 시행 나눗셈이 너무 느립니다. 밀러-라빈은 확률적 검사입니다. 40번 실행하면 오류가 발생할 확률은 < 4^(-40)입니다.

정수 소인수분해

n = p × q가 주어졌을 때 p와 q를 찾는 것이 정수 소인수분해 문제입니다. n이 2048비트라면 현재 알려진 최선의 알고리즘도 2^112번의 연산이 필요하므로 현재로서는 실행하기 어렵습니다.

RSA가 큰 소수 두 개를 사용하는 이유

RSA의 법 n = p × q입니다. n은 알지만 p와 q를 모르면 개인 키를 계산하기 어렵습니다. 보안은 전적으로 n을 소인수분해하기 어려운 성질에 의존합니다.

큰 소수 생성하기

from sympy import randprime p = randprime(2**1023, 2**1024) # random 1024-bit prime 절차: 무작위 홀수를 생성하고 밀러-라빈으로 검사한 뒤 소수가 될 때까지 반복합니다.

안전 소수와 강한 소수

안전 소수 p = 2q+1에서 q도 소수입니다. 안전 소수는 DH에 대한 특정 공격에 강합니다. RSA에서는 Pollard의 p-1 공격을 방지하기 위해 강한 소수를 사용하기도 합니다.

소수 간격과 무한성

유클리드는 300 BCE에 소수가 무한히 많다는 것을 증명했습니다. 쌍둥이 소수 추측(소수 p와 p+2가 무한히 존재한다는 추측)은 아직 증명되지 않았습니다. 암호에 사용할 소수는 결코 고갈되지 않습니다.

빠른 확인

RSA는 왜 큰 소수를 사용합니까?

복습

소수와 소인수분해를 이해하셨습니다. 다음에는 오일러의 피 함수와 GCD를 적용해 RSA에 필요한 마지막 수학 도구를 익히겠습니다.

자주 묻는 질문

“소수와 인수분해” 강의는 무료인가요?

네 — “소수와 인수분해” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Cryptology Academy 강의 전체를 잠금 해제할 수 있습니다. Cryptology Academy 강의에는 총 4개의 강의가 포함되어 있습니다.

“소수와 인수분해”에서 뭘 배우나요?

소수가 공개 키 암호의 근간인 이유를 배웁니다. 브라우저에서 직접 실행하는 실습 코드로 Cryptology Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.

Cryptology Academy을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 Cryptology Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.

“소수와 인수분해” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

이 Cryptology Academy 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 Cryptology Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

이 강의의 모든 강의

  1. 이진수 및 16진수 기초
  2. 모듈러 산술 기초
  3. 소수와 인수분해
  4. GCD, 오일러의 토션트 및 정수론 입문
← Cryptology Academy(으)로 돌아가기