소인수분해

위키백과, 우리 모두의 백과사전.
(소인수 분해에서 넘어옴)
둘러보기로 가기 검색하러 가기

소인수분해(영어: prime factorization, integer factorization)는 합성수소수의 곱으로 나타내는 방법을 말한다.

소인수분해를 일의적으로 결정하는 공식은 아직 발견되지 않았다. 현대 암호 처리에서 소인수분해의 어려움은 중요한 기준이 된다.

소인수분해[편집]

이 그림은 864의 소인수분해 과정을 그림으로 예시하고 있다. 소인수분해의 결과를 간단하게 쓰면 이 된다.

산술의 기본 정리(fundamental theorem of arithmetic)에 의해 모든 양의 정수는 소수들의 곱으로 표현하는 방법이 (곱의 순서를 바꾸는 것을 제외하면) 유일하게 존재한다. 그러나 산술의 기본정리는 그 소인수분해를 하는 방법을 알려주지는 않는다. 단지 존재성을 확인해 줄 뿐이다.

아래는 200 이하 합성수의 소인수분해이다.

  • 4=2×2
  • 6=2×3
  • 8=2×2×2
  • 9=3×3
  • 10=2×5
  • 12=2×2×3
  • 14=2×7
  • 15=3×5
  • 16=2×2×2×2
  • 18=2×3×3
  • 20=2×2×5
  • 21=3×7
  • 22=2×11
  • 24=2×2×2×3
  • 25=5×5
  • 26=2×13
  • 27=3×3×3
  • 28=2×2×7
  • 30=2×3×5
  • 32=2×2×2×2×2
  • 33=3×11
  • 34=2×17
  • 35=5×7
  • 36=2×2×3×3
  • 38=2×19
  • 39=3×13
  • 40=2×2×2×5
  • 42=2×3×7
  • 44=2×2×11
  • 45=3×3×5
  • 46=2×23
  • 48=2×2×2×2×3
  • 49=7×7
  • 50=2×5×5
  • 51=3×17
  • 52=2×2×13
  • 54=2×3×3×3
  • 55=5×11
  • 56=2×2×2×7
  • 57=3×19
  • 58=2×29
  • 60=2×2×3×5
  • 62=2×31
  • 63=3×3×7
  • 64=2×2×2×2×2×2
  • 65=5×13
  • 66=2×3×11
  • 68=2×2×17
  • 69=3×23
  • 70=2×5×7
  • 72=2×2×2×3×3
  • 74=2×37
  • 75=3×5×5
  • 76=2×2×19
  • 77=7×11
  • 78=2×3×13
  • 80=2×2×2×2×5
  • 81=3×3×3×3
  • 82=2×41
  • 84=2×2×3×7
  • 85=5×17
  • 86=2×43
  • 87=3×29
  • 88=2×2×2×11
  • 90=2×3×3×5
  • 91=7×13
  • 92=2×2×23
  • 93=3×31
  • 94=2×47
  • 95=5×19
  • 96=2×2×2×2×2×3
  • 98=2×7×7
  • 99=3×3×11
  • 100=2×2×5×5
  • 102=2×3×17
  • 104=2×2×2×13
  • 105=3×5×7
  • 106=2×53
  • 108=2×2×3×3×3
  • 110=2×5×11
  • 111=3×37
  • 112=2×2×2×2×7
  • 114=2×3×19
  • 115=5×23
  • 116=2×2×29
  • 117=3×3×13
  • 118=2×59
  • 119=7×17
  • 120=2×2×2×3×5
  • 121=11×11
  • 122=2×61
  • 123=3×41
  • 124=2×2×31
  • 125=5×5×5
  • 126=2×3×3×7
  • 128=2×2×2×2×2×2×2
  • 129=3×43
  • 130=2×5×13
  • 132=2×2×3×11
  • 133=7×19
  • 134=2×67
  • 135=3×3×3×5
  • 136=2×2×2×17
  • 138=2×3×23
  • 140=2×2×5×7
  • 141=3×47
  • 142=2×71
  • 143=11×13
  • 144=2×2×2×2×3×3
  • 145=5×29
  • 146=2×73
  • 147=3×7×7
  • 148=2×2×37
  • 150=2×3×5×5
  • 152=2×2×2×19
  • 153=3×3×17
  • 154=2×7×11
  • 155=5×31
  • 156=2×2×3×13
  • 158=2×79
  • 159=3×53
  • 160=2×2×2×2×2×5
  • 161=7×23
  • 162=2×3×3×3×3
  • 164=2×2×41
  • 165=3×5×11
  • 166=2×83
  • 168=2×2×2×3×7
  • 169=13×13
  • 170=2×5×17
  • 171=3×3×19
  • 172=2×2×43
  • 174=2×3×29
  • 175=5×5×7
  • 176=2×2×2×2×11
  • 177=3×59
  • 178=2×89
  • 180=2×2×3×3×5
  • 182=2×7×13
  • 183=3×61
  • 184=2×2×2×23
  • 185=5×37
  • 186=2×3×31
  • 187=11×17
  • 188=2×2×47
  • 189=3×3×3×7
  • 190=2×5×19
  • 192=2×2×2×2×2×2×3
  • 194=2×97
  • 195=3×5×13
  • 196=2×2×7×7
  • 198=2×3×3×11

소인수분해 알고리즘[편집]

현대의 전자기 기반 컴퓨터상에서 소인수분해에 대한 다항식 시간 알고리즘은 알려져 있지 않다. 단, 이론적인 양자컴퓨터에서의 다항식 시간 소인수분해 알고리즘 (쇼어의 알고리즘)은 존재한다. 하지만 아직까지 어떤 합성수를 다항 시간 안에 소인수분해하기는 어려운 문제이며, 예를 들어 193자리 수(RSA-640)는 5개월간 30개의 2.2 GHz 옵테론 CPU를 동원하여 소인수분해 되었다. 소인수분해의 난해함은 RSA와 같은 현대 암호의 핵심적 부분이 된다.

고전적 알고리즘[편집]

고전적인 소인수분해 알고리즘은 대부분 페르마의 소정리를 확장한 것을 이용한다. 그중 자주 사용되는 알고리즘은 아래와 같다.

알고리즘의 발전[편집]

암호학의 발달과 함께 소인수분해 방법도 발전해 왔으며 그중 가장 효율적인 알고리즘들을 간추리면 아래와 같다.

  • 타원 곡선 알고리즘 (Elliptic Curve Method, ECM)의 실행 시간은 로 이전의 잉여체의 성질을 이용한 알고리즘에 비해 매우 우수하다.
  • 수체 체(General Number Field Sieve, GNFS) 알고리즘은 b가 합성수의 비트수일 때, 의 속도를 가지며 현재까지 일반 컴퓨터로 실행시킬 수 있는 소인수분해 알고리즘 중에서 가장 우수하다.
  • 특수 수체 체 (Special Number Field Sieve, SNFS) 알고리즘은 r, e, s가 자연수일 때, re ± s 꼴인 자연수에 대해서 작동하는 알고리즘이다. 여기서 r, s의 값이 커지면 속도가 급속도로 느려지기 때문에 r, s가 작은 자연수에 대해서만 잘 작동하며 사용할 수 있다.
  • 다중 다항식 이차체 (Multiple Polynomial Quadratic Sieve, MPQS) 알고리즘
  • 이차 체 (Quadratic Sieve, QS) 알고리즘은 100자리 이하의 자연수를 소인수분해할 때 적합하며, 보통 어떤 합성수의 소인수들의 크기가 비슷할 때 잘 작동한다.

같이 보기[편집]