# 표기법

#### 집합, 군, 특수 함수(Sets, Groups, and Special Functions)

* $$ℤ$$ (정수 집합) : 모든 정수의 집합 { …, −2, −1, 0, 1, 2, … }
* $$ℕ$$ (자연수 집합) : 0 이상인 정수의 집합 { 0, 1, 2, … }
* $$\[b]$$ (유한 정수 집합) : 0부터 b−1까지의 정수로 이루어진 집합 { 0, 1, …, b−1 }
* $$gcd(n, m)$$(최대공약수) : 정수 n과 m의 0 이상인 최대공약수 gcd(n, m) = 1이면 n과 m은 서로소(coprime)
* $$\mathbb Z\_n$$ (모듈로 정수 집합) : 정수를 n으로 나눈 나머지에 대한 동치류의 집합 { 0, 1, …, n−1 }
* $$\mathbb Z\_n ^*$$ (모듈로 n의 곱셈군) : $$\mathbb Z\_n$$에서 n과 서로소인 원소들의 집합 $$\mathbb Z\_n ^*$$ = { e ∈ $$\mathbb Z\_n$$ | gcd(e, n) = 1 }, n이 소수이면\
  $$\mathbb Z\_n ^\*$$ = { 1, …, n−1 }
* $$\mathbb F\_p$$ (유한체) : 원소의 개수가 p인 체, p가 소수이면 $$\mathbb F\_p$$ = $$\mathbb Z\_p$$ p가 소수의 거듭제곱이면 갈루아 체(Galois Field)
* $$φ(n)$$ (오일러의 파이 함수) : {1, …, n} 중에서 n과 서로소인 정수의 개수, $$φ(n)$$ = | $$\mathbb Z\_n ^\*$$|
* $$|S|$$ (집합의 크기) : 집합 S에 포함된 원소의 개수, 예: |$$\mathbb Z\_n ^*$$| = $$φ(n)$$, n이 소수이면 |$$\mathbb Z\_n ^*$$|= n − 1

#### 벡터 (Vectors)

* $$\mathbf{a} \in \mathbb{Z}\_q^n$$ : $$\mathbb{Z}\_q$$에 속하는 원소 $$n$$개로 이루어진 벡터 $$\mathbf{a} = (a\_1, \dots, a\_n)$$이다.

  여기서 모든 $$i$$에 대해 각 성분 $$a\_i$$는 정수 $$\mathbb{Z}\_q$$에 속한다.
* $$c \cdot \mathbf{a}$$ (스칼라 곱, Scalar Product): 벡터의 각 성분에 상수(스칼라) $$c$$를 곱하는 연산. $$(c \cdot a\_1, \dots, c \cdot a\_n)$$ 

#### 정수론 (Number-theory)

* $$J(w, n) \in {-1, 0, 1}$$ (Jacobi symbol): 정수 $$w$$와 양의 홀수(positive and odd) $$n$$에 대해 정의되는 함수

  결과값은 -1, 0, 1 중 하나를 가진다.

  > 참고:
  >
  > * $$0$$: $$w$$가 $$n$$의 배수일 때 (서로소가 아님)
  > * $$1$$: $$w$$가 $$n$$에 대해 이차 잉여(Quadratic Residue)일 가능성이 높음 (또는 $$n$$이 소수라면 확실함)
  > * $$-1$$: $$w$$가 $$n$$에 대해 이차 비잉여(Quadratic Non-residue)임
* $$J\_n$$: $$\mathbb{Z}^*\_n$$ 의 원소 중에서, 야코비 기호 값이 1인 원소들만 모은 집합. $$J\_n = { w \in \mathbb{Z}^*\_n : J(w, n) = 1 }$$

#### 샘플링 (Sampling)

프로토콜 명세(specifications)에서는 특정 집합에서 원소를 균등하게(uniformly) 무작위로 뽑아야 하는 경우가 많다. 이때 다음과 같은 표기법을 사용한다.

* $$x \stackrel{$}{←} X$$

집합 $$X$$에서 원소 $$x$$를 균등한 확률로 무작위 추출한다는 뜻이다. (즉, 모든 원소가 뽑힐 확률이 동일함)

#### 검증문 (Assertions)

이 문서는 프로토콜을 기술할 때 검증문을 사용한다. 만약 검증 조건이 충족되지 않는다면(거짓이라면), 비밀 정보가 유출되는 것을 막기 위해 프로토콜을 즉시 **중단(abort)**해야한다.

* $$a \stackrel{?}{=} b$$ : $$a = b$$인지 확인한다. 값이 서로 다르면 중단한다.
* $$a \stackrel{?}{>} b$$ : $$a > b$$인지 확인한다. a가 b보다 크지 않으면 중단한다.
* $$a \stackrel{?}{\in} S$$ : $$a$$가 집합 $$S$$의 원소인지 확인한다. 포함되지 않으면 중단한다.

#### 이외 함수

* $$\Delta(f, R)$$ : 두 함수(여기서는 다항식) $$f$$와 $$R$$ 사이의 거리(Distance), 구체적으로는 상대 해밍 거리(Relative Hamming Distance)를 의미한다.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://upsidezkp.gitbook.io/upside-zkp-docs/definitions.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.