확률적 알고리즘: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
잔글 →주석 |
잔글 여러번 → 여러 번 |
||
29번째 줄:
위와 같은 내용에서 소수 판별 문제가 Co-RP에 속하는 것을 알 수 있다.
합성수 ''n''보다 작은 임의의 수를 100번 선택하여 알고리즘을 실행시킨다면, 이런 '증거'를 못 찾을 확률은 (1/4)<sup>100</sup>이다. 그러므로 거의 대부분의 경우에서, 이와 같은 소수 판별법은 매우 좋은 알고리즘이라고 생각할 수 있다. 특히''n''이 아주 크다면, 이 방법 이외에는 효율적인 알고리즘이 없다. 알고리즘을
작은 확률로 오류가 발생하더라도 알고리즘을 조금만 주의해서 실행시키면 오류가 일어날 확률을 천문학적으로 작은 숫자만큼 줄일수 있기 때문에, 실제로 오류가 발생하는 것은 그다지 큰 문제가 되지 않는다. 실제로 결정론적으로 소수를 판별하는 다항시간 알고리즘이 [[AKS 소수 판별법|발견]]되었어도, 다양한 암호 관련 소프트웨어에서는 기존의 소수 판별법을 그대로 사용하고 있으며, 소수 판별 분야에서는 결정론적 알고리즘이 가까운 시일 안에 기존 확률적 알고리즘을 대체할 수는 없을 것으로 보인다.
| |||