수학(mathematics)에서, 반-소수(semiprime)는 정확하게 두 개의 소수의 곱인 자연수입니다. 곱에서 두 소수는 서로 같을 수 있으므로, 반-소수는 소수의 제곱(squares)을 포함합니다. 소수가 무한하게 많이 있기 때문에, 역시 무한하게 많은 반-소수가 있습니다. 반-소수는 두-소수(biprimes)라고도 불립니다.
Examples and variations
100보다 작은 반-소수는 다음과 같습니다:
- 4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, and 95 (OEIS에서 수열 A001358)
제곱 숫자가 아닌 반-소수는 이산, 구별되는, 또는 제곱-없는 반-소수라고 불립니다:
- 6, 10, 14, 15, 21, 22, 26, 33, 34, 35, 38, 39, 46, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95, ... (OEIS에서 수열 A006881)
반-소수는 \(\displaystyle k\)-거의 소수(almost primes), 정확하게 \(\displaystyle k\) 소수 인수를 갖는 숫자의 경우 \(\displaystyle k=2\)입니다. 어쨌든 일부 출처는 "반-소수"를 더 큰 숫자의 집합, 많아야 두 개의 소수 인수 (단위 (1), 소수, 및 반-소수 포함)를 갖는 숫자를 참조하기 위해 사용합니다. 이것들은 다음과 같습니다:
- 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 25, 26, 29, 31, 33, 34, 35, 37, 38, 39, 41, 43, 46, 47, 49, ... (OEIS에서 수열 A037143)
Formula for number of semiprimes
반-소수 세는 형식은 2005년 E. Noel과 G. Panos에 의해 발견되었습니다. \(\displaystyle \pi_2(n)\)은 n보다 작거나 같은 반-소수의 개수를 나타낸다고 놓습니다. 그런-다음
\(\quad\displaystyle \pi_2(n) = \sum_{k=1}^{\pi (\sqrt n) } [\pi(n/p_k) - k + 1 ]\)
여기서 \(\displaystyle \pi(x)\)는 소수-세는 함수(prime-counting function)이고 \(\displaystyle p_k\)는 k-번째 소수를 나타냅니다.
Properties
반-소수는 자신 이외의 인수로 합성수(composite numbers)를 가지지 않습니다. 예를 들어, 숫자 26은 반-소수이고 유일한 인수는 1, 2, 13, 26이며, 이중 26만이 합성수입니다.
제곱-없는 반-소수 \(\displaystyle n=pq\) (\(\displaystyle p\ne q\) 포함)에 대해, 오일러의 토션트 함수(Euler's totient function) \(\displaystyle \varphi(n)\) (\(\displaystyle n\)과 상대적으로 소수(relatively prime)인 \(\displaystyle n\)보다 작거나 같은 양의 정수의 개수)의 값은 다음과 같은 간단한 형식을 취합니다:\(\displaystyle \varphi(n)=(p-1)(q-1)=n-(p+q)+1.\)
이 계산은 RSA 암호시스템(RSA cryptosystem)에서 반-소수의 적용의 중요한 부분입니다. 제곱 반-소수 \(\displaystyle n=p^2\)에 대해, 그 공식은 다시 다음과 같은 간단한 형식입니다:
\(\quad\displaystyle \varphi(n)=p(p-1)=n-p.\)
Applications
반-소수는 암호화와 숫자 이론 분야, 특히 RSA와 블룸 블룸 샤브(Blum Blum Shub)과 같은 유사-무작위 숫자 생성기(pseudorandom number generator)에서 사용되는 공개 키 암호화(public key cryptography) 분야에서 매우 유용합니다. 이들 방법은 두 개의 큰 소수를 찾아서 함께 곱하는 것 (결과적으로 반-소수가 됨)이 계산적으로 간단하지만, 원래 인수를 찾는 것은 어렵다는 사실에 의존합니다. RSA 인수화 도전(RSA Factoring Challenge)에서, RSA 보안(RSA Security)은 특정 큰 반-소수의 인수화에 대한 상을 제공했고 여러 상을 수상했습니다. 원래 RSA 인수화 도전은 1991년에 발행되었고, 2001년에 새로운 RSA 인수화 도전으로 대체되었으며, 나중에 2007년에 철회되었습니다.
1974년에, 아레시보 메시지(Arecibo message)는 성단(star cluster)을 겨냥한 무선 신호와 함께 전송되었습니다. 그것은 \(\displaystyle 23 \times 73\) 비트맵 이미지로 해석되도록 의도된 1679개의 이진 자릿수로 구성되었습니다. 숫자 \(\displaystyle 1679=23\cdot 73\)가 선택되었는데 왜냐하면 그것이 반-소수이고 따라서 오직 두 개의 구별되는 방법 (23행과 73열, 또는 73행과 23열)으로 직사각형 이미지로 배열할 수 있기 때문입니다.
References
- Sloane, N.J.A. (ed.). "Sequence A001358". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
- Stewart, Ian (2010). Professor Stewart's Cabinet of Mathematical Curiosities. Profile Books. p. 154. ISBN 9781847651280.
- Ishmukhametov, Sh. T.; Sharifullina, F. F. (2014). "On distribution of semiprime numbers". Russian Mathematics. 58 (8): 43–48. doi:10.3103/S1066369X14080052. MR 3306238. S2CID 122410656.
- French, John Homer (1889). Advanced Arithmetic for Secondary Schools. New York: Harper & Brothers. p. 53.
- Cozzens, Margaret; Miller, Steven J. (2013). The Mathematics of Encryption: An Elementary Introduction. Mathematical World. Vol. 29. American Mathematical Society. p. 237. ISBN 9780821883211.
- "The RSA Factoring Challenge is no longer active". RSA Laboratories. Archived from the original on 2013-07-27.
- du Sautoy, Marcus (2011). The Number Mysteries: A Mathematical Odyssey through Everyday Life. St. Martin's Press. p. 19. ISBN 9780230120280.
External links