Circle FFT — भाग 1: Circle Domain का निर्माण

Last updated on Aug 20, 2025

Circle STARKs एक नई zk-STARK स्कीम है जिसे Stwo और Plonky3 में इम्प्लीमेंट किया गया है, और इसे कई zkVM प्रोजेक्ट्स द्वारा अपनाया गया है। इसका मुख्य नवाचार (innovation) छोटे 32-बिट फील्ड्स (Mersenne prime $2^{31}-1$ ) के उपयोग को सक्षम करने में निहित है, जबकि यह कुशल FFT ऑपरेशन्स के लिए आवश्यक गणितीय गुणों को बनाए रखता है। इस व्याख्यात्मक लेख शृंखला में, हम Circle STARK के पीछे के मुख्य एल्गोरिदम पर चर्चा करेंगे, जिसका नाम Circle FFT है।

भाग 1 लेख में, हम सबसे पहले समीक्षा करेंगे कि STARK-friendly primes कैसे विकसित हुए हैं, और फिर हम Circle FFT की मूलभूत अवधारणाओं—जैसे कि circle curve, इसका group structure, और twin-cosets तथा standard-position cosets की भूमिकाओं—का विस्तृत उदाहरणों और व्युत्पत्तियों (derivations) का उपयोग करके अन्वेषण करेंगे। इसके बाद, भाग 2 लेख में, हम स्वयं Circle FFT एल्गोरिदम का विस्तार से वर्णन करेंगे।

हम इन मुख्य विचारों—जैसे कि circle group और Circle FFT—का एक वॉकथ्रू भी प्रदान करते हैं, साथ ही Python-script के साथ $p=31$ (Mersenne prime जिसका घातांक $5$ है: $2^5 -1$ ) के लिए स्पष्ट उदाहरण गणनाएं (computations) भी शामिल हैं।

हमारा ध्यान इस बात पर है कि कैसे इनमें से प्रत्येक बिल्डिंग ब्लॉक एक पूर्ण FFT-जैसे रूटीन की ओर ले जाता है, तब भी जब $p-1$ में कोई बड़ा two-adic फैक्टर नहीं होता है।

यदि आप स्वयं उदाहरणों को रन करने में रुचि रखते हैं, तो पूरा Python कोड यहाँ उपलब्ध है, और हम इसे बाद के सेक्शन जैसे कि सेक्शन 4 और 6 में संदर्भित करेंगे, जहाँ हम कोड में group और domain निर्माण की प्रक्रिया को समझेंगे।

यह लेख Yugo द्वारा RareSkills के सहयोग से लिखा गया था। इस लेख को Soulforge Grant द्वारा फंड किया गया था। हम उनके समर्थन के लिए आभारी हैं।

0. STARK‑Friendly Primes से Mersenne 31 तक

STARK-friendly prime में गहराई से जाने से पहले, आइए सबसे पहले finite-field की बुनियादी बातों को याद करें।

एक फील्ड (field) वह सेट है जिसमें जोड़, घटाव, गुणा और भाग (शून्य को छोड़कर) परिभाषित होते हैं। जब तत्वों (elements) का सेट परिमित (finite) होता है, तो इसे finite field कहा जाता है। $\mathbb{F}_p$ शून्य से लेकर $p-1$ (जहाँ $p$ एक अभाज्य संख्या/prime है) तक के पूर्णांकों के सेट को संदर्भित करता है, जिसमें जोड़, घटाव, और गुणा सभी मॉड्यूलो $p$ (modulo $p$ ) लिए जाते हैं, और भाग को मॉड्यूलो $p$ गुणा के व्युत्क्रम (inverse) के रूप में परिभाषित किया जाता है।

हम $\mathbb{F}_p^*$ द्वारा $\mathbb{F}_p \setminus \{0\}$ सेट को दर्शाते हैं। $\mathbb{F}_p^*$ में प्रत्येक तत्व का एक मल्टीप्लिकेटिव इनवर्स (multiplicative inverse) होता है, इसलिए $\mathbb{F}_p^*$ को एक मल्टीप्लिकेटिव ग्रुप के रूप में देखा जा सकता है। इस ग्रुप का आकार, $|\mathbb{F}_p^*|$ , $p-1$ है। जब हम $p-1$ को इसके अभाज्य गुणनखंडों (prime factors) में विभाजित करते हैं, तो यह ज्ञात है कि यदि कोई अभाज्य संख्या $q$ , $r$ बार आती है, तो $q^r$ आकार का एक चक्रीय उपसमूह (cyclic subgroup) होता है।

आप इसे एक छोटे prime, उदाहरण के लिए $p=7$ , के साथ संक्षेप में समझ सकते हैं। चूंकि $p-1=6$ का गुणनखंड $2\times 3$ होता है, इसलिए 2 और 3 आकार के सबग्रुप्स (subgroups) होने चाहिए। वास्तव में, $\mathbb{F}_7^* = \{1,2,3,4,5,6\}$ में, तत्व 6, 2 आकार का एक सबग्रुप $\{1,6\}$ उत्पन्न करता है, और तत्व 2, 3 आकार का एक सबग्रुप $\{1,2,4\}$ उत्पन्न करता है।

कई STARK प्रोटोकॉल्स में, Number-Theoretic Transform (NTT) या Fast Fourier Transform (FFT) ऐसे सबग्रुप पर निर्भर करता है जहाँ फैक्टर 2 की घात (power of 2) होता है, जिससे सबग्रुप का आकार $2^r$ हो जाता है। वह सबसे बड़ा पूर्णांक $r$ जिसके लिए $2^r$ , $(p-1)$ को विभाजित करता है, उसे two-adicity कहा जाता है। एक उच्च two-adicity, FFT/NTT डोमेन के लिए 2 की घात वाले बड़े आकार की अनुमति देती है, जो तेज़ बहुपद मूल्यांकन (polynomial evaluations), इंटरपोलेशन (interpolations), और बहुपद गुणन (polynomial multiplication) प्राप्त करने के लिए महत्वपूर्ण है। इसके अलावा, इन NTT-आधारित ऑपरेशन्स को कुशलतापूर्वक लागू करना बड़े पैमाने पर तेज़ मॉड्यूलर गुणन पर निर्भर करता है—क्योंकि FFT/NTT में तत्वों को बार-बार गुणा करना और उन्हें मॉड्यूलो $p$ कम करना शामिल होता है।

मूल रूप से, STARKs एक prime $p = 2^{251} + 17 \cdot 2^{192} + 1$ का उपयोग करते थे, जिसकी two-adicity 192 है। आधुनिक STARK इम्प्लीमेंटेशन में, फाइनाइट फील्ड के आकार को कम करके ओवरहेड को कम करने के लिए सुधार किए गए थे। उदाहरण के लिए, Goldilocks फील्ड $p = 2^{64} - 2^{32} + 1$ है और इसकी two-adicity 32 है। महत्वपूर्ण रूप से, चूँकि $2^{64} \equiv 2^{32} - 1 \pmod{p},$ दो 64-बिट संख्याओं के गुणनफल को आधार $2^{32}$ में विभाजित किया जा सकता है और केवल कुछ जोड़ और घटाव के साथ कम (reduce) किया जा सकता है।

Circle STARKs के बारे में क्या? जैसा कि Circle STARKs paper में प्रस्तावित है, यह एक Mersenne prime का उपयोग करता है,

p = 2^{31} - 1.

Mersenne prime, किसी पूर्णांक $n$ के लिए $2^n -1$ के रूप की एक अभाज्य संख्या होती है। यहाँ, $n=31$ से $2^{31}−1$ प्राप्त होता है, जो कि एक अभाज्य संख्या है और इसलिए इसे Mersenne prime के रूप में वर्गीकृत किया गया है।

$2^{31}-1$ को चुनने का एक मुख्य कारण यह है कि यह 32-बिट मशीन वर्ड के भीतर फिट बैठता है, जिससे मॉड्यूलर गुणन अत्यधिक तेज़ हो जाता है। विशेष रूप से, जब दो 32-बिट संख्याओं को गुणा किया जाता है, तो परिणाम 64-बिट मान होता है, और $2^{31}-1$ द्वारा मॉड्यूलर रिडक्शन केवल दो जोड़ के साथ किया जा सकता है।

वेक्टराइज्ड इंस्ट्रक्शन्स (vectorized instructions) के साथ यह ऑपरेशन बहुत तेज हो सकता है। आधुनिक CPU मूल रूप से 32-बिट पूर्णांकों को प्रोसेस करने में उत्कृष्ट हैं, और Mersenne 31 ( $2^{31}-1$ ) इस आर्किटेक्चर के भीतर फिट बैठता है, जिससे हार्डवेयर क्षमताओं का इष्टतम उपयोग होता है। मूल STARK में उपयोग किए गए 256-बिट prime की तुलना में, Mersenne 31 लगभग 125 गुना तेज मॉड्यूलर गुणन प्रदान करता है, और Baby Bear ( $2^{31} - 2^{27} + 1$ ) की तुलना में 1.3 गुना स्पीडअप प्रदान करता है, जैसा कि Eli Ben-Sasson द्वारा Why I’m Excited By Circle Stark And Stwo में चर्चा की गई है।

हालाँकि, पारंपरिक FFT या NTT दृष्टिकोण के लिए $\mathbb{F}_p^*$ में 2 की घात का पर्याप्त सबग्रुप बनाने हेतु $p-1$ में एक बड़े 2-adic फैक्टर की आवश्यकता होती है। यहाँ, $|\mathbb{F}_p^*| = p - 1 \;=\; 2^{31} - 2,$ जिसकी two-adicity केवल 1 है। इस प्रकार, हम गुणन के तहत सीधे 2 की घात वाले बड़े सबग्रुप का उपयोग नहीं कर सकते हैं।

Circle STARK अभी भी Mersenne prime field $p = 2^{31} - 1$ का उपयोग करता है। हालाँकि, सीधे $\mathbb{F}_p$ के साथ काम करने के बजाय, हम देखते हैं कि वक्र (curve)

x^2 + y^2 = 1

जो

\mathbb{F}_p

के ऊपर है (जहाँ

p \equiv 3 \pmod{4}

), उसमें ठीक

p + 1

बिंदु होते हैं। उदाहरण के लिए, जब

p = 3\; (= 2^2 - 1)

, तो ठीक चार ऐसे बिंदु होते हैं:

