"소수 (prime number)"의 두 판 사이의 차이

2023년 8월 27일 (일) 16:50 기준 최신판

소수(素數, prime number)는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수를 의미한다. 예를 들어, 자연수 2, 3, 5의 약수는 1과 자기 자신뿐이기 때문에 자연수 2, 3, 5는 소수라고 할 수 있다. 0.1, 0.2, 0.3 등과 같은 소수(小數)와 구별하기 위해 소쑤라고 읽고, 솟수라고 쓰기도 한다. 소수를 곱하여 여러 합성수를 만들 수 있기 때문에, 모든 수의 '씨앗'이라는 뜻에서, 소수를 씨수라고 부르기도 한다.영어로는 프라임 넘버(prime number)라고 한다. 소수의 반대말은 합성수이다.

개요[편집]

소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. 예를 들어, 5는 1x5 또는 5x1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다. 그러나 6은 자신보다 작은 두 숫자(2×3)의 곱이므로 소수가 아닌데, 이렇듯 1보다 큰 자연수 중 소수가 아닌 것은 합성수라고 한다. 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의하기도 한다. 산술의 기본 정리의 '1보다 큰 모든 자연수는 그 자체가 소수이거나, 순서를 무시하고 유일한 소인수의 조합을 갖는다'는 내용을 바탕으로 정수론에서는 매우 중요한 주제로 다루어진다. 또한 현대에는 암호 분야에서의 기술적 사용으로 그 중요성이 부각되고 있다. 소수의 개수는 무한하며, 이는 유클리드의 정리에 의하여 최초로 논증되었다. 소수와 합성수를 구분해낼 수 있는 명확한 공식은 지금까지도 밝혀지지 않은 상태이나, 대역적으로 자연수 중 소수의 비율의 근사치를 예측하는 모델로는 여러가지가 알려져 있다. 이러한 방향으로의 연구의 첫 결과는 19세기 말에 증명된 소수 정리인데, 이는 무작위로 선택된 한 수가 소수일 확률은 그 수의 자릿수, 곧 로그값에 반비례함을 알려준다.^[1]

역사[편집]

유클리드(Euclid)

페르마(Pierre de Feramt)

마린
메르센느(Marin Mersenne)

오일러(Leonhard Euler)

르장드르(Adrien-Marie Legendre)

유클리드(Euclid)

이집트인들의 기록을 살펴보자면 그들이 소수에 대한 약간에 지식이 있었던 것으로 보인다. 예를 들어, 린드파피루스(Rhind papyrus)에는 여러 가지 소수들과 합성 수 들이 쓰여 있었다. 그러나 실질적으로 소수에 관한 연구가 시작된 것은 고대 그리스부터였다. 유클리드가 저술한 원론(기원전 300년)에서는 몇 가지 기본적이고 중요한 증명들이 있는데 예를 들면 소수의 무한성도 그중 하나였다. 또한 유클리드는 메르센 소수(Mersenne prime)로 부터 어떻게 완전수를 만들 수 있는지도 보였다. 에라토스테네스(Eratosthenes)가 고안한 에라토스테네스 체(Sieve of Eratosthenes)는 소수를 찾기에는 가장 간단한 방법이지만 현재 큰 소수를 찾는 컴퓨터는 이 알고리즘을 택하지 않는다. 그리스 이후 17세기까지 소수에 관한 연구는 큰 진보를 하지 않았다.

페르마

