एक फाइनाइट फील्ड (Number Theoretic Transform) में FFT एल्गोरिदम को निष्पादित करने के लिए, $k$-th roots of unity का होना आवश्यक है जहाँ $k$, 2 की एक घात (power of 2) है।

आदर्श रूप से, हम 2 की एक बड़ी घात चाहते हैं ताकि हम बड़े पॉलिनॉमियल्स (polynomials) को गुणा कर सकें। कई आमतौर पर उपयोग किए जाने वाले फाइनाइट फील्ड्स हैं (जिनमें से लगभग सभी के साथ एक आकर्षक नाम जुड़ा हुआ है)। यह लेख कुछ अधिक सामान्य फील्ड्स को सूचीबद्ध करता है।

एक संक्षिप्त परिभाषा के रूप में, किसी फील्ड का characteristic वह अभाज्य संख्या (prime number) है जिसके साथ हम मॉड्यूलस (modulus) लेते हैं, इसलिए फाइनाइट फील्ड $\mathbb{F}_q$ में, $q$ characteristic है। (यदि हम फाइनाइट फील्ड एक्सटेंशन पर विचार करते हैं तो इस परिभाषा के साथ कुछ बारीकियाँ हैं, लेकिन हम अभी उस पर नहीं जाना चाहते हैं। हमारे उद्देश्यों के लिए, $q$ एक अभाज्य संख्या है और फाइनाइट फील्ड का characteristic है)।

जैसा कि हमने Fundamental Theorem of Finite Cyclic Groups में देखा, एक सबग्रुप (subgroup) तब मौजूद होता है जब सबग्रुप का क्रम (order) ग्रुप के क्रम को विभाजित करता है।

इसलिए, यदि फील्ड FFT-फ्रेंडली है, तो वहां कोई $k$ ऐसा मौजूद होता है कि $k|(q-1)$ और $k$, 2 की एक बड़ी घात है। दूसरे शब्दों में, $q-1$, 2 की एक बड़ी घात से विभाज्य है।

यहाँ दी गई सूची पूर्ण नहीं है — हम प्रकाशन के समय केवल अपेक्षाकृत प्रसिद्ध (well-known) फील्ड्स को ही शामिल कर रहे हैं।

FFT-फ्रेंडली फील्ड्स की सूची

Goldilocks Field

Goldilocks फील्ड का characteristic $q=2^{64}-2^{32}+1$ है और इसमें एक $2^{32}$-th root of unity है।

निम्नलिखित Python कोड यह प्रमाणित करता है कि इस फील्ड में $2^{32}$ क्रम का एक multiplicative subgroup मौजूद है।

Copy
q = 2**64 - 2**32 + 1
k = 2**32
assert (q - 1) % k == 0

चूंकि characteristic 64 बिट्स से छोटा है, इसलिए अधिकांश आधुनिक हार्डवेयर (जो आमतौर पर 64 बिट्स के होते हैं) पर इसके एलिमेंट्स को सिंगल वर्ड (single word) में स्टोर किया जा सकता है।

हालाँकि, दो 64-बिट संख्याओं को एक साथ गुणा करने के लिए अस्थायी रूप से 128 बिट्स की आवश्यकता होती है, जिसके लिए गुणा करने हेतु एक अतिरिक्त रजिस्टर (register) की आवश्यकता होती है।

यह एक छोटे फील्ड के उपयोग को प्रेरित करता है जो केवल 32 बिट्स का उपयोग करता है।

Baby Bear Field

Baby Bear फील्ड एक characteristic $2^{31} - 2^{27} + 1$ का उपयोग करता है। इसमें एक $2^{27}$-th root of unity है।

Copy
q = 2**31 - 2**27 + 1
k = 2**27
assert (q - 1) % k == 0

“Baby Bear” नाम Goldilocks’ fairytale पर आधारित एक रूपांतर है, जहाँ कहानी मुख्य पात्र (Goldilocks) की तुलना में Baby Bear के छोटे आकार पर जोर देती है।

चूंकि यह फील्ड 32 बिट्स में फिट हो जाता है, इसलिए एक 64-बिट कंप्यूटर दो एलिमेंट्स को एक सिंगल वर्ड में एक साथ गुणा कर सकता है।

Teddy Bear Field

Teddy Bear Field $2^{32}-2^{30}+1$ characteristic का उपयोग करता है और इसमें एक $2^{30}$-th root of unity है।

Copy
q = 2**32 - 2**30 + 1
k = 2**30
assert (q - 1) % k == 0

Baby Bear फील्ड की तुलना में, यह 32 बिट्स के अंदर फिट बैठता है, लेकिन इसमें एक बड़ा multiplicative subgroup होता है जो आठ गुना बड़ा है।

Teddy Bear फील्ड को Ingonyama द्वारा इस paper में पेश किया गया था।

Koala Bear Field

Koala Bear Field एक और फील्ड है जिसका characteristic $2^{31} - 2^{24} + 1$, 32 बिट्स में फिट बैठता है और इसमें एक $2^{24}$-th root of unity है।

Copy
q = 2**31 - 2**24 + 1
k = 2**24
assert (q - 1) % k == 0

BN-128 field

BN-128 फील्ड का उपयोग elliptic curve pairings के इसके समर्थन के लिए किया जाता है, लेकिन इसमें अपेक्षाकृत बड़ा multiplicative subgroup भी है जिसका क्रम $2^{28}$ है।

Copy
# curve_order = 21888242871839275222246405745257275088548364400416034343698204186575808495617
from py_ecc.bn128 import curve_order
k = 2**28
assert (curve_order - 1) % k == 0

The STARK Field

Starknet द्वारा उपयोग किए जाने वाले Cairo VM का characteristic $2^{251}+17\cdot2^{192}+1$ है और इसमें एक बहुत बड़ा $2^{192}$-th root of unity है।

Copy
q = 2**251 + 17*2**192 + 1
k = 2**192
assert (q - 1) % k == 0

The BLS12-381

BLS12-381 एक और पेयरिंग-फ्रेंडली (pairing-friendly) इलिप्टिक कर्व (elliptic curve) है जिसके कर्व ऑर्डर (curve order) में एक $2^{32}$-th root of unity है।

Copy
# curve_order = 52435875175126190479447740508185965837690552500527637822603658699938581184513
from py_ecc.bls12_381 import curve_order
k = 2**32
assert (curve_order - 1) % k == 0

लाइब्रेरी सपोर्ट

Plonky3 library में Goldilocks, Baby Bear, और Koala Bear के लिए लाइब्रेरीज़ (libraries) हैं।