crypto.egcd
Computes the greatest common divisor and Bezout coefficients x and y for two integers, solving gcd(a,b)=ax+by with the extended Euclidean algorithm.
Instructions
확장 유클리드 알고리즘으로 gcd(a, b) = ax + by 를 만족하는 gcd 와 Bezout 계수 x, y 를 구한다. a, b 는 정수 문자열(자릿수 한도 2048)이고 gcd 는 0 이상이다. 계수 쌍은 유일하지 않으며 이 알고리즘이 내는 한 쌍이다. 모듈러 역원이 목적이면 modinv 가 직접적이다.
Input Schema
| Name | Required | Description | Default |
|---|---|---|---|
| a | Yes | ||
| b | Yes |
Output Schema
| Name | Required | Description | Default |
|---|---|---|---|
| x | Yes | ||
| y | Yes | ||
| gcd | Yes | ||
| _meta | No | 서버가 붙이는 영수증(integrity), 엔진, 힌트 | |
| trace | Yes | 계산 근거(tool, formula, inputs, steps, output) |