1640년 피에르 데 페르마(Pierre de Fermat)는 그의 이름이 붙은 수많은 정리를 남겼는데, 그중 페르마의 소정리(Fermat's little theorem)는 어떤 수가 소수일 간단한 필요 조건에 대한 정리이다. 페르마는 이 정리를 언급했을 뿐, 정확한 증명을 제시하지 않았으며 후에 라이프니츠(Leibnitz)와 오일러(Euler)에 의해 증명되었다. 참고로 페르마 소정리의 특정 부분은 훨씬 전부터 중국에서도 알려져 있었다. 페르마는

n=4

일 때 까지를 검토해 본 후 모든 2^2ⁿ+1 꼴의 수는 소수일 것으로 추측하였으나 그 54번째 페르마 수인

2^{32}+1

은, 오일러에 의해 641의 배수임이 밝혀졌다.

마린 메르센느(Marin Mersenne)

2^{p}-1

꼴의 소수(p는 소수)는 해당 소수를 연구했던 17세기 프랑스 수학자 마린 메르센느(Marin Mersenne)의 공로에 따라 메르센 소수(Mersenne prime)라는 이름이 붙여졌다. 이는 2의 거듭제곱에서 1을 뺀 수가 소수일 때를 말한다.즉 메르센 소수는

Mp=2^{p}-1

을 만족하는 소수이며, 예를 들어 2²-1=3, 2³-1=7, 2⁵-1=31 등이 해당한다.

오일러(Leonhard Euler)

오일러의 정수에 대한 연구는 소수에 대해 많은 결과를 낳았는데, 그는

{\frac {1}{2}}

+

{\frac {1}{3}}

+

{\frac {1}{5}}

+

{\frac {1}{7}}

+

{\frac {1}{11}}

+ ··· 와 같은 형태의 무한 급수가 발산함을 보여, 소수가 무한함을 유클리드와는 다른 방식으로 증명하였다. 또한 오일러는 2^p-1(2^p-1) 꼴의 수 (이 때, 두번째 항은 메르센느 소수) 들이 모두 유일한 짝수 완전수 꼴 임을 보였다. 하지만 현재까지도 홀수 완전수가 존재하는지 존재하지 않는지에 대한 어떠한 증명도 발견되지 않고 있다.

르장드르(Adrien-Marie Legendre)

19세기 초에, 르장드르(Legendre)와 가우스(Gauss)는 독립적으로

x

가 무한대로 발산할 때,

x

보다 작은 소수의 개수는

x/log(x)

와 같다는 사실을 발견하였다. 1859년에 리만은 그의 논문에서 제타 함수(zeta-function)에 대한 아이디어를 선보였다. 리만의 아이디어를 이용하여 1896년 아다마르(Hadamard)와 발레푸생(Vallée-Poussin)은 독립적으로 소수 정리를 증명하였다. 이 후 수학자들은 매우 큰 수에 대하여, 이 수가 소수인지 아닌지 판단할 방법을 모색했다. 이에 따라 1877년에는 페르마 소수들을 위한 Pépin's 테스트, 1878년엔 Proth의 정리, 1856년엔 메르센느 소수들을 위한 Lucas–Lehmer 테스트 등이 발견되었다. 현대에 가장 많이 쓰이는 알고리즘으로는 APRT-CL, ECPP, AKS 등이 있지만 여전히 더 나은 알고리즘을 찾기 위해 많은 수학자가 노력하고 있다. 오랜 시간동안 소수는 순수 수학 외에는 아무 쓸모가 없다고 판단되었으나, 1970년 발명된 RSA 암호 방식을 통해 소수에 대한 생각이 완전히 바뀌게 되었다. ^[2]

종류[편집]

균형잡힌 소수(Balanced primes)

그 전 소수와 그 다음 소수의 평균이 소수가 되는 수. 즉, 소수들만 모아놓은 수열

{p_{n}}

이 있을 때,

p_{n}={{p_{n-1}+p_{n+1}} \over 2}

을 만족하는 소수

p_{n}

을 균형잡힌 소수라 한다. 예를 들어, 소수 53은 그 전 소수 47과 그 다음 소수 59의 평균이므로 균형잡힌 소수이다. (OEIS의 A006562 번 수열에서 확인 할 수 있다.) 균형잡힌 소수들의 종류로는 5, 53, 157, 173, 211, 257, 263, 373, 563, 593, 607, 653, 733, 947, 977, 1103, 1123, 1187, 1223, 1367, 1511, 1747, 1753, 1907, 2287, 2417, 2677, 2903, 2963, 3307, 3313, 3637, 3733 등이 있다.

벨 수 소수(Bell number primes)

벨 수는, 수학자 에릭 템플 벨(Eric Temple Bell)의 이름에서 따온 것으로, 조합론에서 n 개의 원소로 구성된 집합을 분할하는 방법을 나타내며, 몇 가지 벨 수는 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975 등이 있다. 이때, 이 벨 수 들 중에서 소수인 것들을 벨 수 소수라 한다. 처음 몇 벨 수 소수로는 2, 5, 877, 27644437, 35742549198872617291353508656626642567, 359334085968622831041960188598043661065388726959079837 등이 있으며, 이는 OEIS 의 A051130 번 수열에서 찾을 수 있다.

캐럴 소수(Carol primes)

캐럴 소수는

(2^{n}-1)^{2}-2

식을 만족하는 소수이다. 캐럴 소수로는 7, 47, 223, 3967, 16127, 1046527, 16769023, 1073676287, 68718952447, 274876858367, 4398042316799, 1125899839733759, 18014398241046527 등이 있다.

중앙 십각 소수(Centered decagonal primes)

(5(n^{2}-n))+1

을 만족하는 소수다. 다음 식만 만족하는 수들은 1, 11, 31, 61, 101, 151, 211, 281, 361, 451, 551, 661, 781, 911, 1051, 등이 있으며, 이 들 중, 소수인 것을 바로 십각 수(Centered decagonal number)라 한다. 이 십각 수의 특징은 가운데 구슬이 하나 있고, 그 주위를 10각형이, 그 주위를 20각형이... 이렇게 둘러 쌓아 나아가는 수이다. 중앙 십각 소수는 11, 31, 61, 101, 151, 211, 281, 661, 911, 1051, 1201, 1361, 1531, 1901, 2311, 2531, 3001, 3251, 3511, 4651, 5281, 6301, 6661, 7411, 9461, 9901, 12251, 13781, 14851, 15401, 18301, 18911, 19531 등이 있다.

칠각 소수(Centered heptagonal primes)

이는 위 중앙 십각 소수와 비슷하지만, 칠각형으로 둘러 쌓아나간다는 점이 다르다. 칠각 수는

(7n^{2}-7n+2)/2

식을 만족하는 수를 가리키며, 이들 중 소수들을 칠각 소수라 한다. 칠각 소수는 43, 71, 197, 463, 547, 953, 1471, 1933, 2647, 2843, 3697, 4663, 5741, 8233, 9283, 10781, 11173, 12391, 14561, 18397, 20483, 29303, 29947, 34651, 37493, 41203, 46691 등이 있다.

사각 소수(Centered square primes)

십각 소수나 칠각 소수와 같지만, 이는 사각형으로 둘러 쌓아나간다는 점이 다르며

n^{2}+(n+1)^{2}

의 공식을 만족하는 소수이다. 사각 소수는 5, 13, 41, 61, 113, 181, 313, 421, 613, 761, 1013, 1201, 1301, 1741, 1861, 2113, 2381, 2521, 3121, 3613, 4513, 5101, 7321, 8581, 9661, 9941, 10513, 12641, 13613, 14281, 14621 이 있다.

삼각 소수(Centered triangular primes)

한 점을 중심으로 삼각형으로 덮어 나갈 때, 만족하는 점의 개수를 삼각수라고 하고, 이 삼각수 중에 소수가 되는 수를 삼각 소수라 할 때, 이는

(3n^{2}+3n+2)/2

의 공식을 만족한다. 삼각 소수는 19, 31, 109, 199, 409, 571, 631, 829, 1489, 1999, 2341, 2971, 3529, 4621, 4789, 7039, 7669, 8779, 9721, 10459, 10711, 13681, 14851, 16069, 16381, 17659, 20011, 20359, 23251 등이 있다.^[3]

특징[편집]

소수는 1보다 큰 자연수이다. 즉, 1은 소수가 아니다.
소수의 약수는 1과 자기 자신뿐이다. 즉, 소수의 약수는 2개뿐이며, 역도 성립한다.
2는 소수이지만, 2를 제외한 모든 짝수는 2를 약수로 가지므로 소수가 아니다.
2, 3을 제외한 모든 소수는 자연수 n에 대해 $6n-1$ 혹은 $6n+1$ 꼴이다. 역은 성립하지 않는다.^[4]

예제[편집]

에라토스테네스의 체(Sieve of Eratosthenes)

1~100까지의 모든 소수를 구한다고 가정했을 때,

1은 제거
지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.
지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.
지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다.
지워지지 않은 수 중 제일 작은 7을 소수로 채택하고, 나머지 7의 배수를 모두 지운다.
지워지지 않고 남은 수는 전부 소수이다.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	~~100~~

C++

void getChe(int num) {
   int *arr;
   arr = (int *)malloc(sizeof(int) * num);
   int i = 2;

   // 입력받은 수 만큼 배열에 모두 초기화 해둔다.

   for (i = 2; i <= num; i++) {
       arr[i] = i;
   }
   
   for (i = 2; i <= num; i++) { 
       if (arr[i] == 0) // 이미 체크된 수의 배수는 확인하지 않는다.
           continue;
       for (int j = i + i; j <= num; j += i) { // i를 제외한 i의 배수들은 0으로 체크
           arr[j] = 0;
       }
   }

   // 출력

   for (i = 2; i <= num; i++) {
       if (arr[i] != 0)
           cout << arr[i] << " ";
   }
}^[5]

자바(Java)

public class PrimeNumber1 {	
  public static void getPrime(int num, ArrayList<Integer> prime) {
    prime.add(2); 
	
    for (int i = 2; i <= num; i++) {
      for (int j = 0; prime.size() > j; j++) {
        if (i % prime.get(j) == 0) break; // 소수가 아닌 경우 pass
			
        if (j + 1 == prime.size()) // 소수일 때
             prime.add(i);
        }
     }
	
     for (Integer result : prime) {
         System.out.println(result);
     }
  }

  public static void main(String[] args) {
     ArrayList<Integer> prime = new ArrayList<Integer>();

     long start = System.currentTimeMillis();
     getPrime(30000, prime);
     long end = System.currentTimeMillis();
     System.out.println("수행시간 : " + (end - start));
  }
}^[6]

파이썬(Python)

n=1000
a = [False,False] + [True]*(n-1)
primes=[]

for i in range(2,n+1): 
  if a[i]:
    primes.append(i)
    for j in range(2*i, n+1, i):
        a[j] = False
print(primes)^[5]

각주[편집]

↑ 〈소수 (수론)〉, 《위키백과》
↑ jjycjn, 〈소수(Prime number) 이야기〉, 《티스토리》, 2016-09-09
↑ Psi, 〈여러 가지 소수(Prime number)들〉, 《티스토리》, 2007-12-28
↑ 김동이, 〈정수론〉, 《오픈튜토리얼스》, 2015-04-09
↑ ^5.0 ^5.1 신매력, 〈(C++) 소수 구하기 최적의 알고리즘 (2) - 에라토스테네스의 체〉, 《티스토리》, 2013-09-29
↑ 신매력, 〈(JAVA) 소수 구하기 최적의 알고리즘 (1)〉, 《티스토리》, 2013-09-20

참고자료[편집]

〈소수 (수론)〉, 《위키백과》</ref>
수학방 공식 홈페이지 - https://mathbang.net/199
김동이, 〈정수론〉, 《오픈튜토리얼스》, 2015-04-09
〈2. 소수 구하기 - 에라토스테네스의 체〉, 《위키독스》
신매력, 〈(C++) 소수 구하기 최적의 알고리즘 (2) - 에라토스테네스의 체〉, 《티스토리》, 2013-09-29
신매력, 〈(JAVA) 소수 구하기 최적의 알고리즘 (1)〉, 《티스토리》, 2013-09-20
jjycjn, 〈소수(Prime number) 이야기〉, 《티스토리》, 2016-09-09
Psi, 〈여러 가지 소수(Prime number)들〉, 《티스토리》, 2007-12-28

같이 보기[편집]

이 소수 (prime number) 문서는 수학에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

일반 : 자연, 생물, 동물, 식물, 정치, 군사, 경제, 사회, 교육, 문화, 예술, 스포츠, 역사, 역사인물, 인간, 인체, 건강, 정신, 성격, 행동, 언어, 수학 ^□^■^⊕, 위키 도움말

수학	IMO • KMO • 공리 • 그래프이론 • 기하학 • 대수기하학 • 대수학 • 산수 • 산학 • 선형대수학 • 수식 • 수학 • 수학경시대회 • 수학자 • 양 • 위상수학 • 응용수학 • 이산수학 • 조합론 • 집합론 • 필즈상 • 해석학 • 도움말:수학

수	0 • 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 경(10¹⁶) • 공배수 • 공약수 • 구(10³²) • 구골(10¹⁰⁰) • 구골뱅 • 구골플렉스 • 구골플렉시안 • 그레이엄수(G⁶⁴(4)) • 기수 • 로마숫자 • 만 • 무량대수(10⁶⁸) • 무리수 • 무한대(∞) • 무한소 • 배수 • 백 • 벡터 • 복소수 • 부동소수점 • 분모 • 분수 • 분자 • 사원수 • 서수 • 소수 (decimal) • 소수 (prime number) • 소수점 • 수 • 숫자 • 스칼라 • 승수 • 실수 • 십진수 • 아라비아숫자 • 약수 • 양(10²⁸) • 양수 • 억 • 원주율(π) • 유리수 • 음수 • 이진수 • 자(10²⁴) • 자연로그의 밑(e) • 자연수 • 정수 • 조(10¹²) • 지수 • 천 • 합성수 • 해(10²⁰) • 허수(i) • 황금비(φ)

계산	! • ↑ • cos • f(x) • lim • log • sin • tan • ∑ • ∫ • 가감승제 • 값 • 결합법칙 • 계산 • 곱 • 곱셈 • 곱하기 • 공식 • 교환법칙 • 구간 • 구구단 • 극한 • 근 • 근사값 • 나누기 • 나눗셈 • 나머지 • 난이도 • 내림 • 다항식 • 답 • 더하기 • 덧셈 • 도함수 • 독립변수 • 등식 • 라마누잔합 • 로그 • 루트(√) • 리만가설 • 몫 • 무한급수 • 미분 • 미적분 • 미지수 • 반올림 • 발산 • 방정식 • 백분율 • 변수 • 부등식 • 분배법칙 • 비례식 • 비율 • 빼기 • 뺄셈 • 사칙연산 • 산수 • 삼각함수 • 삼차방정식 • 상수 • 상용로그 • 셈 • 수렴 • 수열 • 시그모이드 함수 • 식 • 약분 • 역수 • 역함수 • 역행렬 • 연산 • 오일러 공식 • 오일러 등식 • 올림 • 이차방정식 • 인수 (수학) • 인수분해 • 자연로그 • 적분 • 전개 • 정답 • 정리 • 정의역 • 제곱 • 제곱근 • 종속변수 • 증명 • 지수 • 차수 • 천분율 • 치역 • 퍼센트(%) • 풀이 • 피타고라스 정리 • 함수 • 합 • 항 • 항등식 • 해 • 행렬

도형	각도 • 각뿔 • 곡면 • 곡선 • 구 • 그래프 • 길이 • 내심 • 넓이 • 높이 • 다각형 • 다면체 • 도형 • 둔각 • 둘레 • 마름모 • 면 • 면적 • 무게중심 • 반경 • 반구 • 반원 • 반지름 • 방심 • 변 • 부피 • 빗변 • 사각뿔 • 사각형 • 사다리꼴 • 삼각뿔 • 삼각형 • 선 • 선분 • 수심 • 쌍곡선 • 예각 • 오각형 • 외심 • 원 • 원기둥(원통) • 원뿔 • 원환체(도넛모양) • 육각형 • 이등변삼각형 • 입체 • 점 • 점선 • 정사각형 • 정사면체 • 정삼각형 • 정오각형 • 정육각형 • 정육면체 • 정팔각형 • 정팔면체 • 좌표 • 좌표계 • 좌표축 • 좌표평면 • 중첩 • 지름 • 직각 • 직경 • 직사각형 • 직선 • 직육면체 • 차원 • 초입방체(하이퍼큐브) • 축 • 타원 • 테서랙트 • 텐서 • 팔각형 • 평면 • 평행사변형 • 포물선 • 호

집합	공집합(Ø) • 교집합(∩) • 무한집합 • 벤 다이어그램 • 부분집합(⊂) • 알레프수(ℵ) • 여집합 • 원소 • 유한집합 • 전체집합 • 집합 • 차집합 • 합집합(∪)

통계	경우의 수 • 기댓값 • 기하평균 • 모분산 • 모집단 • 모평균 • 분산 • 분포 • 사건 • 산술평균 • 산포도 • 상관관계 • 순열 • 신뢰구간 • 신뢰도 • 유의수준 • 전수조사 • 정규분포 • 조합 • 조화평균 • 중앙값 • 통계 • 통계학 • 편차 • 평균 • 표본 • 표본분산 • 표본조사 • 표본평균 • 표준편차(σ) • 최빈값 • 합계 • 확률 • 확률밀도함수 • 회귀분석

수학자	갈릴레오 갈릴레이 • 게오르크 칸토어 • 고트프리트 빌헬름 라이프니츠 • 니콜로 폰타나(타르탈리아) • 다비트 힐베르트 • 레오나르도 피보나치 • 레온하르트 오일러 • 로널드 그레이엄 • 르네 데카르트 • 버트런드 러셀 • 베르너 하이젠베르크 • 베른하르트 리만 • 브룩 테일러 • 블레즈 파스칼 • 스리니바사 라마누잔 • 아르키메데스 • 아이작 뉴턴 • 알콰리즈미 • 앙리 푸앵카레 • 오거스터스 드 모르간 • 요하네스 케플러 • 요한 베르누이 • 유클리드(에우클레이데스) • 유휘 • 이순지 • 이임학 • 조제프-루이 라그랑주 • 조지 불 • 존 내시 • 존 네이피어 • 존 월리스 • 존 폰 노이만 • 지롤라모 카르다노 • 최석정 • 카를 프리드리히 가우스 • 토머스 베이즈 • 피에르 드 페르마 • 피타고라스 • 헤론 • 홍정하 • 히파르코스

기타	IMO • KMO • 국제수학연맹 • 세계수학자대회 • 올림피아드 • 필즈상

위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘^□^■^⊕, 알고리즘, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스

암호기술	개인키 • 경량암호 • 다자간 계산(MPC) • 다중서명(멀티시그) • 동형암호 • 디지털서명 • 링서명 • 배타적 논리합(XOR) • 복호화 • 블랙박스 암호 • 서명 • 소수 • 소인수분해 • 슈노르서명 • 스케인 • 스키테일 • 스테가노그래피 • 안전한 다자간 계산(SMPC) • 암호 • 암호경제학 • 암호문 • 암호키 • 암호학 • 암호화 • 이산로그 • 전자봉투 • 전자서명 • 전치암호 • 종단간 암호화 • 치환암호(대체암호) • 키 • 패딩 • 패스워드 • 평문 • 합성수 • 해독 • 해시 • 형태보존암호 • 혼돈 • 화이트박스 암호 • 확산

논리연산	논리곱(AND) • 논리연산 • 논리합(OR) • 배타적 논리합(XOR) • 부울곱 • 부울대수 • 부울합 • 부정논리곱(NAND) • 부정논리합(NOR) • 부정연산(NOT)

SHA	SHA • SHA0 • SHA1 • SHA2 • SHA224 • SHA256 • SHA384 • SHA512 • SHA512/224 • SHA512/256 • SHA3 • SHA3-224 • SHA3-256 • SHA3-384 • SHA3-512

MD	MD • MD2 • MD4 • MD5 • RIPEMD • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320

기타 해시	CRC-16 • CRC-32 • CRC-64 • Keccak-256 • Keccak-384 • Keccak-512 • Shake-128 • Shake-256 • 베이스32 • 베이스32 파일 • 베이스58 • 베이스64 • 베이스64 파일 • 순환중복검사

대칭키	AES • ARIA(아리아) • DES • HIGHT(하이트) • LEA • SEED(시드) • 대칭키 • 대칭키 암호 알고리즘 • 디피-헬만 • 디피-헬만 키교환 • 레인달 • 블로피시 • 블록암호 • 스트림 암호 • 에스박스(S-Box) • 트리플 DES

비대칭키	PKI • RSA • 공개키 • 공개키 암호 알고리즘 • 비대칭키 • 엘가말 • 타원곡선 • 타원곡선 디지털서명 알고리즘 • 타원곡선암호

영지식증명	영지식 상호 증명(ZKIP) • 영지식 스나크 • 영지식 스타크 • 영지식증명

양자암호	BB84 프로토콜 • E91 프로토콜 • B92 프로토콜 • 비밀키 오류율 • 안전성 증명 • 양자난수생성기 • 양자내성암호 • 양자암호 • 양자얽힘 • 양자역학 • 양자중첩 • 양자컴퓨터 • 양자키 • 양자키분배 • 양자통신 • 연속 변수 프로토콜

암호해독	기지평문공격(KPA) • 선택암호문공격(CCA) • 선택평문공격(CPA) • 암호공격 • 암호문 단독공격(COA) • 암호해독

암호학 인물	라이언 플레이페어 • 레너드 애들먼 • 로널드 리베스트 • 마틴 헬만 • 블레즈 드 비즈네르 • 아디 샤미르 • 앨런 튜링 • 웨슬리 피터슨 • 찰스 휘트스톤 • 휫필드 디피

위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반

[1] 〈소수 (수론)〉, 《위키백과》

[2] ycjn, 〈소수(Prime number) 이야기〉, 《티스토리》, 2016-09-09

[3] Psi, 〈여러 가지 소수(Prime number)들〉, 《티스토리》, 2007-12-28

[4] 김동이, 〈정수론〉, 《오픈튜토리얼스》, 2015-04-09

[.EC.97.90.EB.9D.BC.ED.86.A0.EC.8A.A4.ED.85.8C.EB.84.A4.EC.8A.A4.EC.9D.98_.EC.B2.B4-5] 5.0 ^5.1 신매력, 〈(C++) 소수 구하기 최적의 알고리즘 (2) - 에라토스테네스의 체〉, 《티스토리》, 2013-09-29

[6] 신매력, 〈(JAVA) 소수 구하기 최적의 알고리즘 (1)〉, 《티스토리》, 2013-09-20

[1]

[2]

[3]

[4]

[5]

[6]

@@ 1번째 줄: / 1번째 줄: @@
-'''소수'''(素數, prime number)는 <!--소 수, 소쑤, 솟수, 씨수, prime number-->자신보다 작은 두 개의 [[자연수]]를 곱하여 만들 수 없는 1보다 큰 자연수를 의미한다. 예를 들어, 자연수 2, 3, 5의 [[약수]]는 1과 자기 자신뿐이기 때문에 자연수 2, 3, 5는 소수라고 할 수 있다. 0.1, 0.2, 0.3 등과 같은 소수(小數)와 구별하기 위해 '''소쑤'''라고 읽고, '''솟수'''라고 쓰기도 한다. 북한에서는 '''씨수'''라고 한다. 영어로는 '''프라임 넘버'''(prime number)라고 한다.
+'''소수'''(素數, prime number)는 <!--소 수, 소쑤, 솟수, 씨수, prime number-->자신보다 작은 두 개의 [[자연수]]를 곱하여 만들 수 없는 1보다 큰 자연수를 의미한다. 예를 들어, 자연수 2, 3, 5의 [[약수]]는 1과 자기 자신뿐이기 때문에 자연수 2, 3, 5는 소수라고 할 수 있다. 0.1, 0.2, 0.3 등과 같은 소수(小數)와 구별하기 위해 '''소쑤'''라고 읽고, '''솟수'''라고 쓰기도 한다. 소수를 곱하여 여러 [[합성수]]를 만들 수 있기 때문에, 모든 수의 '씨앗'이라는 뜻에서, 소수를 '''씨수'''라고 부르기도 한다.영어로는 '''프라임 넘버'''(prime number)라고 한다. 소수의 반대말은 [[합성수]]이다.
 ==개요==
-소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. 예를 들어, 5는 1x5 또는 5x1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다. 그러나 6은 자신보다 작은 두 숫자(2×3)의 곱이므로 소수가 아닌데, 이렇듯 1보다 큰 자연수 중 소수가 아닌 것은 합성수라고 한다. 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의하기도 한다. 산술의 기본 정리의 '1보다 큰 모든 자연수는 그 자체가 소수이거나, 순서를 무시하고 유일한 소인수의 조합을 갖는다'는 내용을 바탕으로 정수론에서는 매우 중요한 주제로 다루어진다. 또한 현대에는 암호 분야에서의 기술적 사용으로 그 중요성이 부각되고 있다. 소수의 개수는 무한하며, 이는 유클리드의 정리에 의하여 최초로 논증되었다. 소수와 합성수를 구분해낼 수 있는 명확한 공식은 지금까지도 밝혀지지 않은 상태이나, 대역적으로 자연수 중 소수의 비율의 근사치를 예측하는 모델로는 여러가지가 알려져 있다. 이러한 방향으로의 연구의 첫 결과는 19세기 말에 증명된 소수 정리인데, 이는 무작위로 선택된 한 수가 소수일 확률은 그 수의 자릿수, 곧 로그값에 반비례함을 알려준다.<ref>〈[https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_(%EC%88%98%EB%A1%A0) 소수 (수론)]〉, 《위키백과》</ref>
+소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. 예를 들어, 5는 1x5 또는 5x1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다. 그러나 6은 자신보다 작은 두 숫자(2×3)의 곱이므로 소수가 아닌데, 이렇듯 1보다 큰 자연수 중 소수가 아닌 것은 [[합성수]]라고 한다. 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의하기도 한다. 산술의 기본 정리의 '1보다 큰 모든 자연수는 그 자체가 소수이거나, 순서를 무시하고 유일한 소인수의 조합을 갖는다'는 내용을 바탕으로 정수론에서는 매우 중요한 주제로 다루어진다. 또한 현대에는 암호 분야에서의 기술적 사용으로 그 중요성이 부각되고 있다. 소수의 개수는 무한하며, 이는 유클리드의 정리에 의하여 최초로 논증되었다. 소수와 [[합성수]]를 구분해낼 수 있는 명확한 공식은 지금까지도 밝혀지지 않은 상태이나, 대역적으로 자연수 중 소수의 비율의 근사치를 예측하는 모델로는 여러가지가 알려져 있다. 이러한 방향으로의 연구의 첫 결과는 19세기 말에 증명된 소수 정리인데, 이는 무작위로 선택된 한 수가 소수일 확률은 그 수의 자릿수, 곧 로그값에 반비례함을 알려준다.<ref>〈[https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_(%EC%88%98%EB%A1%A0) 소수 (수론)]〉, 《위키백과》</ref>
 ==역사==
@@ 168번째 줄: / 168번째 줄: @@
 ==같이 보기==
+* [[합성수]]
 * [[자연수]]
 * [[약수]]
 * [[소인수분해]]
+* [[소수 (decimal)]]
 * [[알고리즘]]
 * [[C++]]
@@ 177번째 줄: / 179번째 줄: @@
 * [[에라토스테네스]]
 * [[유클리드]]
+* [[소수]]
-{{암호 알고리즘|검토 필요}}
+{{수|검토 필요}}
+{{암호 알고리즘}}

위키원

이름공간

변수

보기

더 보기

검색