Editing Openai/69679fe4-9524-800d-9c74-5c34521fd378 (section)

=== ## ===

추가 입력(2k비트)은 다음 형태:
* i번째 호출에서: (a0,b0,a1,b1,...,ai−1,bi−1,1,0,0,...)(a_0,b_0,a_1,b_1,...,a_{i-1},b_{i-1},1,0,0,...)(a0,b0,a1,b1,...,ai−1,bi−1,1,0,0,...)

따라서:
* suffixZero[j] = ⋀t=j2k−1¬zt \bigwedge_{t=j}^{2k-1} \neg z_t⋀t=j2k−1¬zt
* i≥1이면: isStagei=z2i∧suffixZero2i+1isStage_i = z_{2i}\wedge suffixZero_{2i+1}isStagei=z2i∧suffixZero2i+1
* i=0이면: isStage0=suffixZero0isStage_0 = suffixZero_0isStage0=suffixZero0

이걸 i=0..R-1까지만 만들면 충분(최대 109개)

==== isItert=⋁p=0BisStaget(B+1)+pisIter_t = \bigvee_{p=0}^{B} isStage_{t(B+1)+p}isItert=p=0⋁BisStaget(B+1)+p ====

==== - 모든 t에 대해 S0,S1,...,STS_0,S_1,...,S_TS0,S1,...,ST를 “순차적으로” 계산하되 차수 계산은 하지 말고(가벼운 연산만) ====

필요한 것은:
* xjx_jxj / yjy_jyj를 transcript에서 디코딩(이전 출력)
* 그 one-hot으로 이웃 판정: neighXj[v]=⋁u∈N(v)xj[u]neighX_j[v] = \bigvee_{u\in N(v)} x_j[u]neighXj[v]=u∈N(v)⋁xj[u]
* 업데이트: alivej+1[v]=alivej[v]∧neighXj[v]∧¬neighYj[v]∧¬xj[v]∧¬yj[v]∧¬foundPrefixjalive_{j+1}[v] = alive_j[v] \wedge neighX_j[v] \wedge \neg neighY_j[v] \wedge \neg x_j[v]\wedge \neg y_j[v] \wedge \neg foundPrefix_jalivej+1[v]=alivej[v]∧neighXj[v]∧¬neighYj[v]∧¬xj[v]∧¬yj[v]∧¬foundPrefixj

그리고 현재 반복의 alive는:

aliveCur[v]=⋁t(isItert∧alivet[v])aliveCur[v] = \bigvee_{t} (isIter_t \wedge alive_t[v])aliveCur[v]=t⋁(isItert∧alivet[v])

==== 각 v에 대해: ====

deg(v)=∑u∈N(v)aliveCur[u]deg(v)=\sum_{u\in N(v)} aliveCur[u]deg(v)=u∈N(v)∑aliveCur[u]
이걸 직렬로 더하면 너무 큼 →
'''Wallace tree(3:2 compressor 층별)'''로 deg(v)를 약 O(deg(v)) full-adder로 압축 가능.
* Full adder 1개를 XOR/AND/OR로 구성하면 노드 5개.
* n=1000, m=10000이면 총 deg합=20000이라 전체 FA 수가 manageable.
* 마지막에 ripple adder로 binary 확정(B≤10 → 50노드/정점)

==== - Alice는 최소 deg, Bob은 최대 deg를 찾는다. ====
* 비교는 a<ba<ba<b를 borrow 기반으로 하면 bit당 4노드 정도로 가능: - borrow_out = (~a & b) | (borrow & XNOR(a,b))

그리고 “candidate가 하나도 없으면”
'''invalid index(2^B−1)'''를 내보내서
상대 멤버십 검사에서 false positive가 나오지 않게 해야 함.

==== - i<R이면: - p<B: 선택된 정점 번호 bit p - p=B: 멤버십 검사 bit (Alice: y_t∈C?, Bob: x_t∈I?) ====
* i≥R이면: - foundFinal(모든 멤버십 비트 OR)을 출력 → 최종 라운드에서 둘 다 1이면 교집합 존재