블럼 정수

수학에서 n = p×q가 3모드 4와 일치하는 p와 q가 구별되는 소수라면 자연수 n은 블럼 정수다.^[1]즉, 일부 정수 t에 대해 p와 q는 4t + 3 형식이어야 한다.이 형식의 정수를 블럼 프라임이라고 한다.^[2]이것은 블럼 정수의 요인이 가상의 부분이 없는 가우스 프리타임이라는 것을 의미한다.처음 몇 블럼 정수는

21, 33, 57, 69, 77, 93, 129, 133, 141, 161, 177, 201, 209, 213, 217, 237, 249, 253, 301, 309, 321, 329, 341, 381, 393, 413, 417, 437, 453, 469, 473, 489, 497, ... (sequence A016105 in the OEIS)

이 정수들은 컴퓨터 과학자 Manuel Blum의 이름을 따서 명명되었다.^{[citation needed]}

특성.

주어진 n = p×q a Blum 정수, Q_n 모든 2차 잔류물 modulo n과 coprime의 집합은 n과 ∈ Q이다_n.다음:^[2]

• a는 4개의 제곱근 modulo n을 가지고 있는데, 그 중 정확히 하나는 Q에도_n 있다.
• a_n in Q의 고유한 제곱근은 modulo n의 주 제곱근이라고 한다.
• f(x) = x mod² n에 의해 정의된 f: Q_n → Q_n 함수는 순열이다.f의 역함수는: f (x) = x mod^{((p − 1)(q − 1) + 4)/8} n이다.^[3]
• 모든 블럼 정수 n에 대해 -1은 자코비 기호 mod n이 +1이지만, -1은 n의 2차 잔류물이 아니다.

${\displaystyle \좌측 \frac {-1}{n1}\우측)=\좌측 \frac {-1}{p}\우측)\좌측 \frac {-1}{q}\우측)=(-1)^{2}=1}$

역사

MPQS, NFS와 같은 현대적인 팩토링 알고리즘이 개발되기 전에는 RSA moduli로 Blum 정수를 선택하는 것이 유용하다고 생각되었다.MPQS와 NFS는 무작위로 선택한 프리타임으로 구성된 RSA moduli와 동일한 용도의 블럼 정수를 고려할 수 있기 때문에 더 이상 유용한 예방 조치로 간주되지 않는다.^{[citation needed]}

참조