🔢 mathematics

Primitive-Root Determinant Densities over Prime Fields and Implications for PRIM-LWE

यह शोध पत्र प्राइम-एलडब्ल्यूई (PRIM-LWE) समस्या के लिए डाइमेंशन-यूनिफॉर्म रिडक्शन कांस्टेंट (dimension-uniform reduction constant) से संबंधित एक खुले प्रश्न को बिना किसी शर्त के हल करता है, यह सिद्ध करते हुए कि प्राइम फील्ड्स पर प्रिमिटिव-रूट डिटर्मिनेंट्स (primitive-root determinants) वाली मैट्रिसेस का घनत्व $\Theta(1/\log\log x)$ द्वारा निम्न स्तर पर सीमित है, जिससे प्रिमोरियल प्राइम्स (primorial primes) के बारे में अपुष्ट अनुमानों पर निर्भर किए बिना क्रिप्टोग्राफिक मॉड्युली के लिए स्पष्ट ओवरहेड बाउंड्स स्थापित होते हैं।

मूल लेखक: Vipin Singh Sehrawat

प्रकाशित 2026-03-13

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Vipin Singh Sehrawat

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

यहाँ सरल भाषा, उपमाओं और रूपकों का उपयोग करके पेपर की व्याख्या दी गई है।

बड़ी तस्वीर: गुप्त कुंजियों (Secret Keys) के लिए एक लॉटरी

कल्पना कीजिए कि आप डिजिटल पैसे या संदेशों की सुरक्षा के लिए एक उच्च-सुरक्षा वाली तिजोरी (एक क्रिप्टोग्राफिक सिस्टम) बना रहे हैं। तिजोरी को लॉक करने के लिए, आपको एक गुप्त कुंजी (secret key) की आवश्यकता होगी। PRIM-LWE नामक आधुनिक एन्क्रिप्शन के एक विशिष्ट प्रकार में, इस कुंजी के लिए एक विशेष नियम है: इसे एक "विशेष संख्या" (गणितीय रूप से, एक प्रिमिटिव-रूट डिटरमिनेंट वाली मैट्रिक्स) होनी चाहिए।

इन विशेष संख्याओं को एक विशाल लॉटरी में गोल्डन टिकटों (Golden Tickets) के रूप में सोचें।

यदि आप अपनी कुंजी के रूप में एक यादृच्छिक (random) संख्या चुनते हैं, तो इसकी एक निश्चित संभावना है कि वह एक गोल्डन टिकट हो।
यदि आप ऐसी संख्या चुनते हैं जो गोल्डन टिकट नहीं है, तो सुरक्षा प्रणाली टूट जाती है, या आपको तब तक नई संख्याएँ चुननी पड़ती हैं जब तक कि आपको वह संख्या न मिल जाए जो काम करती है। इस "मिलने तक चुनने" की प्रक्रिया को रिजेक्शन सैंपलिंग (rejection sampling) कहा जाता है।

यह पेपर एक बहुत ही महत्वपूर्ण प्रश्न पूछता है: ये गोल्डन टिकट कितने दुर्लभ हैं?

समस्या: क्या गोल्डन टिकट गायब हो रहे हैं?

लंबे समय से, गणितज्ञों को पता था कि अधिकांश संख्याओं के लिए, गोल्डन टिकट इतने सामान्य हैं कि उन्हें आसानी से पाया जा सकता है। लेकिन वे "सबसे खराब स्थिति" (worst-case scenario) को लेकर चिंतित थे।

उन्होंने पूछा: "क्या किसी विशिष्ट प्रकार की संख्या (एक प्राइम मोडुलस) है जहाँ गोल्डन टिकट इतने अविश्वसनीय रूप से दुर्लभ हो जाते हैं कि आपको एक खोजने के लिए अरबों साल तक इंतजार करना पड़ सकता है?"