(0,1), (0,2), (1,0), (2,0)

।

यह महत्वपूर्ण है क्योंकि $p+1$ में 2 की एक बड़ी घात शामिल हो सकती है, जो $2^n$ आकार के सबग्रुप्स बनाती है। इस प्रकार, $\mathbb{F}_p$ में एकल तत्वों के साथ काम करने के बजाय, Circle STARK उन जोड़ों $(x,y)\in \mathbb{F}_p^2$ पर विचार करता है जो $x^2 + y^2 = 1$ (अर्थात circle curve के बिंदुओं) को संतुष्ट करते हैं।
ऐसा करके, Circle STARK इन circle तत्वों पर सीधे अपना स्वयं का तेज़ बहुपद इंटरपोलेशन और मूल्यांकन—जिसे अक्सर Circle FFT कहा जाता है—लागू कर सकता है।

1. Circle Curve

आइए Circle STARKs के मुख्य गणित की ओर बढ़ें। एक फाइनाइट फील्ड $\mathbb{F}_p$ पर एक circle curve, $\mathbb{F}_p^2$ का वह सबसेट है जो उन सभी बिंदुओं $(x,y)$ द्वारा परिभाषित होता है जो इसे संतुष्ट करते हैं:

x^2 + y^2 = 1.

हम कभी-कभी इस सेट को

C(\mathbb{F}_p)

या केवल “circle” द्वारा दर्शाते हैं।

Circle STARKs में, हम उन primes $p$ पर ध्यान केंद्रित करते हैं जिनमें $p \equiv 3 \pmod{4}$ (उदाहरण के लिए, $p=3,7,11,\dots$ ) हो। इस शर्त के तहत, $-1$ , $\mathbb{F}_p$ में एक पूर्ण वर्ग (square) नहीं है। ठोस रूप से, यह सुनिश्चित करता है कि समीकरण $x^2 + y^2 = 1$ के $\mathbb{F}_p^2$ में ठीक $p+1$ समाधान हैं और कोई अतिरिक्त आउटलायर समाधान (यानी, अनंत पर बिंदु / points at infinity) नहीं हैं। इस लेख के लिए, हमें बस यह चाहिए कि उस शर्त के तहत $\mathbb{F}_p^2$ में $x^2 + y^2 = 1$ ठीक $p+1$ बिंदु देता है।

(हालाँकि, जो पाठक इस ज्यामितीय दृष्टिकोण में रुचि रखते हैं कि क्यों $p \equiv 3 \pmod{4}$ ठीक $p + 1$ समाधानों की ओर ले जाता है, वे परिशिष्ट (Appendix) देख सकते हैं।)

1.1 Toy Example $p=7\equiv 3 \pmod{4}$

उदाहरण के लिए, यदि $p =7$ (जो $3 \pmod{4}$ है), तो $C(\mathbb{F}_{7})$ , $\mathbb{F}_{7}^2$ में उन सभी $(x,y)$ का सेट है जिसके लिए $x^2 + y^2 = 1$ है।

यहाँ $\mathbb{F}_{7}^2$ में कुछ जोड़े $(x,y)$ दिए गए हैं जो $x^2 + y^2 \equiv 1 \pmod{7}$ को संतुष्ट करते हैं। उदाहरण के लिए:

$(1, 0)$ और $(0, 1)$ स्पष्ट हैं क्योंकि $1^2 + 0^2=1$ और $0^2 + 1^2=1$ है।
$(5,2)$ भी काम करता है क्योंकि $5^2 + 2^2 = 25 + 4 = 29$ , और $29 \bmod 7 = 1$ है।

हम देखते हैं कि $p=7$ के लिए ऐसे ठीक $8$ $(p+1)$ जोड़े हैं।

2. Circle Group

इस प्रकार के सेट को $C(\mathbb{F}_p)$ द्वारा दर्शाया जाता है और इसे अक्सर $\mathbb{F}_p$ पर Circle Curve कहा जाता है। एक आश्चर्यजनक तथ्य यह है कि $|C(\mathbb{F}_p)| = p + 1$ । उदाहरण के लिए, यदि $p = 7$ है, तो वृत्त पर ठीक $7 + 1 = 8$ बिंदु हैं — विशेष रूप से $8 = 2^3$ ।

यह महत्वपूर्ण है क्योंकि सामान्य STARK सेटिंग में, हम अक्सर FFT-जैसे ऑपरेशन्स के लिए $2^n$ आकार का डोमेन चाहते हैं। $p = 7$ के मामले में, वृत्त पर ठीक 8 बिंदुओं का होना यह अर्थ रखता है कि हम $2^n$ आकार के सबग्रुप्स बना सकते हैं। बाद में, हम देखेंगे कि Circle FFT में इस गुण ( $p+1$ में उच्च 2-adicity) का उपयोग कैसे किया जाता है।

एक प्रमुख गुण यह है कि $C(\mathbb{F}_p)$ को इसके बिंदुओं पर एक समूह संक्रिया (group operation) (जो अनिवार्य रूप से एक बाइनरी ऑपरेटर है) के साथ दिया जा सकता है। विशेष रूप से, हम इस ऑपरेशन को दर्शाने के लिए “ $\cdot$ ” का उपयोग करते हैं: $C(\mathbb{F}_p)$ में दो बिंदुओं $(x_0,y_0)$ और $(x_1,y_1)$ के लिए,

(x_0, y_0)\,\cdot\,(x_1, y_1) \;=\; \bigl(x_0 x_1 - y_0 y_1,\;\; x_0 y_1 + y_0 x_1\bigr).

हम जांच कर सकते हैं कि यह group operation, $C(\mathbb{F}_p)$ के भीतर रहता है (परिणाम अभी भी $x^2 + y^2=1$ को संतुष्ट करता है) और सेट को $p+1$ आकार का एक चक्रीय समूह (cyclic group) बनाता है।

2.1 Checking the Group Axioms

एक ग्रुप के स्वयंसिद्धों (axioms) के रूप में, हम आमतौर पर निम्नलिखित चार गुणों को सूचीबद्ध करते हैं: संवरक (closure), तत्समक अवयव (identity element), प्रतिलोम अवयव (inverse element), और सहचर्य (associativity)। आइए यह पुष्टि करने के लिए हर एक पर करीब से नज़र डालें कि वे सभी लागू होते हैं।

2.1.1 Closure

वृत्त पर दो बिंदु $(x_0, y_0)$ और $(x_1, y_1)$ लें;

x_0^2 + y_0^2 = 1 \quad\text{and}\quad x_1^2 + y_1^2 = 1.

एक नया बिंदु परिभाषित करें

(\hat{x}, \hat{y}) \;=\; \bigl( x_0\,x_1 \;-\; y_0\,y_1, \;\; x_0\,y_1 \;+\; y_0\,x_1 \bigr).

हम यह दिखाएंगे कि $(\hat{x}, \hat{y})$ भी वृत्त पर स्थित है, जिसके लिए हम $(\hat{x}^2 + \hat{y}^2)$ की क्रमिक रूप से गणना करेंगे:

