검색 결과

...각보다 빨리 온다]. 전자신문. 2017년 6월 28일.</ref> 쇼어 알고리즘을 사용하면 크기가 <math>N</math>인 수를 소인수 분해할 때 <math>O(\log^3 N)</math>의 시간과 <math>O(\log N)</math>의 저장공간이 필요하다. 쇼어는 ...열쇠 <math>N</math>으로 사용한다. 이와 같은 방식이 안전한 이유는 <math>N</math>을 빠른 시간 안에 효율적으로 소인수 분해하는 알고리즘이 지금까지 발견되지 않았기 때문이다. 그러나 쇼어 알고리즘을 충분히 큰 수에 대해서 적용할 수 있는 기계가 만들어지면 ...

...>'' ± ''s'' 꼴의 수를 빠르게 소인수분해할 수 있으며, 보통 지수가 작은 [[메르센 수]]를 소인수분해할 때 많이 쓰이는 [[알고리즘]]이다. 또한 [[수체 체]]는 특수 수체 체의 변형된 방법으로, 모든 자연수 n을 빠르게 소인수분해할 수 있는 알고리즘이지만 특수 수 {{수론 알고리즘}} ...

...212; 1 알고리즘 (Pollard's ''p-1'' algorithm)'''은 1974년 존 폴라드가 발견한 [[소인수분해]] [[알고리즘]]이다. 소인수분해에 사용되는 특수한 유형의 알고리즘으로 어떤 수 n-1의 소인수들이 매우 많거나 작은 소인수들이 많이 있는 [[자연수 ''n''이 어떤 소인수 p를 가지고 있는 합성수라고 하자. [[페르마 소정리]]에 따르면, p와 서로소인 어떤 양의 정수 a, 그리고 모든 양의 정수 K에 대 ...

...''({{llang|en|prime factorization, integer factorization}})는 1보다 큰 자연수를 '''소인수([[소수 (수론)|소수]]인 [[인수]])들만의 곱'''으로 나타내는 것 또는 [[합성수]]를 [[소수 (수론)|소수]]의 곱으로 나타 == 소인수분해 알고리즘 == ...

...분수 소인수분해 알고리즘'''은 어떤 [[자연수]]의 [[제곱근]]의 [[연분수]] 전개를 이용하여 자연수를 [[소인수분해]]하는 [[알고리즘]]이다. == 알고리즘 == ...

...해 사용되는 [[소인수 분해]] 알고리즘으로, 양자컴퓨터가 상용화되었을 때 기준으로는 현재까지 발견된 알고리즘 중에서 3번째([[쇼어 알고리즘]], [[수체 체]] ([[:en:General_number_field_sieve|General number field sieve]]) :<math>n</math>에 대한 [[소인수 분해]] 시간은 다음과 같다. ...

# 순방향은 쉽다: 입력 <math>x</math>에 대해 출력 <math>f(x)</math>를 구할 수 있는 (결정론적) 다항시간 알고리즘 <math>A</math>가 존재한다. (즉, <math>A(x)=f(x)</math>이다.) # 역방향은 어렵다: 모든 확률적 다항시간 알고리즘 <math>A^'</math>과 모든 다항식 <math>p(\cdot)</math>, 충분히 큰 모든 <math>n</math>에 대하 ...

수론에서, '''소수판별법'''은 어떤 자연수 N이 [[소수 (수론)|소수]]인지 [[합성수]]인지를 판별하는 [[알고리즘]]들을 말한다. ...수를 소인수 분해 할 수도 있다. 이 방법은 간단하고 편리하지만 다른 소수 판별법 중에서 가장 비효율적인 방식에 속하며 여러 소인수 분해 방법들 중에서도 가장 비효율적인 방법에 속한다. ...

...]] 방법이다. 모든 [[자연수]]에 적용할 수 있으면서 일반적인 컴퓨터에서 실행할 수 있는 소인수분해 알고리즘 중 3번째로 빠른 [[알고리즘]]이며 (2번째는 다중 [[이차 체]] - Multiple Polynomial Quadratic Sieve, 1번째는 [[수체 체]] == 알고리즘 == ...

...개념의 일반화이다. 이를 통해 '''으뜸 분해'''({{llang|en|primary decomposition}})라는, [[소인수 분해]]의 일반화를 정의할 수 있다. === 으뜸 분해 === ...

{{다른 뜻|폴라드 로 이산 로그 알고리즘|소인수분해 알고리즘|이산 로그 알고리즘}} ...ref> 이 알고리즘은 저장 공간을 적게 사용하고 소인수분해하는 데 걸리는 실행 시간은 소인수분해하려는 [[합성수]]의 가장 작은 [[소인수]]의 제곱근에 비례하는 알고리즘이다. ...

어떤 문제는 '''NP-완전''', '''P''' 어느 쪽인지 아직 밝혀지지 않았다. 이 문제들(예: [[소인수 분해]])은 어려울 것으로 추측하고 있다. 이와 비슷하게 '''P-완전'''인지 '''NC'''인지 밝혀지지 않았지만, 어려울 것으로 보고 예를 들어 두 이진수의 [[최대공약수]]를 찾는 문제의 [[판정 문제]]꼴이나, [[유클리드 호제법|확장 유클리드 알고리즘]]이 이진수 두 개를 입력받았을 때 어떤 답을 할지 판정하는 문제가 있다. ...

...')은 [[이산 푸리에 변환]](Discrete Fourier Transform, DFT)과 그 역변환을 빠르게 수행하는 효율적인 [[알고리즘]]이다. FFT는 [[디지털 신호 처리]]에서 [[편미분 방정식]]의 근을 구하는 알고리즘에 이르기까지 많은 분야에서 사용한다. ..."이라고 묘사했으며, [[IEEE]] 잡지 Computing in Science & Engineering에서 선정한 "20세기 최고의 알고리즘 10선"에 포함되었다. ...

...nal number theory}})는 [[수론]]에서 등장하는 각종 값들을 계산하는 [[알고리즘]]을 연구하는 분야이다. [[소인수 분해]]나 [[유한체]]에 대한 알고리즘의 연구가 대표적인 예이다. ...

양자 계산에서 '''양자 알고리즘'''은 양자 계산의 실제 모델에서 실행되는 [[알고리즘]]이며 가장 일반적으로 사용되는 모델은 계산의 양자 회로 모델이다.<ref>{{서적 인용|제목=Quantum Computation an ...algorithm|웹사이트=quantum-computing.ibm.com|확인날짜=7 June 2022}}</ref> [[순차 검색 알고리즘|선형 검색]]보다 제곱으로 빠르게 실행된다. ...