소수판별법: 두 판 사이의 차이

을 만족하는 자연수 <math>a_p</math>가 A의 모든 소인수에 대하여 존재한다면 N은 소수가 된다. 만약 첫 번째 식의 값이 1이 아니거나 두 번째 식의 값이 1 또는 N이 아니라면 N은 합성수가 된다. 또한 브릴하트와 레머, 그리고 셀프리지는 A 부분이 <math>(N/2)^{\frac{1}{3}}</math>보다 커도 사용할 수 있는 개량된 알고리즘을 개발하였으며, 이 소수판별법과 [[쇼어 알고리즘|쇼어의 알고리즘]]을 [[양자 컴퓨터|양자컴퓨터]]에서 [[재귀]] 반복하여 사용한다면 어떤 수를 소인수분해하는 데 걸리는 시간은 <math>O((\log{n})^23(\log{\log{n}})^2(\log{\log{\log{n}}}))</math>이 된다.