\begin{aligned} \hat{x}^2 + \hat{y}^2 &=\; (x_0 x_1 - y_0 y_1)^2 \;+\; (x_0 y_1 + y_0 x_1)^2 \quad \text{// वर्ग का विस्तार करें (expand squares)} \\[6pt] &=\; {x_0^2 x_1^2} -\; 2\,x_0 x_1\,y_0 y_1 +\; {y_0^2 y_1^2} \;+\; {x_0^2 y_1^2} +\; 2\,x_0 y_1\,y_0 x_1 +\; {y_0^2 x_1^2} \\[4pt] &=\; x_0^2 x_1^2 \;+\; y_0^2 y_1^2 \;+\; x_0^2 y_1^2 \;+\; y_0^2 x_1^2 \quad \text{// $\pm2\,x_0 y_1\,y_0 x_1$ कट गए} \\[3pt] &=\; x_0^2 \bigl(x_1^2 + y_1^2\bigr) \;+\; y_0^2 \bigl(x_1^2 + y_1^2\bigr) \quad \text{// $(x_1^2 + y_1^2)$ को कॉमन लें} \\[3pt] &=\; \bigl(x_0^2 + y_0^2\bigr)\, \bigl(x_1^2 + y_1^2\bigr) \quad \text{// $x_0^2 + y_0^2$ का उपयोग करके फिर से गुणनखंड (factor) करें} \end{aligned}

चूँकि हम जानते हैं कि $x_0^2 + y_0^2 = 1$ और $x_1^2 + y_1^2 = 1$ , हम इन मानों को गुणनफल में प्रतिस्थापित करते हैं:

\hat{x}^2 + \hat{y}^2 \;=\; (x_0^2 + y_0^2)\,(x_1^2 + y_1^2) \;=\; 1 \times 1 \;=\; 1.

अतः $(\hat{x}, \hat{y})$ भी $(\hat{x}^2 + \hat{y}^2 = 1)$ को संतुष्ट करता है और इसलिए वृत्त पर स्थित है। यह पुष्टि करता है कि सेट इस संक्रिया के तहत संवृत (closed) है

(x_0, y_0) \;\cdot\; (x_1, y_1) \;=\; (\hat{x}, \hat{y}).

2.1.2 Identity Element

बिंदु $(1,0)$ समूह संक्रिया (group operation) के तहत identity element के रूप में कार्य करता है। ठोस रूप से, वृत्त पर किसी भी $(x,y)$ के लिए,

(1,0)\cdot(x,y) \;=\; \bigl(1\cdot x - 0\cdot y,\;1\cdot y + 0\cdot x\bigr) \;=\; (x,y),

कोई बिंदु $(0,1)$ के बारे में सोच सकता है। यदि हम $(0,1)$ को एक identity के रूप में उपयोग करने का प्रयास करते हैं, तो हम देखते हैं कि यह विफल रहता है:

(0,1)\cdot(x,y) \;=\; \bigl(0\cdot x - 1\cdot y,\;0\cdot y + 1\cdot x\bigr) \;=\; (-y,\;x),

जो सामान्य

x,y

के लिए

(x,y)

के बराबर नहीं है। चूंकि identity element अद्वितीय (unique) होता है, इसलिए

(0,1)

identity नहीं हो सकता।

2.1.3 Inverse

एक ग्रुप में, किसी तत्व $(x,y)$ का प्रतिलोम (inverse) वह अद्वितीय बिंदु $(x',y')$ होता है जो इसे संतुष्ट करता है:

(x,y)\,\cdot\,(x',y') \;=\; (1,0).

वृत्त पर, हम देखते हैं कि

(x,-y)

, group operation के संबंध में

(x,y)

के inverse के रूप में कार्य करता है। वास्तव में,

(x,y)\,\cdot\,(x,\,-y) \;=\; \bigl(x\,x - y\,(-y),\; x\,(-y) + y\,x\bigr) \;=\; \bigl(x^2 + y^2,\;0\bigr) \;=\; (1,0),

चूँकि

x^2 + y^2 = 1

है।
इस प्रकार, group operation के तहत

(x,y)

का inverse

(x,\,-y)

है।

2.1.4 Associativity

अंतिम ग्रुप स्वयंसिद्ध (group axiom) associativity है: वृत्त पर किन्हीं तीन बिंदुओं

$(x_0,y_0), (x_1,y_1), (x_2,y_2)$ के लिए,

\bigl((x_0,y_0)\,\cdot\,(x_1,y_1)\bigr)\,\cdot\,(x_2,y_2) \;=\; (x_0,y_0)\,\cdot\,\bigl((x_1,y_1)\,\cdot\,(x_2,y_2)\bigr).

इसे बहुपद (polynomial) का विस्तार करके सत्यापित किया जा सकता है, लेकिन हम यहाँ विस्तार में नहीं जाएंगे क्योंकि यह बहुत लंबा हो जाएगा।

2.2 A Special Operation: The Squaring Map $\pi$

इन ग्रुप स्वयंसिद्धों (group axioms) के अलावा, वृत्त पर एक और संक्रिया है जो बाद के अनुभागों में, विशेष रूप से Circle FFT के लिए विशेष रूप से उपयोगी है, वह है squaring map। यह मैप किसी बिंदु पर स्वयं उसी के साथ group operation लागू करता है:

\pi(x,y) \;=\; (x,y)\,\cdot\,(x,y) \;=\; \bigl(x^2 - y^2,\;2\,x\,y\bigr).

चूँकि वृत्त $x^2 + y^2 = 1$ को संतुष्ट करता है, हमें $x^2 - y^2 = 2x^2 - 1$ प्राप्त होता है, इसलिए

\pi(x,y) \;=\; \bigl(2\,x^2 - 1,\;2\,x\,y\bigr).

Circle FFT में, हम पुनरावर्ती (recursive) तरीके से कुछ मूल्यांकन डोमेन (evaluation domains) को आधा करने के लिए $\pi$ का उपयोग करेंगे— $\pi$ का प्रत्येक अनुप्रयोग (application) डोमेन के आकार को 2 के गुणक से कम कर देता है। ऐसा इसलिए है क्योंकि $\pi$ group operation के साथ संगत (compatible) है। ठोस रूप से, वृत्त पर दो बिंदुओं $P$ और $Q$ के लिए,

\pi\bigl(P \cdot Q\bigr) \;=\; \pi(P) \;\cdot\; \pi(Q).

यह संगतता (compatibility) दर्शाती है कि $\pi$ , $2^n$ आकार के एक twin-coset को $2^{n-1}$ आकार के दूसरे twin-coset में मैप करता है। हम इस डोमेन-हाल्विंग (domain-halving) गुण पर विस्तार से बाद में लौटेंगे।

2.3 A Special Operation: The Involution $J$

Squaring map के अलावा, एक और महत्वपूर्ण ऑपरेशन है। यह ऑपरेशन, जिसे involution कहा जाता है, इस प्रकार परिभाषित किया गया है:

J(x,y) \;=\; (x,\;-y).

ज्यामितीय रूप से, यह

x

-निर्देशांक (coordinate) को अपरिवर्तित छोड़ते हुए

y

-निर्देशांक के चिह्न को पलट देता है। ध्यान दें कि

J

अपना स्वयं का inverse है—

J

को दो बार लागू करने पर आप मूल बिंदु पर वापस आ जाते हैं:

J\bigl(J(x,y)\bigr) \;=\; J(x,\;-y) \;=\; (x,\;y).

वृत्त $x^2 + y^2 = 1$ पर, involution $J(x,y)$ वक्र (curve) पर हर बिंदु को बनाए रखता है (क्योंकि $y$ को नकारात्मक करने से $x^2 + y^2$ प्रभावित नहीं होता है)। हालाँकि, $y=0$ वाला बिंदु $J$ के तहत स्थिर (fixed) रहता है, जिसका अर्थ है $J(x,\,0) = (x,\,0)$ ।

2.4 Concrete Operation of Circle Group at $p=31$

पिछले ठोस उदाहरण में, हमने $p = 7$ के साथ $C(\mathbb{F}_p)$ का अन्वेषण किया, जो अंतर्ज्ञान (intuition) बनाने के लिए एक उपयोगी toy example के रूप में काम आया। हालाँकि, Circle Group की गहरी संरचनात्मक विशेषताओं—जैसे लंबी सबग्रुप चेन्स या twin-cosets या standard positon coset के निर्माण—को उजागर करने के लिए $p = 7$ बहुत छोटा है।

इसलिए, अब हम इन समृद्ध व्यवहारों को अधिक सार्थक तरीके से स्पष्ट करने के लिए थोड़े बड़े prime, $p = 31$ (जो $p = 2^5 - 1$ को संतुष्ट करता है) की ओर मुड़ते हैं।

$p = 31$ दिए जाने पर, जो $3 \pmod{4}$ के सर्वांगसम (congruent) है, $\mathbb{F}_{31}^2$ में बिंदुओं $(x, y)$ का सेट जो समीकरण $x^2 + y^2 = 1$ को संतुष्ट करता है, जिसे $C(\mathbb{F}_{31})$ के रूप में दर्शाया गया है, निम्नलिखित चित्र में दर्शाया गया है:

यहाँ $\mathbb{F}_{31}^2$ में कुछ जोड़े $(x,y)$ के उदाहरण दिए गए हैं जो $x^2 + y^2 \equiv 1 \pmod{31}$ को संतुष्ट करते हैं:

$(5,10)$ भी काम करता है क्योंकि $5^2 + 10^2 = 25 + 100 = 125$ , और $125 \bmod 31 = 125 - 4\cdot31 = 1$ है।
$(7,13)$ भी एक समाधान है: $7^2 = 49 \equiv 18$ (mod 31) और $13^2 = 169 \equiv 14$ (mod 31), इसलिए $18 + 14 = 32 \equiv 1$ (mod 31) है।
$(30,0)$ यह दर्शाता है कि $30 \equiv -1 \pmod{31}$ , अतः $(-1)^2 + 0^2 \equiv 1$ (mod 31) है।

Circle Group को देखने के लिए, आइए $\mathbb{F}_{31}$ पर काम करें, जहाँ वृत्त $C(\mathbb{F}_{31})$ में 32 बिंदु हैं। मान लें कि हम यह बिंदु चुनते हैं:

Q \;=\; (13,\,7).

हम

Q

को group operation के माध्यम से बिंदु

(30,0)

के साथ जोड़ सकते हैं:

(13,\,7) \,\cdot\,(30,\,0) \;=\; \bigl( 13 \cdot 30 - 7 \cdot 0,\;\; 13 \cdot 0 + 7 \cdot 30 \bigr) \;=\; (390,\,210) \;\equiv\; (18,\,24) \pmod{31}.

वास्तव में, कोई भी यह सत्यापित कर सकता है:

18^2 + 24^2 \;\equiv\; 324 + 576 \;\equiv\; 900 \;\equiv\; 1 \pmod{31},

इसलिए $(18,\,24)$ भी वृत्त $x^2 + y^2 = 1$ पर स्थित है।
इस बीच, $Q$ का inverse है:

Q^{-1} \;=\; (13,\,-7)\;\equiv\;(13,\,24)\pmod{31},

क्योंकि

(13,\,7)\,\cdot\,(13,\,24) \;=\; (1,\,0).

इसके अतिरिक्त, squaring map बिंदु $Q=(13,7)$ पर काम कर सकता है। याद करें कि

\pi(x,y) \;=\; (x,y)\,\cdot\,(x,y).

अतः,

\pi(Q) \;=\; (13,7)\,\cdot\,(13,7) \;=\; \bigl(13\cdot 13 - 7\cdot 7,\;13\cdot 7 + 7\cdot 13\bigr) \; \;\equiv\; (27,\,27) \pmod{31}.

3. Subgroups of Circle Group

हमने स्थापित किया है कि $C(\mathbb{F}_p)$ , $p+1$ आकार का एक चक्रीय समूह (cyclic group) है। यदि $p + 1$ दो की घात (power of two) है, मान लीजिए $p+1 = 2^m$ , तो सबग्रुप्स की एक नेस्टेड श्रृंखला (nested chain) होती है

G_0 \;\subset\; G_1 \;\subset\; G_2 \;\subset\; \dots \;\subset\; G_m \;=\; C(\mathbb{F}_p)

जहाँ प्रत्येक

G_k

का क्रम (order)

|G_k| = 2^k

होता है।
दूसरे शब्दों में,

G_1

, 2 आकार का एक सबग्रुप है,

G_2

का आकार 4 है, और इसी तरह

G_m = C(\mathbb{F}_p)

तक, जिसका आकार

2^m = p+1

है।

उदाहरण के लिए, यदि $p = 31$ (इसलिए $p+1 = 32 = 2^5$ ), तो हमें एक श्रृंखला प्राप्त होती है

G_0,\,G_1,\,G_2,\,G_3,\,G_4,\,G_5

जहाँ

G_5 = C(\mathbb{F}_{31})

और प्रत्येक

G_k

का आकार

2^k

है। एक सारांश इस प्रकार दिख सकता है:

$k$	$\lvert G_k\rvert = 2^k$
$G_0$	1
$G_1$	2
$G_2$	4
$G_3$	8
$G_4$	16
$G_5$	32

नीचे, हम $C(\mathbb{F}_{31})$ में प्रत्येक सबग्रुप को स्पष्ट रूप से सूचीबद्ध करते हैं।

Size 1:  [Point(1, 0)]
Size 2:  [Point(1, 0), Point(30, 0)]
Size 4:  [Point(1, 0), Point(0, 30), Point(30, 0), Point(0, 1)]
Size 8:  [Point(1, 0), Point(4, 27), Point(0, 30), Point(27, 27), Point(30, 0), Point(27, 4), Point(0, 1), Point(4, 4)]
Size 16:  [Point(1, 0), Point(7, 13), Point(4, 27), Point(18, 24), Point(0, 30), Point(13, 24), Point(27, 27), Point(24, 13), Point(30, 0), Point(24, 18), Point(27, 4), Point(13, 7), Point(0, 1), Point(18, 7), Point(4, 4), Point(7, 18)]
Size 32:  [Point(1, 0), Point(2, 11), Point(7, 13), Point(26, 10), Point(4, 27), Point(21, 5), Point(18, 24), Point(20, 29), Point(0, 30), Point(11, 29), Point(13, 24), Point(10, 5), Point(27, 27), Point(5, 10), Point(24, 13), Point(29, 11), Point(30, 0), Point(29, 20), Point(24, 18), Point(5, 21), Point(27, 4), Point(10, 26), Point(13, 7), Point(11, 2), Point(0, 1), Point(20, 2), Point(18, 7), Point(21, 26), Point(4, 4), Point(26, 21), Point(7, 18), Point(2, 20)]

4. Python Code 1: Circle Group

अब हम Simple Python इम्प्लीमेंटेशन के माध्यम से Circle Group कोड की समीक्षा करेंगे। यहाँ केवल सबसे महत्वपूर्ण फ़ंक्शन्स या भागों का वर्णन किया गया है, और पूरा कोड यहाँ उपलब्ध है।

यहाँ, हम अंतर्निहित फाइनाइट फील्ड में अंकगणित को संभालने और वक्र (curve) पर समूह संक्रियाओं (group operations) को संभालने के लिए क्रमशः दो मुख्य क्लासेस- FieldElement और CirclePoint—परिभाषित करते हैं।

4.1 FieldElement

सबसे पहले, FieldElement क्लास फाइनाइट फील्ड $\mathbb{F}_{31}$ में अंकगणितीय संक्रियाओं को परिभाषित करती है, जैसे कि जोड़, गुणा, और व्युत्क्रम मॉड्यूलो 31 (inversion modulo 31)। यह circle वक्र पर सभी गणनाओं का आधार है।

# Mersenne 5
MOD = 31

class FieldElement:
    def __init__(self, value):
        """Initialize a field element"""
        self.value = value % MOD

    def __add__(self, other):
        """Add two field elements"""
        return FieldElement((self.value + other.value) % MOD)

    def __mul__(self, other):
        """Multiply two field elements"""
        return FieldElement((self.value * other.value) % MOD)

    def inv(self):
        """Compute the multiplicative inverse"""
        return FieldElement(pow(self.value, MOD - 2, MOD))

    def square(self):
        """Compute the square"""
        return self * self

4.2 CirclePoint

CirclePoint क्लास वृत्त वक्र $x^2+y^2=1$ पर बिंदुओं का प्रतिनिधित्व करती है। add विधि (method) group operation को लागू करती है, जबकि double squaring map को लागू करती है।

class CirclePoint:
    def __init__(self, x, y):
        """Initialize a point on the circle x^2 + y^2 = 1"""
        if (x.square() + y.square()).value != 1:
            raise ValueError("Point does not lie on the circle")
        self.x = x
        self.y = y

    def add(self, other):
       """Perform group operation: (x1,y1)・(x2,y2) = (x1*x2 - y1*y2, x1*y2 + x2*y1)."""
        nx = self.x * other.x - self.y * other.y
        ny = self.x * other.y + other.x * self.y
        return CirclePoint(nx, ny)

    def double(self):
        """Apply squaring map: π(x,y) = (2*x^2 - 1, 2*x*y), since x^2 + y^2 = 1."""
        xx = self.x.square().double() - FieldElement.one()
        yy = self.x.double() * self.y
        return CirclePoint(xx, yy)

    @classmethod
    def identity(cls):
        """Return the identity element (1, 0) of the circle group."""
        return cls(FieldElement.one(), FieldElement.zero())

फिर आप धारा 2.4 में वर्णित Circle Group ऑपरेशन उदाहरण का अनुकरण कर सकते हैं।

उदाहरण के लिए, CirclePoint $(13, 7)$ और CirclePoint $(30, 0)$ को जोड़ने पर Point $(18, 24)$ प्राप्त होता है।

p1 = CirclePoint(FieldElement(13), FieldElement(7))
p2 = CirclePoint(FieldElement(30), FieldElement(0))

# group operation
p3 = p1.add(p2)
print(f"p1・p2 = {p3}")

p1・p2 = Point(18, 24)

$p1=(13,7)$ को दोगुना (doubling) करने पर $(27, 27)$ प्राप्त होता है

# squaring map
p1_double = p1.double()
print(f"π(p1) = {p1_double}")

π(p1) = Point(27, 27)

$(13, 7)$ का inverse $(13, 24)$ है, और उन्हें जोड़ने पर identity $(1, 0)$ प्राप्त होता है

# Inverse
p1_inv = p1.inverse()
print(f"p1's inverse = {p1_inv}")
p1_plus_inv = p1.add(p1_inv)
print(f"p1・p1_inv = {p1_plus_inv}")

p1's inverse = Point(13, 24)
p1・p1_inv = Point(1, 0)

4.3 Circle Group

फ़ंक्शन generate_subgroup, $2^k$ क्रम के सबग्रुप $G_k$ को उत्पन्न करता है। यह get_nth_generator फ़ंक्शन से उपयुक्त जनरेटर प्राप्त करता है और सबग्रुप बनाने के लिए ग्रुप ऑपरेशन add को दोहराता है।

def generate_subgroup(k: int) -> list[CirclePoint]:
    """Generate a subgroup of size 2^k using the generator."""
    g_k = get_nth_generator(k)
    p = CirclePoint.identity()
    return [ (p := p.add(g_k)) if i else p
             for i in range(1 << k) ]

उदाहरण के लिए, आप 8 आकार का सबग्रुप प्राप्त कर सकते हैं।

G3 = generate_subgroup(3)

Size 8:  [Point(1, 0), Point(4, 27), Point(0, 30), Point(27, 27), Point(30, 0), Point(27, 4), Point(0, 1), Point(4, 4)]

5. Coset, Twin-Cosets and Standard Position Cosets

Twin-Cosets और Standard Position Cosets Circle STARKs में डोमेन हैं। twin-cosets और standard position cosets के गणितीय गुणों को समझने से पहले, आइए संक्षेप में समीक्षा करें कि पारंपरिक STARKS में डोमेन का उपयोग कैसे किया जाता है। जैसा कि धारा 0 में चर्चा की गई है, पारंपरिक STARKS आमतौर पर अपने डोमेन के रूप में $\mathbb{F}_p^*$ के रूप में दर्शाए गए मल्टीप्लिकेटिव (सब)ग्रुप्स का उपयोग करते थे। इन डोमेन ने दो प्राथमिक उद्देश्यों की पूर्ति की।

सबसे पहले, उन्होंने IFFT के माध्यम से कम्प्यूटेशन ट्रेस (computation trace) से बहुपद (polynomials) बनाते समय मूल्यांकन डोमेन (evaluation domain) के रूप में कार्य किया, और हमें FFT के माध्यम से विस्तारित डोमेन के साथ Low Degree Extension (LDE) का संचालन करना होता है और साथ ही हम constraint polynomials का निर्माण करते हैं और LDE पर उनका मूल्यांकन करते हैं।

दूसरा, Low Degree Testing में, विशेष रूप से FRI कमिटमेंट्स (commitments) के साथ, बहुपदों का मूल्यांकन FFT के माध्यम से उन डोमेन पर किया जाना चाहिए जिन्हें पुनरावर्ती (recursive) FRI फोल्डिंग स्टेप्स के दौरान क्रमिक रूप से आधा कर दिया जाता है।

इसके अलावा, FRI फोल्डिंग स्टेप्स के दौरान, जैसे-जैसे बहुपद की डिग्री (degree) आधी की गई, डोमेन के आकार को भी आधा करने की आवश्यकता पड़ी। डोमेन के आकार को आधा करना FRI और FFT दोनों के लिए केंद्रीय है। आगे बढ़ते समय इसे ध्यान में रखें।

क्योंकि जहाँ एक ओर circle group स्वयं पहले से ही उच्च 2-adicity प्रदान करता है, वहीं Twin-Cosets या Standard Position Cosets का निर्माण यह सुनिश्चित करता है कि, FFT में पुनरावर्ती स्क्वायरिंग (recursive squaring) स्टेप्स के दौरान, मूल्यांकन डोमेन (यानी, Twin-Cosets या Standard Position Coset) को उनके कोसेट (coset) संरचना को बनाए रखते हुए आकार में आधा किया जा सकता है। यह रिकर्सन (recursion) के प्रत्येक स्तर में इन डोमेन पर FFT-शैली ऑपरेशन्स को सक्षम करने के लिए आवश्यक है।

5.1 Coset

आइए ग्रुप थ्योरी में coset की परिभाषा को याद करें। मान लीजिए $H$ एक ग्रुप $\mathcal{G}$ का एक सबग्रुप है, और मान लीजिए $Q \in \mathcal{G}$ है। तो $Q$ द्वारा $H$ का बायां कोसेट (left coset) यह सेट है:

Q \,\cdot\, H \;=\; \{\,Q \cdot h \;\mid\; h \in H\}.

यदि $Q \in H$ है, तो $Q \cdot H = H$ । अन्यथा, यदि $Q \notin H$ है, तो $Q \cdot H$ , $H$ से एक असंयुक्त (disjoint) सेट है, लेकिन फिर भी इसका आकार $H$ के समान ही होता है। यह इसलिए सत्य है क्योंकि यदि $Q \in H$ है, तो ग्रुप ऑपरेशन के तहत $H$ का संवरक (closure) यह सुनिश्चित करता है कि $Q \cdot H = H$ है, जबकि यदि $Q \notin H$ है, तो $Q \cdot H$ का कोई भी तत्व यह निहित किए बिना कि $Q \in H$ है, $H$ में नहीं हो सकता है, और आक्षेप (bijection) $h \mapsto Q \cdot h$ आकार को सुरक्षित रखता है।

हमारी विशेष सेटिंग में, $\mathcal{G} = C(\mathbb{F}_p)$ है, जो $p+1$ आकार का चक्रीय (cyclic) है। पिछले भाग से, हम जानते हैं कि सबग्रुप्स की एक श्रृंखला $G_0 \subset G_1 \subset \dots \subset G_m$ है जिसका $|G_k| = 2^k$ है।

इसलिए, उदाहरण के लिए, यदि हम $2^{n-1}$ क्रम के $G_{n-1}$ को स्थिर (fix) करते हैं, तो वृत्त पर किसी भी बिंदु $Q$ के लिए, कोसेट

Q \,\cdot\, G_{n-1} \;=\; \bigl\{Q\cdot g \;\mid\; g\in G_{n-1}\bigr\}

को $G_{n-1}$ का एक कोसेट कहा जाता है।
उस सेट की कार्डिनैलिटी (cardinality) भी $2^{n-1}$ ही होगी, और यह स्वयं $G_{n-1}$ से तब तक असंयुक्त (disjoint) है जब तक कि $Q$ पहले से ही $G_{n-1}$ से संबंधित न हो।

5.1.1 Coset Example

आइए इस उदाहरण को जल्दी से स्पष्ट करें। $p=31$ के मामले में, याद रखें कि $p+1=32=2^5$ है, इसलिए सबग्रुप्स $G_1, G_2, \dots, G_5$ की एक श्रृंखला है जहाँ $|G_1|=2$ है। ठोस रूप से,

G_1 \;=\; \{\,(1,0),\,(30,0)\}.

अब एक बिंदु $Q$ लें जो $G_1$ में नहीं है। उदाहरण के लिए,

Q \;=\; (2,\,11).

चूँकि $Q$ , $G_1$ में नहीं है, सेट

Q \,\cdot\, G_1 \;=\; \{\,(2,11)\cdot(1,0),\,(2,11)\cdot(30,0)\}

$G_1$ का एक विशिष्ट (distinct) कोसेट होगा, जो स्वयं $G_1$ से असंयुक्त (disjoint) होगा।

$(2,11)\cdot(1,0) \;=\; (\,2\cdot1 - 11\cdot0,\;\;2\cdot0 + 11\cdot1) \;=\; (2,\,11),$
$(2,11)\cdot(30,0) \;=\; (\,2\cdot30 - 11\cdot0,\;\;2\cdot0 + 30\cdot11) \;\equiv\; (29,\,20) \;\pmod{31}.$

अतः,

Q \cdot G_1 \;=\; \{(2,\,11),\,(29,\,20)\},

जिसका आकार वास्तव में 2 है। यह $Q=(2,11)$ के संगत $G_1$ का कोसेट है, जो स्वयं सबग्रुप $G_1$ से स्पष्ट रूप से भिन्न है।

5.2 Twin-Cosets

अब हम दो कोसेट्स के संघ (union) को लेकर एक twin-coset परिभाषित करते हैं: $Q \cdot G_{n-1}$ और इसका inverse कोसेट $Q^{-1} \cdot G_{n-1}$ । ठोस रूप से, मान लें

D \;=\; \bigl(Q \,\cdot\, G_{n-1}\bigr) \;\cup\; \bigl(Q^{-1} \,\cdot\, G_{n-1}\bigr).

हम कहते हैं कि

D

आकार

2^n

का एक twin-coset है यदि निम्नलिखित शर्तें पूरी होती हैं:

Disjointness (असंयुक्तता)
दो कोसेट्स $Q \cdot G_{n-1}$ और $Q^{-1} \cdot G_{n-1}$ असंयुक्त (disjoint) हैं।
व्यवहार में, यह disjointness यह सुनिश्चित करने के बराबर है कि $Q^2 \notin G_{n-1}$ है। यह समतुल्यता (equivalence) कोसेट्स के गुणों से उत्पन्न होती है। यदि $Q^2 \in G_{n-1}$ होता, तो $Q = Q^{-1} \cdot Q^2$ , $Q \cdot G_{n-1}$ और $Q^{-1} \cdot G_{n-1}$ दोनों में होता (ओवरलैप)। इसके विपरीत, यदि कोसेट्स ओवरलैप नहीं करते हैं, तो $Q$ को $Q^{-1} \cdot g$ (किसी भी $g \in G_{n-1}$ के लिए) के रूप में नहीं लिखा जा सकता है, जिसका अर्थ है $Q^2 \notin G_{n-1}$ ।
Involution $J$ के तहत कोई स्थिर बिंदु (fixed points) नहीं
किसी बिंदु $P$ को मैप $f$ का fixed point कहा जाता है यदि $f(P) = P$ हो। हमारे मामले में, हम involution $J(x,y) \;=\; \bigl(x,\;-y\bigr)$ पर विचार करते हैं।
यदि $D$ में कोई ऐसा बिंदु होता जहाँ $y=0$ है, तो $J(x,0) = (x,0)$ अपरिवर्तित रहता। यह एक fixed point है। हम $D$ में ऐसे बिंदुओं से बचना चाहते हैं, क्योंकि परिभाषा के अनुसार एक twin-coset, $J$ के किसी भी fixed point को बाहर रखता है।

इन शर्तों के तहत, प्रत्येक कोसेट $Q \cdot G_{n-1}$ और $Q^{-1} \cdot G_{n-1}$ में $2^{n-1}$ अलग-अलग बिंदु हैं, जिससे $D$ में कुल $2^n$ बिंदु होते हैं। सहज रूप से, हम एक कोसेट को उसके inverse कोसेट के साथ मिलाते हैं, जिससे $2^n$ तत्वों का एक डोमेन बनता है।

5.2.1 Twin-Coset Example

अनुभाग 5.1.1 में कोसेट उदाहरण (जहाँ हमने $Q=(2,11)$ चुना जो $G_1$ में नहीं है) को जारी रखते हुए, आइए अब आकार $2^n = 2^2 = 4$ का एक twin-coset बनाएं। हमने पहले ही देखा है:

Q \cdot G_1 \;=\; \{(2,\,11),\,(29,\,20)\}.

इसके बाद,

Q^{-1}=(2,\,20)

की गणना करें और कोसेट

Q^{-1}\cdot G_1

बनाएं:

Q^{-1} \,\cdot\, G_1 \;=\; \{\,(2,20)\cdot(1,0),\,(2,20)\cdot(30,0)\}

$(2,20)\cdot(1,0)\;=\;\bigl(2\cdot1 \;-\;20\cdot0,\;\;2\cdot0 \;+\;1\cdot20\bigr)\;=\;(2,\,20).$
$(2,20)\cdot(30,0)\;=\;\bigl(2\cdot30 \;-\;20\cdot0,\;\;2\cdot0 \;+\;30\cdot20\bigr)\;=\;(60,\,600)\;\equiv\;(29,\,11)\;\pmod{31}.$

अतः,

Q^{-1}\cdot G_1 \;=\; \{(2,\,20),\,(29,\,11)\}.

यूनियन (union) लेने पर, twin-coset यह है:

D \;=\; \bigl(Q \cdot G_1\bigr) \;\cup\; \bigl(Q^{-1}\cdot G_1\bigr) \;=\; \{(2,\,11),\,(29,\,20)\} \;\cup\; \{(2,\,20),\,(29,\,11)\}.

इस डोमेन

D

का आकार 4 है और यह twin-coset शर्तों को संतुष्ट करता है: दोनों कोसेट्स असंयुक्त (disjoint) हैं (चूंकि

Q^2\notin G_1

), और

D

में

y=0

वाला कोई बिंदु नहीं है, इसलिए involution

J(x,y)=(x,-y)

के तहत कोई fixed points नहीं हैं। इस प्रकार,

D

वास्तव में

2^2=4

आकार का एक twin-coset है।

5.3 Standard Position Cosets

एक standard position coset आकार $2^n$ का एक विशेष प्रकार का twin-coset $D$ है जो सबग्रुप $G_n$ के एकल कोसेट (single coset) के साथ भी मेल खाता है:

D \;=\; Q \cdot G_{n-1} \;\cup\; Q^{-1}\cdot G_{n-1} \;=\; Q \cdot G_n.

यहाँ, याद करें कि $G_n$ , $C(\mathbb{F}_p)$ का $2^n$ क्रम का अद्वितीय (unique) सबग्रुप है, जैसा कि पहले अनुभाग 3 में पेश किया गया था। हमारे पास सबग्रुप्स की एक श्रृंखला है:

G_0 \subset G_1 \subset \dots \subset G_n \subset \dots \subset C(\mathbb{F}_p),

और प्रत्येक $G_k$ का आकार $2^k$ है। इसलिए, $G_n$ में $G_{n-1}$ शामिल है, और हम $2^{n+1}$ क्रम के एक बिंदु $Q$ का उपयोग करके इन सबग्रुप्स के कोसेट्स को संबंधित करेंगे।

आइए इसे चरण दर चरण खोलें:

सबसे पहले, चूंकि $G_{n-1} \subset G_n$ है, हम $G_n$ को $G_{n-1}$ के दो असंयुक्त (disjoint) कोसेट्स से युक्त मान सकते हैं, अर्थात्:

G_n = G_{n-1} \cup R \cdot G_{n-1},\quad \text{for some } R \notin G_{n-1}.

यदि हम अब इसे

2^{n+1}

क्रम के एक निश्चित बिंदु

Q

से गुणा करते हैं, तो हमें प्राप्त होता है:

Q \cdot G_n = Q \cdot G_{n-1} \cup Q \cdot R \cdot G_{n-1}.

यह पता चलता है कि $Q \cdot R = Q^{-1}$ है, इसलिए:

Q \cdot G_n = Q \cdot G_{n-1} \cup Q^{-1} \cdot G_{n-1}.

इसलिए, कोसेट $Q \cdot G_n$ को दो असंयुक्त कोसेट्स के यूनियन के रूप में लिखा जा सकता है: एक $Q$ द्वारा, दूसरा $Q^{-1}$ द्वारा, प्रत्येक छोटे सबग्रुप $G_{n-1}$ पर। यह बिल्कुल twin-coset की परिभाषा है।

लेकिन सभी twin-cosets इस तरह से उत्पन्न नहीं होते हैं। यह सुनिश्चित करने के लिए कि यह निर्माण ठीक से काम करता है, हमें आवश्यकता है:

Disjointness: $Q^2 \notin G_{n-1}$ । अन्यथा, दोनों कोसेट्स ओवरलैप हो जाएंगे।
Involution के तहत कोई fixed points नहीं: परिणामी सेट $D$ में $y = 0$ वाले बिंदुओं से बचना चाहिए, ताकि involution $J(x, y) = (x, -y)$ का $D$ में कोई fixed points न हो।
सही क्रम (Correct order): $Q$ का क्रम $2^{n+1}$ होना चाहिए ताकि यह गारंटी दी जा सके कि $Q \cdot G_n$ ठीक $2^n$ अलग-अलग तत्वों को कवर करता है।

जब ये संतुष्ट हो जाते हैं, तो कोसेट $D = Q \cdot G_n$ एक standard position coset देता है: $2^n$ आकार का एक डोमेन जो एक साथ एक twin-coset और एक बड़े सबग्रुप का एकल कोसेट (single coset) है।

5.4 Hand-Computed Example: Twin-Cosets and Standard Position Cosets at $p=31$

नीचे, हम स्पष्ट करते हैं कि जब $p=31$ होता है तो twin-cosets और standard position cosets की धारणाएं कैसे लागू होती हैं। हमारे पास $p+1=32=2^5$ है, इसलिए सबग्रुप्स $G_1,\,G_2,\,G_3,\,G_4,\,G_5$ मौजूद हैं, जहाँ $|G_3|=8$ और $|G_2|=4$ है। हम $G_3$ के लिए standard position coset दिखाएंगे जो $D=Q \cdot G_2 \;\cup\; Q^{-1} \cdot G_2=Q \cdot G_3$ है।

5.4.1 Twin-Coset Construction

Setup
मान लें $n=3$ है। तब $G_2$ का आकार 4 है। 16 क्रम का एक बिंदु $Q$ चुनें (इसलिए $Q\notin G_3$ , लेकिन $Q \in G_4$ है)। ठोस रूप से, कोई $Q = (13,\,7)$ चुन सकता है।
Forming the Twin-Coset

$D= \bigl(Q \cdot G_2\bigr) \;\cup\; \bigl(Q^{-1}\cdot G_2\bigr).$

चूंकि $G_2$ में चार बिंदु $(1,0)$ , $(0,30)$ , $(30,0)$ , और $(0,1)$ हैं, प्रत्येक बिंदु को $Q = (13,\,7)$ या $Q^{-1}=(13,24)$ से गुणा किया जाता है।
1. $Q \cdot (1,0)=(13,7)$ ,
2. $Q \cdot (0,30)=(7,18)$ ,
3. $Q \cdot (30,0)=(18,24)$ ,
4. $Q \cdot (0,1)=(24,13)$ ,
5. $Q^{-1}\cdot(1,0)=(13,24)$ ,
6. $Q^{-1}\cdot(0,30)=(24,18)$ ,
7. $Q^{-1}\cdot(30,0)=(18,7)$ ,
8. $Q^{-1}\cdot(0,1)=(7,13)$ .

D= \bigl(Q \cdot G_2\bigr) \;\cup\; \bigl(Q^{-1}\cdot G_2\bigr)= \{(13,7),(7,18),(18,24),(24,13),(13,24),(24,18),(18,7),(7,13)\}

इन्हें मिलाने पर 8 अलग-अलग बिंदु मिलते हैं। $D$ का कोई भी तत्व $J$ द्वारा स्थिर (fixed) नहीं है, इसलिए $D$ आकार $2^3=8$ का एक twin-coset है। इन्हें मिलाने पर 8 अलग-अलग बिंदु मिलते हैं। $D$ का कोई भी तत्व $J$ द्वारा स्थिर (fixed) नहीं है, इसलिए $D$ आकार $2^3 = 8$ का एक twin-coset है।

नीचे दिए गए चित्र में, 🔴 लाल बिंदु $Q \cdot G_2$ का प्रतिनिधित्व करते हैं और 🔵 नीले बिंदु $Q^{-1} \cdot G_2$ का प्रतिनिधित्व करते हैं। साथ मिलकर, वे 8-पॉइंट twin-coset $D$ बनाते हैं।

5.4.2 Checking Standard Position coset

यह समान $D$ 8 आकार के किसी सबग्रुप $G_3$ के लिए $Q\cdot G_3$ के बराबर भी है, जिसका अर्थ है कि $D$ एक standard position coset है।

$G_3$ सबग्रुप $\{(1,0),(4,27),(0,30),(27,27),(30,0),(27,4),(0,1),(4,4)\}$ है, तब प्रत्येक तत्व को $Q=(13,7)$ से गुणा करने पर ठीक $D$ में मौजूद 8 बिंदु प्राप्त होते हैं।

$Q \cdot (1,\,0) = (13,\,7)$
$Q \cdot (4,\,27) = (18,\,7)$
$Q \cdot (0,\,30) = (7,\,18)$
$Q \cdot (27,\,27) = (7,\,13)$
$Q \cdot (30,\,0) = (18,\,24)$
$Q \cdot (27,\,4) = (13,\,24)$
$Q \cdot (0,\,1) = (24,\,13)$
$Q \cdot (4,\,4) = (24,\,18)$

Q \cdot G_3 \;=\; \{ (13,7),\,(18,7),\,(7,18),\,(7,13), (18,24),\,(13,24),\,(24,13),\,(24,18) \}.

अतः

D= Q\cdot G_3 = Q\cdot G_2 \;\cup\; Q^{-1}\cdot G_2.

क्योंकि $D$ दोनों $G_2$ का एक twin-coset और $G_3$ का एक एकल कोसेट (single coset) है, इसलिए हम इसे आकार 8 का एक standard position coset कहते हैं।

नीचे दिए गए चित्र में, 🟢 हरे बिंदु सबग्रुप $G_3$ का प्रतिनिधित्व करते हैं, 🔴 लाल और 🔵 नीले बिंदु क्रमशः दो असंयुक्त (disjoint) कोसेट्स $Q \cdot G_2$ और $Q^{-1} \cdot G_2$ का प्रतिनिधित्व करते हैं। उनका यूनियन (union) twin-coset $D$ बनाता है, और पूरा 8-पॉइंट सेट standard position coset $Q \cdot G_3$ का निर्माण करता है।

इस प्रकार, जब भी $Q$ का क्रम $2^{n+1}$ होता है, हम $2^n$ आकार का एक standard position coset बना सकते हैं। यह संरचना Circle STARK में महत्वपूर्ण है, क्योंकि यह $2^n$ बिंदुओं का एक स्पष्ट डोमेन प्रदान करती है, भले ही $p-1$ पर्याप्त रूप से two-adic न हो।

6. Python Code 2: Circle Domain

अब हम Simple Python इम्प्लीमेंटेशन के माध्यम से Circle Domain कोड की समीक्षा करेंगे। डोमेन निर्माण (जैसे twin-coset और standard position coset) भी उसी Python notebook में लागू किया गया है। आप इसे रन कर सकते हैं और निरीक्षण कर सकते हैं कि ये सेट चरण-दर-चरण कैसे बनाए जाते हैं।

6.1 Twin-Coset

यह फ़ंक्शन सबग्रुप पर $Q$ और उसके inverse $Q^{-1}$ के लिए ग्रुप ऑपरेशन add लागू करके एक डोमेन उत्पन्न करता है, जिससे समरूपता (symmetry) और आकार $2^n$ सुनिश्चित होता है।

def generate_twin_coset(Q, G_n_minus_1):
    """Generate twin-coset: D = Q・G_(n-1) ∪ Q^{-1}・G_(n-1)."""
    Q_inv = Q.inverse()
    coset_Q = [Q.add(g) for g in G_n_minus_1]
    coset_Q_inv = [Q_inv.add(g) for g in G_n_minus_1]
    return coset_Q + coset_Q_inv

G2 = generate_subgroup(2)
Q = CirclePoint(FieldElement(13), FieldElement(7))
twin_cosets = generate_twin_coset(Q, G2)
print(twin_cosets)

[Point(13, 7), Point(7, 18), Point(18, 24), Point(24, 13), Point(13, 24), Point(24, 18), Point(18, 7), Point(7, 13)]

6.2 Standard Position Coset

यह फ़ंक्शन $Q$ और सबग्रुप के लिए ग्रुप ऑपरेशन add लागू करके standard position coset उत्पन्न करता है।

def generate_standard_position_coset(Q, G_n):
    """Generate standard position coset D = Q・G_n."""
    return [Q.add(g) for g in G_n]

G3 = generate_subgroup(3)
Q = CirclePoint(FieldElement(13), FieldElement(7))
D = generate_standard_position_coset(Q, G3)

[Point(13, 7), Point(18, 7), Point(7, 18), Point(7, 13), Point(18, 24), Point(13, 24), Point(24, 13), Point(24, 18)]

इस तरह के कोड से, आप standard position coset की समानता $D \;=\;Q \,\cdot\, G_{n-1}\;\cup\;Q^{-1} \,\cdot\, G_{n-1}\;=\;Q \,\cdot\, G_n$ की जांच कर सकते हैं।

D_std = generate_standard_position_coset(Q, G3)
D_twin = generate_twin_coset(Q, G2)
print("Q・G3:", D_std)
print("(Q・G2) ∪ (Q^-1・G2):", D_twin)
if set(D_std) == set(D_twin):
    print("Equal: standard position coset Q·G3 = Q·G2 ∪ Q^-1·G2")
else:
    print("Not Equal")

7. Decomposition of a Larger Standard Position Coset into Smaller Twin-Cosets

Circle FFT और FRI के कई चरणों में, हमें विभिन्न आकारों के मूल्यांकन डोमेन को प्रबंधित करने की आवश्यकता होती है, जो सभी circle वक्र (curve) पर स्थित होते हैं। इसे प्राप्त करने की एक प्रमुख विधि Circle STARKs paper से Lemma 2 है, जो यह सुनिश्चित करती है कि किसी भी $n \le m$ के लिए आकार $2^m$ के standard position coset को $2^n$ आकार के छोटे twin-cosets में तोड़ा जा सकता है।

7.1 Statement of Lemma 2

मान लें कि $D \subset C(\mathbb{F}_p)$ आकार $2^m$ का एक standard position coset है। तो किसी भी $n \le m$ के लिए, कोई $D$ को $2^n$ आकार के twin-cosets में विघटित (decompose) कर सकता है। ठोस रूप से, यदि

D \;=\; Q \cdot G_m \quad \text{where}\quad |G_m| = 2^m,

तो

D = \bigcup_{k=0}^{\left(\frac{2^m}{2^n}\right)-1} \Bigl( Q^{4k+1} \cdot G_{n-1} \cup Q^{-(4k+1)} \cdot G_{n-1} \Bigr)

सरल शब्दों में, यदि $D$ , $2^m$ आकार का एक standard position coset है, तो हम $Q$ की घातों (powers of $Q$ ) का उपयोग करके इसे छोटे twin-cosets (प्रत्येक $2^n$ आकार का) में विभाजित कर सकते हैं। यह विभाजन किसी को $D$ के ठीक उसी हिस्से को बनाने की अनुमति देता है जिसकी आवश्यकता Circle FFT प्रोटोकॉल के किसी दिए गए चरण में होती है।

7.2 Hand-Computed Example: Splitting a Size- $8$ standard position coset into 2 Twin-Cosets of Size $4$

मान लें कि $p = 31$ , तो $p+1 = 32 = 2^5$ है। हमारे पास सबग्रुप्स $G_1, G_2, G_3, \dots$ हैं, जहाँ $\lvert G_3\rvert=8$ है।

Our standard position coset
मान लें $D = Q \cdot G_3$ जहाँ $\lvert D\rvert=8$ है। यहाँ, $Q$ का क्रम 16 है, जिसका अर्थ है $Q\notin G_3$ लेकिन $Q \cdot G_3$ , 8 आकार का एक कोसेट बनाता है।

D= \bigl(Q \cdot G_2\bigr) \;\cup\; \bigl(Q^{-1}\cdot G_2\bigr)= Q\cdot G_3 = \{(13,7),(7,18),(18,24),(24,13),(13,24),(24,18),(18,7),(7,13)\}

Goal
$D$ को $2^n=4$ आकार के twin-cosets में तोड़ें। मान लें $n=2$ , इसलिए $\lvert G_2\rvert=4$ और $\lvert G_1\rvert=2$ है।
तब Lemma 2 सुझाव देता है

$D= \bigcup_{k=0}^{(8/4)-1} \Bigl( Q^{\,4k+1}\cdot G_{1} \;\cup\; Q^{-\,\bigl(4k+1\bigr)}\cdot G_{1} \Bigr).$

चूंकि $8/4=2$ है, हमारे पास $k=0$ और $k=1$ है।

7.2.1 Case $k=0$

$Q^{4\cdot0+1}=Q^1=Q$ ।
$G_1=\{(1,0), (30,0)\}$ ।

गणना करें:

$Q\cdot(1,0) = (13,7)$
$Q\cdot(30,0) = (18,24)$
$Q^{-1}\cdot(1,0) = (13,24)$
$Q^{-1}\cdot(30,0) = (18,7)$

इस प्रकार, पहले twin-coset में 4 अलग-अलग बिंदु हैं।

7.2.2 Case $k=1$

$Q^{4\cdot1+1} = Q^5$ ।
यानी $Q^5 = (24,13)$ ।
इसी तरह, $Q^{-5} = (24, -13)\equiv (24,18)$ ।

फिर से, प्रत्येक को $(1,0)$ और $(30,0)$ से गुणा करें:

$Q^5\cdot(1,0) = (24,13)$
$Q^5\cdot(30,0) = (7,18)$
$Q^{-5}\cdot(1,0) = (24,18)$
$Q^{-5}\cdot(30,0) = (7,13)$

इससे 4 और बिंदु प्राप्त होते हैं, जो 4 आकार का दूसरा twin-coset बनाते हैं।

7.2.3 Union of the Two Twin-Cosets

दोनों 4-पॉइंट सेट ( $k=0$ और $k=1$ के लिए) का यूनियन (union) लेने पर पूरा 8-तत्वों वाला कोसेट $D$ वापस मिल जाता है। अतः:

D=\Bigl( Q^1 \cdot G_1 \;\cup\; Q^{-1} \cdot G_1 \Bigr) \;\;\cup\;\; \Bigl( Q^5 \cdot G_1 \;\cup\; Q^{-5} \cdot G_1 \Bigr).

यह ठीक Lemma 2 के कथन से मेल खाता है, जो यह दर्शाता है कि कैसे एक 8-पॉइंट standard position coset को प्रत्येक 4 आकार के दो twin-cosets में विघटित किया जा सकता है।

7.3 Hand-Computed Example: Splitting a Size- $8$ standard position coset into 4 Twin-Cosets of Size $2$

और हम इस आकार-8 के standard position coset को कई छोटे twin-cosets में भी विभाजित कर सकते हैं।

मान लें $n=1$ , इसलिए $\lvert G_1\rvert=2$ है। Lemma 2 देता है:

D = \bigcup_{k=0}^{(8/2)-1} \Bigl( Q^{4k+1}\cdot G_0 \;\cup\; Q^{-\,(4k+1)}\cdot G_0 \Bigr).

चूंकि $G_0 = \{(1,0)\}$ है, प्रत्येक twin-coset में 2 बिंदु हैं:

$k=0$ : $\{Q^1 \cdot G_0 = Q, Q^{-1} \cdot G_0 = Q^{-1}\}$ $=\{(13, 7), (13, 24)\}$
$k=1$ : $\{Q^5 \cdot G_0 = Q^5, Q^{-5} \cdot G_0 = Q^{-5}\}$ $
={(24, 13), (24, 18)}$
$k=2$ : ${Q^9 \cdot G_0 = Q^9, Q^{-9} \cdot G_0 = Q^{-9}}
$ $=\{(18, 24), (18, 7)\}$
$k=3$ : $\{Q^{13} \cdot G_0 = Q^{13}, Q^{-13} \cdot G_0 = Q^{-13}\}$ $
={(7, 18), (7, 13)}$
$D = \{(13,7),(13,24)\} \cup \{(24,13),(24,18)\} \cup \{(18,24),(18,7)\} \cup \{(7,18),(7,13)\}$
यह $D$ को $2$ आकार के चार twin-cosets में विघटित कर देता है।

8. Squaring Map Halves a Twin-Coset

जहाँ Lemma 2 बड़े कोसेट्स को छोटे twin-cosets में विभाजित करने पर केंद्रित है, वहीं Lemma 3 एक twin-coset के आकार को आधा करने के लिए squaring map का लाभ उठाता है। इस प्रक्रिया का उपयोग Circle FFT में डोमेन को आधा करने वाले चरणों के लिए किया जाता है, जहाँ हम डोमेन के आकार को क्रमिक रूप से कम करते हैं।

8.1 Statement of Lemma 3

यह प्रमेयिका (lemma) Circle STARKs paper में प्रकट होती है, जहाँ इसका उपयोग squaring map द्वारा सक्षम पुनरावर्ती (recursive) डोमेन हाल्विंग (halving) को औपचारिक रूप देने के लिए किया जाता है।
मान लीजिए $D$ , $2^n$ आकार (जहाँ $n \ge 2$ ) का एक twin-coset है। तो squaring map $\pi(x,y) = (x^2 - y^2,\,2xy)$ लागू करने से $D$ , $2^{n-1}$ आकार के एक अन्य twin-coset $\pi(D)$ में बदल जाता है। इसके अलावा, यदि $D$ एक standard position coset था, तो $\pi(D)$ भी एक standard position coset ही रहता है।
सहज रूप से, $\pi$ एक ग्रुप एंडोमोर्फिज़्म (group endomorphism) है, और यह सबग्रुप $G_{n-1}$ को $G_{n-2}$ में मैप करता है। इसलिए, $2^n$ आकार का एक twin-coset स्वाभाविक रूप से $2^{n-1}$ आकार का एक और twin-coset देता है।

8.1.1 Abstract View of Lemma 3’s Proof

मान लें कि $D$ , $2^n$ आकार का एक twin-coset है, जिसका एक अमूर्त (abstract) संकेतन में अर्थ है

D = Q \cdot G_{n-1} \;\cup\; Q^{-1}\cdot G_{n-1},

जहाँ

|G_{n-1}| = 2^{n-1}

है।
विशेष रूप से,

\pi

ग्रुप एंडोमोर्फिज़्म (group endomorphism) के कारण सबग्रुप

G_{n-1}

को

G_{n-2}

पर मैप करता है।

\pi(D) \;=\; \pi\!\Bigl(Q \cdot G_{n-1} \cup Q^{-1}\cdot G_{n-1}\Bigr)= \bigl(\pi(Q) \cdot G_{n-2}\bigr) \;\cup\; \bigl(\pi(Q)^{-1} \cdot G_{n-2}\bigr).

यह ठीक सबग्रुप

G_{n-2}

में एक twin-coset की परिभाषा है, जिसका आकार

2^{n-2}

है। तदनुसार,

\pi(D)

स्वयं

2^{n-1}

आकार का एक twin-coset है।
यदि

D

मूल रूप से एक standard position coset था, तो

\pi

लागू करने से वह standard position गुण संरक्षित रहता है, क्योंकि

\pi(G_n) = G_{n-1}

है। इस प्रकार

\pi(D)

फिर से एक standard position coset है, लेकिन अब

2^{n-1}

आकार का है।

8.2 Hand-Computed Example (Halving a Size- $8$ Twin-Coset to Size $4$ )

मान लें $p=31$ है और मान लें कि $D$ आकार $2^3=8$ का एक twin-coset है। ठोस रूप से,

D = Q\cdot G_2 \;\cup\; Q^{-1}\cdot G_2 \quad\text{with}\quad Q=(13,7).

चूँकि

\lvert G_2\rvert=4

, हमारे पास

\lvert D\rvert=8

है। हम जाँच करते हैं कि

\pi

D

को कैसे प्रभावित करता है:

8.2.1 Computing $\pi(Q)$ and $\pi(Q^{-1})$

\pi(Q)= \bigl(13^2 - 7^2,\;2\cdot13\cdot7\bigr)= (27,\,27),

\pi(Q^{-1})= (27,\,4).

8.2.2 Applying $\pi$ to $D$

सबग्रुप $G_1$ का आकार 2 है, मान लें $G_1 = \{(1,0), (30,0)\}$ है। Lemma 3 द्वारा,

\pi(D) = \bigl(\pi(Q)\cdot G_1\bigr) \cup \bigl(\pi(Q)^{-1}\cdot G_1\bigr).

$$
\begin{align*}
\pi(Q)\cdot(1,0) &= (27,27)\
\pi(Q)\cdot(30,0) &= (4,4)\
\pi(Q^{-1})\cdot(1,0) &= (27,4)\
\pi(Q^{-1})\cdot(30,0) &= (4,27)

\end{align*}

{(27,27), (4,4)}
\cup
{(27,4), (4,27)}$$
जो कि आकार 4 का एक twin-coset है।
इस प्रकार,

\pi

D

को 8 तत्वों से घटाकर 4 कर देता है, ठीक वैसा ही जैसा Lemma 3 बताता है।

\pi

का बार-बार अनुप्रयोग (application) डोमेन को 2 की घातों में छोटा करना जारी रखता है, जो Circle FFT की पुनरावर्ती संरचना (recursive structure) में एक महत्वपूर्ण भूमिका निभाता है।
नीचे दिए गए चित्र में:

बायां वृत्त मूल twin-coset $D = Q \cdot G_2 \cup Q^{-1} \cdot G_2$ दिखाता है, जहाँ 🔴 लाल = $Q \cdot G_2$ और 🔵 नीला = $Q^{-1} \cdot G_2$ है।
दायां वृत्त आधा किया हुआ twin-coset $\pi(D)$ दिखाता है, जहाँ 🔵 नीला = $\pi(Q) \cdot G_1$ और 🔴 लाल = $\pi(Q^{-1}) \cdot G_1$ है।
⚫ काले बिंदु सबग्रुप $G_1 = \{(1, 0), (30, 0)\}$ को चिह्नित करते हैं।
यह दृश्य स्पष्ट करता है कि $\pi$ कैसे ग्रुप एंडोमोर्फिज़्म (group endomorphism) के माध्यम से $2^3 = 8$ आकार के मूल डोमेन को $2^2 = 4$ आकार के एक नए twin-coset में मैप करता है।

9. What We Built in Part 1

इस लेख में, हमने इस बात पर ध्यान केंद्रित किया कि कैसे $\mathbb{F}_p$ पर circle वक्र $x^2 + y^2 = 1$ को $p + 1$ आकार के एक चक्रीय समूह (cyclic group) में बदला जा सकता है, और हमने ठोस उदाहरणों के साथ twin-cosets और standard position cosets पर चर्चा की। हमने दो प्रमुख तकनीकें भी दिखाईं: एक बड़े standard position coset को छोटे twin-cosets में विभाजित करने के लिए, और दूसरी squaring map को लागू करके twin-coset के आकार को आधा करने के लिए। एक साथ, ये तकनीकें हमें $2^n$ आकार के डोमेन को अपनी इच्छानुसार नया आकार देने (reshape) की अनुमति देती हैं।
अगले भाग में, हम स्वयं Circle FFT में और गहराई तक जाएंगे, यह दिखाते हुए कि कैसे ये $2^n$ -आकार के डोमेन—उन्हें विभाजित करने या आधा करने की क्षमता के साथ—तेज़ बहुपद मूल्यांकन (polynomial evaluation) और इंटरपोलेशन (interpolation) को सक्षम करते हैं, तब भी जब $p - 1$ पर्याप्त रूप से two-adic न हो।

References

Circle STARKs
https://eprint.iacr.org/2024/278
Plonky3
https://github.com/Plonky3/Plonky3
ZK11: Circle STARKs - Ulrich Haböck & Shahar Papini
https://youtu.be/NAhLYMysSdk?si=OlzNKS1DSTRkPnUR
Circle STARKs: Part I, Mersenne
https://blog.zksecurity.xyz/posts/circle-starks-1/
Why I’m Excited By Circle Stark And Stwo
https://starkware.co/integrity-matters-blog/why-im-excited-by-circle-stark-and-stwo/
Exploring circle STARKs
https://vitalik.eth.limo/general/2024/07/23/circlestarks.html
An introduction to circle STARKs
https://blog.lambdaclass.com/an-introduction-to-circle-starks/
Yet another circle STARK tutorial
https://research.chainsafe.io/blog/circle-starks/
Deep dive into Circle-STARKs FFT
https://ihagopian.com/posts/deep-dive-into-circle-starks-fft
Coset’s Circle STARKs lecture videos
https://youtube.com/playlist?list=PLbQFt1T_44DyihAOawprEABRPWgYeXB5u&si=AJe0dP7FUfp2Bebe
Ethereum/research/circlestark(Python implementation)
https://github.com/ethereum/research/tree/master/circlestark
Rust Implementation Demo of Circle Domain and Circle FFT
https://youtu.be/ur3c4mIi1Jc?si=lxU10mZ6vOFCrzvw
https://github.com/0xxEric/CircleFFT
STARKの原理
https://zenn.dev/qope/articles/8d60f77e3a7630

Appendix

नीचे, हम circle वक्र के Projective बनाम Affine दृष्टिकोण (view) का परिचय देते हैं, और फिर समझाते हैं कि Circle STARKs विशेष रूप से $p \equiv 3 \pmod{4}$ वाले primes को क्यों चुनते हैं ताकि points at infinity जैसी प्रोजेक्टिव जटिलताओं (projective complications) से बचा जा सके।

A.1 Projective and Affine

$\mathbb{F}_p$ पर एक affine plane में, एक बिंदु को केवल $(x,y)$ के रूप में लिखा जाता है जहाँ $x,y \in \mathbb{F}_p$ है। इसके विपरीत, projective plane $\mathbb{P}^2(\mathbb{F}_p)$ में, प्रत्येक बिंदु को $(X : Y : Z)$ द्वारा दर्शाया जाता है, लेकिन सभी गैर-शून्य अदिश गुणज (nonzero scalar multiples) समान स्थान का प्रतिनिधित्व करते हैं। औपचारिक रूप से,

(X : Y : Z) \;\equiv\; (\lambda X : \lambda Y : \lambda Z)\quad (\lambda \neq 0).

जब $Z \neq 0$ होता है, तो हम प्रत्येक निर्देशांक (coordinate) को $Z$ से विभाजित करके फिर से स्केल कर सकते हैं, जिससे एक affine बिंदु $\bigl(X/Z,\;Y/Z\bigr)$ प्राप्त होता है।
जब $Z=0$ होता है, तो हमें अनंत पर एक बिंदु (point at infinity) प्राप्त होता है, जिसका कोई affine समकक्ष (counterpart) नहीं होता है।

A.2 Why Avoid Points at Infinity?

यह देखने के लिए कि points at infinity कैसे उत्पन्न होते हैं, $x^2 + y^2 = 1$ को projective रूप में फिर से लिखें:

X^2 + Y^2 \;=\; Z^2.

यहाँ, यदि

Z \neq 0

है, तो हम

x = X/Z

और

y = Y/Z

मानते हैं, इसलिए

x^2 + y^2 = 1

X^2 + Y^2 = Z^2

बन जाता है।
Point at infinity

Z=0

के साथ कोई भी समाधान है। क्या ऐसे समाधान मौजूद हैं, यह इस बात पर निर्भर करता है कि

-1

\mathbb{F}_p

में एक वर्ग (square) है या नहीं:

उदाहरण के लिए, यदि $p \equiv 1 \pmod{4}$ है, तो $-1$ , $\mathbb{F}_p$ में एक वर्ग है।
ठोस रूप से, कोई $a$ है जिसके लिए $a^2 \equiv -1 \pmod{p}$ है, जिसका अर्थ है कि $X^2 + Y^2 \equiv 0 \pmod{p}$ का $Z=0$ पर गैर-शून्य $(X,Y)$ हो सकता है।
यह circle पर अतिरिक्त अनंत बिंदु (infinite points) देता है, जिससे समूह संक्रियाएं (group operations) और इम्प्लीमेंटेशन जटिल हो जाता है।
उदाहरण: $p=5$
- यहाँ, $-1 \equiv 4$ , $\mathbb{F}_5$ में है, और $4$ वास्तव में $(2^2)$ है।
- इसलिए $X^2 + Y^2 \equiv 0 \pmod{5}$ , $Z=0$ पर गैर-शून्य $(X,Y)$ की अनुमति देता है, जिससे अनंत पर दो बिंदु (points at infinity) मिलते हैं।
- Affine समीकरण $x^2 + y^2=1$ के ठीक चार affine समाधान हैं:
  
  $\{(0,1),\,(0,4),\,(1,0),\,(4,0)\}.$
और अनंत पर projective बिंदु हैं
$\{(2:1:0), (3:1:0)\}$ , कुल $6$ समाधान हैं — जो $p+1=6$ (affine $4$ + अनंत $2$ ) से मेल खाते हैं।
यदि $p \equiv 3 \pmod{4}$ है, तो $-1$ , $\mathbb{F}_p$ में एक वर्ग (square) नहीं है।
नतीजतन, $X^2 + Y^2 \equiv 0 \pmod{p}$ का $Z=0$ पर कोई गैर-शून्य समाधान नहीं है। हमें अनंत पर कोई बिंदु नहीं मिलता है, और सभी समाधान affine रहते हैं।
उदाहरण: $p=3$
- चूँकि $-1 \equiv 2 \pmod{3}$ एक वर्ग नहीं है (हमारे पास $1^2 \equiv 1$ और $2^2 \equiv 1$ है), कोई भी $(X,Y)$ , $Z=0$ पर $X^2+Y^2\equiv0$ को संतुष्ट नहीं करता है।
- समीकरण $x^2 + y^2=1$ के तब केवल affine समाधान होते हैं। $x,y \in \{0,1,2\}$ की जाँच करने पर प्राप्त होता है:
  
  $\{(0,1),\,(0,2),\,(1,0),\,(2,0)\},$
  कुल $4$ समाधानों के लिए, जो $p+1=4$ से मेल खाते हैं।

Circle STARK में, हम विशेष रूप से $p \equiv 3 \pmod{4}$ चुनते हैं ताकि $-1$ , $\mathbb{F}_p$ में वर्ग (square) न हो। यह सुनिश्चित करता है कि हमारे वृत्त $x^2 + y^2=1$ में कोई अनंत (projective) बिंदु नहीं है, जिससे हर समाधान affine निर्देशांक में रहता है और points at infinity को संभालने की जटिलताओं से बचा जाता है।