यदि उत्तर "हाँ" होता, तो इसका मतलब यह होता कि कुछ विशिष्ट सेटिंग्स के लिए, यह एन्क्रिप्शन विधि अविश्वसनीय रूप से धीमी और अक्षम हो जाती है।

खोज: "धीरे-धीरे लुप्त होता" टिकट

लेखक, विपिन सिंह सेहरावत, दो मुख्य बातें सिद्ध करते हैं:

1. "बुरी खबर" (सैद्धांतिक रूप से):
हाँ, आप ऐसी संख्याएँ पा सकते हैं जहाँ गोल्डन टिकट अत्यंत दुर्लभ होते हैं। वास्तव में, यदि आप संख्याओं की एक विशाल सूची देखते हैं, तो "सबसे दुर्लभ" संख्याएँ जैसे-जैसे सूची बढ़ती है, और भी दुर्लभ होती जाती हैं। पेपर यह सिद्ध करता है कि इन टिकटों का घनत्व (density) शून्य के अत्यंत करीब पहुँच सकता है।

उपमा: एक समुद्र तट की कल्पना करें जिसमें रेत है। अधिकांश समय, आप आसानी से एक सुनहरा कण पा सकते हैं। लेकिन यदि आप समुद्र तट पर और आगे चलते रहते हैं, तो आप अंततः एक ऐसा हिस्सा पा सकते हैं जहाँ सुनहरे कण इतने विरल (sparse) हैं कि आपको एक खोजने के लिए घंटों खुदाई करनी पड़ती है। पेपर सिद्ध करता है कि यह "विरल हिस्सा" मौजूद है, लेकिन यह अविश्वसनीय रूप से धीरे-धीरे वहाँ पहुँचता है।

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

उपमा: पेपर यह गणना करता है कि उस समुद्र तट के हिस्से को खोजने के लिए जहाँ सुनहरे कण वास्तव में दुर्लभ हैं, आपको इतनी विशाल दूरी तय करनी होगी जो ब्रह्मांड की आयु से भी अधिक समय ले लेगी।
परिणाम: वास्तविक दुनिया के सुरक्षा मानकों (जैसे ML-KEM और ML-DSA के लिए NIST मानक) में उपयोग किए जाने वाले विशिष्ट नंबरों के लिए, गोल्डन टिकट वास्तव में काफी सामान्य हैं। एक वैध कुंजी खोजने के लिए आपको औसतन केवल 2 से 4 संख्याएँ ही चुननी पड़ती हैं। यह एक छोटा, प्रबंधनीय खर्च है।

वितरण का "आकार" (The Shape of the Distribution)

यह पेपर इन संख्याओं के "परिदृश्य" (landscape) का भी मानचित्रण करता है।

एक पर्वत श्रृंखला की कल्पना करें जहाँ ऊँचाई यह दर्शाती है कि गोल्डन टिकट कितने सामान्य हैं।
पेपर दिखाता है कि यह परिदृश्य सतत (continuous) है। ऐसी कोई अचानक ढलान नहीं है जहाँ टिकट तुरंत गायब हो जाते हैं। इसके बजाय, टिकटों की "सामान्यता" बहुत सामान्य (लगतः 50% समय) से लेकर बहुत दुर्लभ तक सुचारू रूप से बदलती है।
यह भी सामने आया कि किसी भी विशिष्ट "दुर्लभता" के स्तर के लिए, हमेशा कुछ संख्याएँ मौजूद होती हैं जो उस विवरण में फिट बैठती हैं। लेकिन जो संख्याएँ अत्यंत दुर्लभ हैं, वे बहुत कम हैं।

यह क्यों मायने रखता है? ("NTT" कनेक्शन)

क्रिप्टोग्राफर अक्सर अपने कंप्यूटर को तेज़ चलाने के लिए विशिष्ट संख्याओं को चुनते हैं। इन्हें NTT-फ्रेंडली संख्याएँ कहा जाता है।

