바흐 알고리즘

이 기사는 주요 출처에 대한 언급에 너무 많이 의존하고 있다. 이차 또는 3차 소스를 추가하여 개선하십시오.(2021년 8월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

바흐의 알고리즘은^[1] 그 발견자인 에릭 바흐의 이름을 따서 그 인자화와 함께 난수를 생성하기 위한 확률론적 다항식 시간 알고리즘이다.숫자를 효율적으로 인자로 하는 알고리즘이 알려져 있지 않기 때문에, 즉, 난수를 생성하여 인자로 만드는 간단한 방법은 비현실적이기 때문에 관심이 있다.

알고리즘은 예상대로 O(log n) 원시성 테스트를 수행한다.

단순하지만 효율성이 떨어지는 알고리즘($성능{\displaystyle }$, 기대치, O${\displaystyle ({log\mathrm{}}^{}}$ 2${\displaystyle {}^{}\mathrm{nn}}$ ${\displaystyle )}$ ${\displaystyle O(\log ^{2$}n$)}$ 원시성$$ 테스트)는 Adam Kalai 때문이다.^[2]

개요

이 절은 출처를 인용하지 않는다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 섹션을 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다.(2020년 6월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

바흐의 알고리즘은 요인화와 함께 / < N $[\displaystyle N/2<x\leq$ N$}($주어진 입력 $N{\displaystyle }$ ${\displaystyle N}$의 경우)$$ 범위에서 숫자 x {\$displaystyle$ x$}$를 균일하게$$ 생성한다.이것은 특정 분포에 ${\displaystyle {따라}^{}}$ p ${\displaystyle {}^{}}$ N ${\displaystyle p$$}$과(와) p $p{\displaystyle }$ ${\displaystyle N}$$${\$displaystyle p$$^{a}\leq$ N$}$과$($와) 같은 prime number p ${\$displaystyle a$}$을(를) 선택하여 이루어진다.이 알고리즘 다음 재귀적으로 있다. 그리고 x{\displaystyle x=p^{}y}는 그건 동업-= 설정하고, p.를 그 범위는 수는 y{이\displaystyle}M/2<y{이\displaystyle}의 인수 분해와 함께 y≤ M{\displaystyle M/2<, y\leq M}, M)N/p는{\displaystyle M=N/p^{}}를 생성하 a$$$x{\displaystyle }$ ${\displaystyle x}$의 인자화를 생성하기 위한$$ $y{\displaystyle }$ ${\displaystyle y}$의 인자화에 대한$$ ${\displaystyle$ p$^{a$$\}.$이렇게 하면 원하는 범위에 대한 로그 분포를 가진$$ $x{\displaystyle }$ ${\displaystyle x}$이(가) 제공되며, 거부 샘플링을 사용하여 균일한 분포를 얻는다.

참조

추가 읽기

• 바흐, 에릭.MIT Press, 1984년 수치-이론 알고리즘 분석 및 설계의 분석 방법.제2장 "Random Factorization의 생성"의 일부를 여기에서 온라인으로 이용할 수 있다.