소인수분해

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

소인수분해(영어: 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와 같은 암호 알고리즘의 핵심적 부분이 된다.

고전적 알고리즘[편집]

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

알고리즘의 발전[편집]

암호학의 발달과 함께 소인수분해 방법도 발전해 왔으며 그중 유의미한 것을 간추리면 아래와 같다.

  • 타원 곡선에 의한 알고리즘(ECM)은 점근 속도로 이전의 잉여체의 성질을 이용한 알고리즘에 비해 매우 우수하다.
  • 수범위체(number field sieve) 알고리즘은 b가 합성수의 bit수일 때, 의 속도이며 범용 소인수분해 알고리즘에서 가장 우수하다.
  • 다중 다항식 이차체(multiple polynomial quadratic sieve : mpqs) 알고리즘
  • 이차 체

같이 보기[편집]

각주[편집]