डर: लोगों को डर था कि इन "तेज़" संख्याओं को चुनने से अनजाने में आपके गोल्डन टिकट गायब हो सकते हैं।
वास्तविकता: पेपर दिखाता है कि हालांकि "तेज़" होना (NTT-फ्रेंडली होना) यह गारंटी नहीं देता कि आपके पास बहुत सारे गोल्डन टिकट होंगे, लेकिन वर्तमान मानकों (जैसे 3329 और 8380417) में उपयोग किए जाने वाले विशिष्ट तेज़ नंबरों की संरचना बहुत अनुकूल है। उनमें बहुत कम "बुरे कारक" (bad factors) हैं जो टिकटों को दुर्लभ बना सकते हैं।
निर्णय: वर्तमान एन्क्रिप्शन मानक सुरक्षित हैं। "ओवरहेड" (एक कुंजी खोजने में खर्च किया गया अतिरिक्त समय) छोटा और अनुमानित है।

एक वाक्य में सारांश

पेपर यह सिद्ध करता है कि हालांकि यह गणितीय रूप से संभव है कि एन्क्रिप्शन सेटिंग्स ऐसी हों जहाँ वैध कुंजियाँ नगण्य रूप से दुर्लभ हों, लेकिन वास्तविक दुनिया में, वे सेटिंग्स इतनी दूर हैं कि व्यावहारिक उद्देश्यों के लिए, वैध कुंजियाँ हमेशा आसानी से मिल जाती हैं, और वर्तमान सुरक्षा मानक पूरी तरह से सुरक्षित हैं।

साधारण पाठक के लिए मुख्य बातें

