Algorithm Vision

수학 알고리즘Intermediate

확장 유클리드 알고리즘

유클리드 GCD를 확장하여 ax + by = gcd(a,b)를 만족하는 베주 계수 x와 y를 찾습니다. RSA 암호학의 모듈러 곱셈 역원 계산, 선형 디오판토스 방정식 해결, 중국인의 나머지 정리에 중요합니다. 고전 알고리즘이 어떻게 현대 계산 문제를 해결하도록 확장되는지 보여줍니다.

#mathematical#number-theory#cryptography#modular-arithmetic

Complexity Analysis

Time (Average)

O(log min(a, b))

Expected case performance

Space

O(1)

Memory requirements

Time (Best)

O(log min(a, b))

Best case performance

Time (Worst)

O(log min(a, b))

Worst case performance

Input Numbers (positive integers)

Number A

Number B

Quick Presets:

Step: 1 / 0

Animation Speed500ms

SlowFast

Keyboard Shortcuts

Space Play/Pause← → StepR Reset1-4 Speed

Real-time Statistics

Algorithm Performance Metrics

Progress0%

Comparisons

0

Swaps

0

Array Accesses

0

Steps

1/ 0

Algorithm Visualization

Step 1 of 0

Initialize array to begin

Default

Comparing

Swapped

Sorted

Code Execution

Currently executing

Previously executed

Implementation

Related Algorithms

View all in 수학 알고리즘

에라토스테네스의 체

합성수를 반복적으로 제거하여 n까지의 모든 소수를 찾습니다. 에라토스테네스 (기원전 276-194년)의 이름을 따서 명명되었습니다.

mathematicalprime-numbers

파스칼의 삼각형

각 숫자가 바로 위의 두 숫자의 합인 이항 계수의 삼각형 배열입니다. 블레즈 파스칼(1623-1662)의 이름을 따서 명명되었으며, 수세기 전부터 수학자들에게 알려져 있었습니다. 이항 전개, 조합론, 피보나치 수와의 연결을 포함한 아름다운 수학적 패턴을 보여줍니다.

mathematicalcombinatorics

유클리드 알고리즘 (최대공약수)

기원전 300년경부터 사용된 반복적인 나눗셈을 통해 두 수의 최대공약수를 계산하는 고대 알고리즘입니다. 여전히 널리 사용되는 가장 오래된 알고리즘 중 하나로 수학적 우아함과 효율성을 보여줍니다. 암호학, 분수 단순화, 수론 응용의 기초입니다.

O(log min(a, b))

mathematicalnumber-theory

Back to 수학 알고리즘

Extended Euclidean Algorithm - Algorithm Vision