"प्रिमिटिव-रूट" नियम: सुरक्षा सुनिश्चित करने के लिए गुप्त कुंजी के लिए यह एक विशेष आवश्यकता है।
"रिजेक्शन सैंपलिंग" की लागत: यह वह समय है जो आप एक वैध कुंजी खोजने में बर्बाद करते हैं। पेपर ठीक से गणना करता है कि इसमें कितना समय लगता है।
"सबसे खराब स्थिति" बनाम "वास्तविक दुनिया": गणितीय रूप से, सबसे खराब स्थिति बुरी है (इसमें लंबा समय लगता है), लेकिन व्यावहारिक रूप से, वह स्थिति इतनी दुर्लभ है कि हमें चिंता करने की आवश्यकता नहीं है।
"धीमी गिरावट" (The Slow Decay): पेपर एक प्रसिद्ध गणितीय सूत्र (Mertens' theorem) का उपयोग यह दिखाने के लिए करता है कि इन कुंजियों की "दुर्लभता" इतनी धीरे बढ़ती है (संख्या के आकार के डबल लॉगरिदम की तरह) कि यह नगण्य है।

संक्षेप में: लेखक ने आशंकाओं को दूर कर दिया है। "गोल्डन टिकट" सुरक्षित हैं, तिजोरी सुरक्षित है, और हमें कुंजी खोजने के लिए अनंत काल तक इंतजार नहीं करना पड़ेगा।

यहाँ विपिन सिंह सेहरावत के शोध पत्र "Primitive-Root Determinant Densities over Prime Fields and Implications for PRIM-LWE" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

यह शोध पत्र PRIM-LWE (प्रिमिटिव-रूट डिटरमिनेंट के साथ लर्निंग विद एरर्स) समस्या के संबंध में एक मौलिक प्रश्न को संबोधित करता है, जिसे सेहरावत, यो और डेसमेड्ट द्वारा पेश किया गया था।

संदर्भ: PRIM-LWE, मानक LWE समस्या का एक रूपांतर है जहाँ गुप्त मैट्रिक्स $S$ को इस प्रकार प्रतिबंधित किया जाता है कि उसका डिटरमिनेंट (determinant) प्राइम फील्ड $p$ के ऊपर एक प्रिमिटिव रूट (primitive root) हो (अर्थात, $\det(S)$ , मल्टीप्लिकेटिव ग्रुप $\mathbb{F}_p^*$ को जनरेट करता है)।
मुख्य प्रश्न: मानक डिसीजन-LWE से डिसीजन-PRIM-LWE में सुरक्षा रिडक्शन (security reduction), प्रिमिटिव-रूट डिटरमिनेंट वाली गुप्त मैट्रिसेस को सैंपल करने की क्षमता पर निर्भर करता है। इस रिडक्शन की दक्षता डायमेंशन-यूनिफॉर्म कांस्टेंट $c(p)$ द्वारा नियंत्रित होती है, जिसे $n \to \infty$ होने पर प्रिमिटिव-रूट डिटरमिनेंट वाली $n \times n$ मैट्रिसेस के घनत्व (density) के रूप में परिभाषित किया गया है:
$c(p) = \frac{\phi(p-1)}{p-1} \prod_{j=1}^{\infty} \left(1 - \frac{1}{p^j}\right)$
खुला प्रश्न (The Open Problem): सेहरावत आदि ने पहले यह अवलोकन किया था कि यदि अनंत संख्या में प्रिमोरियल प्राइम्स (primorial primes - वे अभाज्य संख्याएँ जो $N_k + 1$ के रूप में होती हैं, जहाँ $N_k$ प्रथम $k$ अभाज्य संख्याओं का गुणनफल है) मौजूद हैं, तो $\inf_p c(p) = 0$ होगा। उन्होंने पूछा था कि क्या यह इन्फिमम (infimum) अनकंडीशनल रूप से शून्य है (प्रिमोरियल प्राइम्स की अप्रामाणित अनंतता की धारणा के बिना)।
निहितार्थ: यदि $\inf_p c(p) = 0$ है, तो रिजेक्शन-सैंपलिंग ओवरहेड ( $1/c(p)$ ) कुछ विशिष्ट प्राइम्स के लिए सैद्धांतिक रूप से अत्यधिक बढ़ सकता है, जिससे विशिष्ट मॉड्यूल चयन के लिए PRIM-LWE के व्यावहारिक सुरक्षा गारंटियों को कमजोर किया जा सकता है।

2. कार्यप्रणाली (Methodology)

लेखक शास्त्रीय विश्लेषणात्मक संख्या सिद्धांत (classical analytic number theory) का उपयोग करके इस समस्या का समाधान करते हैं, जिससे अप्रामाणित अनुमानों (conjectures) से बचा जा सके। कार्यप्रणाली निम्नलिखित पर आधारित है:

Dirichlet's Theorem on Primes in Arithmetic Progressions: किसी भी $k$ के लिए $p \equiv 1 \pmod{N_k}$ वाले प्राइम्स के अस्तित्व को सुनिश्चित करने के लिए।
Mertens' Third Theorem: उत्पाद $\prod (1 - 1/p_i)$ के एसिम्प्टोटिक व्यवहार का अनुमान लगाने के लिए।
Linnik's Theorem: एक अंकगणितीय प्रगति (arithmetic progression) में न्यूनतम अभाज्य संख्या के आकार को सीमित करने के लिए, जिससे क्षय (decay) की मात्रात्मक दर स्थापित होती है।
Erdős–Wintner Theory: शिफ्ट किए गए प्राइम्स ( $p-1$ ) पर मूल्यांकित एडिटिव फंक्शन्स के वितरण का विश्लेषण करने के लिए।
Transport Lemmas: टोटिएंट रेश्यो (totient ratio) $\phi(p-1)/(p-1)$ से पूर्ण घनत्व $c(p)$ तक वितरण संबंधी परिणामों को स्थानांतरित करने के लिए।

3. मुख्य योगदान और परिणाम (Key Contributions and Results)

A. अनकंडीशनल वैनिशिंग ऑफ द इन्फिमम (Unconditional Vanishing of the Infimum)

यह शोध पत्र अनकंडीशनल रूप से सिद्ध करता है कि $\inf_{p \text{ prime}} c(p) = 0$ है।

तंत्र (Mechanism): किसी भी $k$ के लिए, डिरिचलेट का प्रमेय यह सुनिश्चित करता है कि अनंत संख्या में प्राइम्स $p \equiv 1 \pmod{N_k}$ मौजूद हैं। ऐसे प्राइम्स के लिए, अनुपात $\frac{\phi(p-1)}{p-1}$ उत्पाद $\prod_{i=1}^k (1 - 1/p_i)$ द्वारा ऊपरी रूप से सीमित है। मर्टेंस के प्रमेय के अनुसार, जैसे-जैसे $k \to \infty$ होता है, यह उत्पाद 0 की ओर जाता है।
महत्व: यह प्रिमोरियल प्राइम्स के अनंत होने की परिकल्पना की आवश्यकता के बिना इस खुले प्रश्न को हल करता है। यह पुष्टि करता है कि विशिष्ट अनुक्रमों के लिए रिडक्शन कांस्टेंट मनमाने ढंग से छोटा हो सकता है।

B. शार्प एसिम्प्टोटिक ऑर्डर (Sharp Asymptotic Order)

यह शोध पत्र न्यूनतम घनत्व के घटने की सटीक दर स्थापित करता है:
$\min_{p \le x} c(p) \asymp \frac{1}{\log \log x}$

ऊपरी सीमा (Upper Bound): $x$ के नीचे $p \equiv 1 \pmod{N_k}$ खोजने के लिए लिनिक के प्रमेय का उपयोग करके प्राप्त की गई।
निचली सीमा (Lower Bound): यह दिखाकर प्राप्त की गई कि किसी भी $p \le x$ के लिए, $\omega(p-1)$ (विशिष्ट अभाज्य गुणनखंडों की संख्या) सीमित है, जो घनत्व को $1/\log \log x$ से तेज़ घटने से रोकता है।
निहितार्थ: यह क्षय (decay) अत्यंत धीमा है। क्रिप्टोग्राफिक सुरक्षा मापदंडों (जैसे, $2^{128}$ या $2^{4096}$ ) के लिए, $\log \log x$ छोटा है (लगभग 4.5 से 7.95), जिसका अर्थ है कि घनत्व व्यावहारिक रूप से महत्वपूर्ण बना रहता है।

C. लिमिटिंग डिस्ट्रीब्यूशन (Limiting Distribution)

यह शोध पत्र सभी प्राइम्स के सेट पर $c(p)$ के सांख्यिकीय व्यवहार को स्पष्ट करता है:

वितरण (Distribution): $c(p)$ प्राइम्स पर एक निरंतर, विशुद्ध रूप से सिंगुलर लिमिटिंग डिस्ट्रीब्यूशन $G$ रखता है।
सपोर्ट (Support): इस वितरण का सपोर्ट अंतराल $[0, 1/2]$ है।
गुणधर्म: वितरण फलन $G$ , $[0, 1/2]$ पर सख्ती से बढ़ता हुआ (strictly increasing) है। इसका तात्पर्य यह है कि किसी भी थ्रेशोल्ड $\tau \in (0, 1/2)$ के लिए, प्राइम्स का सेट जहाँ $c(p) \le \tau$ है, का एक सकारात्मक सापेक्ष घनत्व $G(\tau)$ है।
संबंध: $c(p)$ का वितरण टोटिएंट रेश्यो $\phi(p-1)/(p-1)$ के समान है, क्योंकि अनंत उत्पाद पद $\prod (1 - p^{-j})$ तेजी से 1 की ओर अभिसरित (converge) होता है।

D. क्रिप्टोग्राफिक मॉड्युली के लिए स्पष्ट सीमाएँ (Explicit Bounds for Cryptographic Moduli)

यह शोध पत्र $q-1$ की गुणनखंड संरचना, विशेष रूप से $\omega(q-1)$ (विशिष्ट अभाज्य गुणनखंडों की संख्या) के आधार पर $c(q)$ के लिए ठोस निचली सीमाएँ प्रदान करता है।

सामान्य सीमा: $c(q) \ge P_3 \prod_{i=1}^{\omega(q-1)} (1 - 1/p_i)$ , जहाँ $P_3 \approx 0.56$ है।
NIST मानक:
- ML-KEM ( $q=3329$ ): $\omega(q-1)=2$ । यहाँ ओवरहेड $1/c(q) \le 2.17$ है।
- ML-DSA ( $q=8380417$ ): $\omega(q-1)=4$ । यहाँ ओवरहेड $1/c(q) \le 3.42$ है।
NTT-फ्रेंडली प्राइम्स: यह शोध पत्र स्पष्ट करता है कि केवल "NTT-फ्रेंडलीनेस" (आमतौर पर $q \equiv 1 \pmod{2^t}$ ) एक अच्छा बाउंड सुनिश्चित नहीं करती है, क्योंकि यह केवल $q-1$ के 2-adic भाग को नियंत्रित करती है। हालाँकि, अधिकांश व्यावहारिक NTT प्राइम्स में कम विषम (odd) अभाज्य गुणनखंड होते हैं, जिससे $\omega(q-1)$ कम रहता है और परिणामस्वरूप रिजेक्शन-सैंपलिंग ओवरहेड कम होता है।
सार्वभौमिक सीमा (Universal Bound): किसी भी $q > 2^{30}$ के लिए, $1/c(q) \le 1.79 \log q$ ।

4. महत्व और निहितार्थ (Significance and Implications)

सैद्धांतिक अनिश्चितता का समाधान: यह शोध पत्र निर्णायक रूप से उत्तर देता है कि $c(p)$ शून्य के करीब पहुँच सकता है, लेकिन यह बहुत धीरे-धीरे ( $\Theta(1/\log \log p)$ ) होता है। यह सभी प्राइम्स के लिए एक समान निचली सीमा की संभावना को खारिज करता है, लेकिन यह भी पुष्टि करता है कि "वर्स्ट-केस" प्राइम्स दुर्लभ हैं और धीरे घटते हैं।
PRIM-LWE की व्यावहारिक सुरक्षा: परिणाम मानक क्रिप्टोग्राफिक मॉड्युली के साथ PRIM-LWE के व्यावहारिक उपयोग को प्रमाणित करते हैं। NIST-मानकीकृत प्राइम्स के लिए रिजेक्शन-सैंपलिंग ओवरहेड छोटा है (कारक 2.17 और 3.42), जिसका अर्थ है कि सुरक्षा रिडक्शन मजबूत और कुशल बना रहता है।
मॉडुलस चयन के लिए मार्गदर्शन: यह शोध पत्र मॉडुलस चयन में ट्रेड-ऑफ को मात्रात्मक रूप से दर्शाता है। कम ओवरहेड सुनिश्चित करने के लिए, एक को ऐसे प्राइम्स $q$ चुनने चाहिए जहाँ $q-1$ की गुणनखंड संरचना (विशेष रूप से $\omega(q-1)$ की संख्या) नियंत्रित हो।
गणितीय अंतर्दृष्टि: यह PRIM-LWE घनत्व और शास्त्रीय संख्या-सिद्धांत वितरणों (Erdős–Wintner) के बीच एक गहरा संबंध स्थापित करता है, यह सिद्ध करता है कि घनत्व $[0, 1/2]$ पर पूर्ण सपोर्ट के साथ एक निरंतर सिंगुलर नियम का पालन करता है।

निष्कर्षतः, जबकि घनत्व का सैद्धांतिक इन्फिमम शून्य है, यह शोध पत्र प्रदर्शित करता है कि सभी व्यावहारिक क्रिप्टोग्राफिक उद्देश्यों के लिए, घनत्व एक छोटे स्थिरांक कारक द्वारा शून्य से दूर रहता है, जिससे यह सुनिश्चित होता है कि PRIM-LWE समस्या एक व्यवहार्य और सुरक्षित LWE वेरिएंट बनी रहती है।