2025-11-14T23:46:11.547081

On Deterministically Finding an Element of High Order Modulo a Composite

Oznovich, Volk
We give a deterministic algorithm that, given a composite number $N$ and a target order $D \ge N^{1/6}$, runs in time $D^{1/2+o(1)}$ and finds either an element $a \in \mathbb{Z}_N^*$ of multiplicative order at least $D$, or a nontrivial factor of $N$. Our algorithm improves upon an algorithm of Hittmeir (arXiv:1608.08766), who designed a similar algorithm under the stronger assumption $D \ge N^{2/5}$. Hittmeir's algorithm played a crucial role in the recent breakthrough deterministic integer factorization algorithms of Hittmeir and Harvey (arXiv:2006.16729, arXiv:2010.05450, arXiv:2105.11105). When $N$ is assumed to have an $r$-power divisor with $r\ge 2$, our algorithm provides the same guarantees assuming $D \ge N^{1/6r}$.
academic

समग्र संख्या के मॉड्यूलो उच्च क्रम के एक तत्व को नियतात्मक रूप से खोजने पर

मूल जानकारी

  • पेपर ID: 2506.07668
  • शीर्षक: On Deterministically Finding an Element of High Order Modulo a Composite
  • लेखक: Ziv Oznovich, Ben Lee Volk (Efi Arazi School of Computer Science, Reichman University, Israel)
  • वर्गीकरण: cs.DS (डेटा संरचनाएं और एल्गोरिदम), math.NT (संख्या सिद्धांत)
  • प्रस्तुति समय: 11 जून 2025 (arXiv v3)
  • पेपर लिंक: https://arxiv.org/abs/2506.07668

सारांश

यह पेपर एक नियतात्मक एल्गोरिदम प्रस्तुत करता है जो समग्र संख्या NN और लक्ष्य क्रम D≥N1/6D \geq N^{1/6} दिए जाने पर, D1/2+o(1)D^{1/2+o(1)} समय में चलता है और या तो एक तत्व a∈ZN∗a \in \mathbb{Z}_N^* खोजता है जिसका गुणक क्रम कम से कम DD है, या NN का एक गैर-तुच्छ गुणनखंड खोजता है। यह एल्गोरिदम Hittmeir के एल्गोरिदम में सुधार करता है, जिसे अधिक मजबूत धारणा D≥N2/5D \geq N^{2/5} की आवश्यकता थी। जब NN में rr वीं घात गुणनखंड (r≥2r \geq 2) होते हैं, तो एल्गोरिदम D≥N1/6rD \geq N^{1/6r} की धारणा के तहत समान गारंटी प्रदान करता है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या की पृष्ठभूमि

  1. पूर्णांक गुणनखंडन की चुनौती: पूर्णांक गुणनखंडन कम्प्यूटेशनल संख्या सिद्धांत की मूल समस्या है। वर्तमान में सर्वश्रेष्ठ यादृच्छिक एल्गोरिदम (जैसे संख्या क्षेत्र छलनी) में उप-घातीय जटिलता है, जबकि सर्वश्रेष्ठ नियतात्मक एल्गोरिदम हाल तक दृढ़ घातीय थे।
  2. नियतात्मक एल्गोरिदम का महत्व: हालांकि सैद्धांतिक रूप से माना जाता है कि प्रत्येक यादृच्छिक एल्गोरिदम को बहुपद धीमा करके नियतात्मक एल्गोरिदम द्वारा अनुकरण किया जा सकता है, लेकिन बिना शर्त विरैंडमीकरण परिणाम प्राप्त करना जटिलता सिद्धांत और एल्गोरिदम डिजाइन में अभी भी महत्वपूर्ण है।
  3. उच्च क्रम तत्वों की भूमिका: Hittmeir और Harvey के अग्रणी कार्य से पता चलता है कि बड़े गुणक क्रम वाले तत्वों को नियतात्मक रूप से खोजना कुशल नियतात्मक गुणनखंडन एल्गोरिदम डिजाइन करने की कुंजी है।

अनुसंधान प्रेरणा

  1. पैरामीटर रेंज में सुधार: Hittmeir के एल्गोरिदम को D≥N2/5D \geq N^{2/5} की आवश्यकता है, यह शर्त अपेक्षाकृत कठोर है और एल्गोरिदम की प्रयोज्यता को सीमित करती है।
  2. गुणनखंडन एल्गोरिदम को बेहतर बनाना: Harvey-Hittmeir गुणनखंडन एल्गोरिदम में, उच्च क्रम तत्व खोजने का चरण N1/5+o(1)N^{1/5+o(1)} समय में चलता है, जो एल्गोरिदम की बाधाओं में से एक है।
  3. सैद्धांतिक महत्व: विरैंडमीकरण सैद्धांतिक कंप्यूटर विज्ञान की एक महत्वपूर्ण समस्या है, और संख्या सिद्धांत एल्गोरिदम में विरैंडमीकरण का गहरा सैद्धांतिक महत्व है।

मूल योगदान

  1. पैरामीटर सुधार: लक्ष्य क्रम की आवश्यकता को D≥N2/5D \geq N^{2/5} से घटाकर D≥N1/6D \geq N^{1/6} कर दिया, जो एल्गोरिदम की प्रयोज्यता को काफी हद तक बढ़ाता है।
  2. चलने का समय संरक्षण: पैरामीटर आवश्यकताओं को शिथिल करते हुए, D1/2+o(1)D^{1/2+o(1)} की चलने का समय जटिलता को बनाए रखा।
  3. rr वीं घात मामले का अनुकूलन: जब NN में rr वीं घात गुणनखंड होते हैं, तो आवश्यकता को और भी घटाकर D≥N1/6rD \geq N^{1/6r} कर दिया।
  4. गुणनखंडन एल्गोरिदम सुधार: नए गुणनखंडन उप-प्रोग्राम प्रदान किए, ज्ञात अवशेष वर्ग जानकारी के तहत गुणनखंडन विधि में सुधार किया।
  5. सैद्धांतिक उपकरण: क्रमागत पूर्णांकों में विशिष्ट सर्वांगसमता शर्तों को संतुष्ट करने वाले तत्वों की संख्या के लिए अधिक कड़ी सीमाएं साबित कीं।

विधि विस्तार

कार्य परिभाषा

इनपुट: समग्र संख्या NN और लक्ष्य क्रम D≥N1/6D \geq N^{1/6}आउटपुट: या तो ZN∗\mathbb{Z}_N^* में एक तत्व aa जिसका गुणक क्रम कम से कम DD है, या NN का एक गैर-तुच्छ गुणनखंड समय जटिलता: D1/2+o(1)D^{1/2+o(1)}

एल्गोरिदम आर्किटेक्चर

मुख्य एल्गोरिदम संरचना (Algorithm 4.1)

एल्गोरिदम एक पुनरावृत्तिमूलक खोज रणनीति अपनाता है, जिसमें मुख्य रूप से निम्नलिखित चरण शामिल हैं:

  1. पूर्व-प्रसंस्करण: छोटे गुणनखंडों की जांच के लिए Strassen विधि का उपयोग
  2. पुनरावृत्तिमूलक खोज: a=2,3,4,…a = 2, 3, 4, \ldots के लिए खोज
  3. क्रम गणना: सुधारी गई Baby-step Giant-step विधि का उपयोग
  4. सूचना संचय: चर MM को बनाए रखना जो जांचे गए तत्वों के क्रम का न्यूनतम सामान्य गुणज दर्ज करता है
  5. अंतिम गुणनखंडन: जब MM पर्याप्त बड़ा हो तो नए गुणनखंडन एल्गोरिदम का उपयोग

मूल तकनीकी सुधार

1. क्रमागत मूलों की सीमा में सुधार (Claim 2.6)

बड़े पूर्णांक N, ℓ के लिए, यदि N का एक अभाज्य गुणनखंड p > 2ℓ है,
तो m = 10√ℓ क्रमागत पूर्णांकों {a, a+1, ..., a+m} में,
आवश्यक रूप से एक तत्व b मौजूद है जैसे कि b^ℓ ≢ 1 (mod N)

यह Hittmeir एल्गोरिदम में O(M)O(M) की खोज जटिलता को O(M)O(\sqrt{M}) तक सुधारता है।

2. अवशेष वर्ग गुणनखंडन एल्गोरिदम (Theorem 3.2)NN और s≥Nαs \geq N^α दिए गए (α≤1/(4r)α \leq 1/(4r), gcd⁡(N,s)=1\gcd(N,s) = 1), एल्गोरिदम N1/(4r)−α+o(1)N^{1/(4r)-α+o(1)} समय में सभी rr वीं घात गुणनखंड खोज सकता है जो p≡1(mods)p \equiv 1 \pmod{s} को संतुष्ट करते हैं।

तकनीकी नवाचार बिंदु

1. बहुपद निर्माण में सुधार

Harvey-Hittmeir एल्गोरिदम के आधार पर, आधार बहुपद को f(x)=x+Pf(x) = x + P से सुधारकर: g(x)=x+s′+s′(P−P~)g(x) = x + s' + s'(P - \tilde{P}) जहां s′s' ss का NN मॉड्यूलो व्युत्क्रम है, P~\tilde{P} PP का ss मॉड्यूलो अवशेष है।

2. खोज स्थान में कमी

अभाज्य गुणनखंड p≡1(mods)p \equiv 1 \pmod{s} की जानकारी का उपयोग करके, मूलों की खोज का आकार HH से लगभग H/sH/s तक कम किया, जिससे खोज अंतराल की संख्या ss गुना कम हो गई।

3. LLL जाली आधार न्यूनीकरण का अनुप्रयोग

बहुपद प्रणाली का निर्माण:

N^{m-\lfloor i/r \rfloor} g(x)^i, & 0 \leq i < rm \\ g(x)^i, & rm \leq i < d \end{cases}$$ LLL एल्गोरिदम के माध्यम से छोटे वेक्टर खोजें, जो छोटे गुणांकों वाले और लक्ष्य मूल पर शून्य वाले बहुपद के अनुरूप हैं। ## प्रायोगिक सेटअप ### सैद्धांतिक विश्लेषण ढांचा यह पेपर मुख्य रूप से सैद्धांतिक विश्लेषण करता है, गणितीय प्रमाण के माध्यम से एल्गोरिदम की सही्ता और जटिलता को सत्यापित करता है: 1. **सही्ता प्रमाण**: साबित करता है कि एल्गोरिदम प्रत्येक समाप्ति बिंदु पर सही परिणाम आउटपुट करता है 2. **जटिलता विश्लेषण**: प्रत्येक चरण की समय जटिलता का विस्तृत विश्लेषण 3. **पैरामीटर अनुकूलन**: सैद्धांतिक विश्लेषण के माध्यम से इष्टतम पैरामीटर सेटिंग निर्धारित करता है ### मुख्य लेम्मा सत्यापन - **Lemma 2.5** (Forbes आदि): बहुपद प्रणाली मूलों की संख्या सीमा - **Claim 2.6**: क्रमागत पूर्णांकों में सर्वांगसमता शर्त को संतुष्ट न करने वाले तत्वों की मौजूदगी - **Claim 3.3**: अवशेष वर्ग बाधा के तहत मूल आकार की सीमा ## प्रायोगिक परिणाम ### सैद्धांतिक परिणाम 1. **मुख्य प्रमेय (Theorem 1.1)**: - पैरामीटर आवश्यकता: $D \geq N^{1/6}$ (बनाम Hittmeir का $N^{2/5}$) - चलने का समय: $D^{1/2+o(1)}$ (अपरिवर्तित) 2. **$r$ वीं घात मामला (Theorem 4.2)**: - पैरामीटर आवश्यकता: $D \geq N^{1/6r}$ - चलने का समय: $D^{1/2+o(1)}$ 3. **गुणनखंडन एल्गोरिदम (Theorem 3.2)**: - शर्त: $s \geq N^α$, $α \leq 1/(4r)$ - चलने का समय: $N^{1/(4r)-α+o(1)}$ ### जटिलता सुधार - **खोज चरण**: $O(M)$ से $O(\sqrt{M})$ तक सुधारा गया - **पैरामीटर रेंज**: घातांक $2/5$ से $1/6$ तक कम किया गया - **गुणनखंडन दक्षता**: ज्ञात अवशेष जानकारी के समय में काफी वृद्धि ### संबंधित कार्य के साथ तुलना | एल्गोरिदम | पैरामीटर आवश्यकता | चलने का समय | वर्ष | |----------|------------------|-----------|------| | Hittmeir | $D \geq N^{2/5}$ | $D^{1/2+o(1)}$ | 2018 | | GFHP | $D \geq N^{1/4r}$ | $D^{1/2+o(1)}$ | 2025 | | यह पेपर | $D \geq N^{1/6}$ | $D^{1/2+o(1)}$ | 2025 | ## संबंधित कार्य ### नियतात्मक गुणनखंडन एल्गोरिदम विकास 1. **शास्त्रीय विधि**: Pollard-Strassen एल्गोरिदम ($N^{1/4+o(1)}$) 2. **हाल के सफलताएं**: Hittmeir-Harvey एल्गोरिदम ($N^{1/5+o(1)}$) 3. **यादृच्छिक एल्गोरिदम**: संख्या क्षेत्र छलनी आदि उप-घातीय एल्गोरिदम ### उच्च क्रम तत्व खोज 1. **यादृच्छिक विधि**: यादृच्छिक तत्वों में आमतौर पर बड़ा क्रम होता है 2. **नियतात्मक चुनौती**: ऐसे तत्वों को नियतात्मक रूप से कैसे खोजें 3. **अनुप्रयोग**: गुणनखंडन एल्गोरिदम में महत्वपूर्ण भूमिका ### जाली आधार न्यूनीकरण अनुप्रयोग 1. **Coppersmith विधि**: बहुपद छोटे मूलों की खोज 2. **Harvey-Hittmeir**: $r$ वीं घात गुणनखंड गुणनखंडन 3. **यह पेपर विस्तार**: अवशेष वर्ग जानकारी के साथ संयुक्त सुधार ## निष्कर्ष और चर्चा ### मुख्य निष्कर्ष 1. उच्च क्रम तत्व खोज की पैरामीटर आवश्यकता को $N^{2/5}$ से $N^{1/6}$ तक सफलतापूर्वक कम किया 2. $D^{1/2+o(1)}$ का इष्टतम चलने का समय बनाए रखा 3. नियतात्मक गुणनखंडन एल्गोरिदम के लिए बेहतर उप-प्रोग्राम प्रदान किया ### सीमाएं 1. **अभाज्य मामला**: एल्गोरिदम अभाज्य इनपुट के लिए उपयोगी आउटपुट नहीं दे सकता 2. **पैरामीटर प्रतिबंध**: अभी भी $D \geq N^{1/6}$ की निचली सीमा की आवश्यकता है 3. **व्यावहारिक दक्षता**: सैद्धांतिक सुधार का व्यावहारिक अनुप्रयोग में प्रभाव सत्यापन की आवश्यकता है ### भविष्य की दिशाएं 1. **1/5 बाधा को तोड़ना**: गुणनखंडन एल्गोरिदम में इस एल्गोरिदम का अनुप्रयोग आगे के सुधार ला सकता है 2. **अभाज्य क्षेत्र जनरेटर**: $\mathbb{Z}_p^*$ के जनरेटर को नियतात्मक रूप से खोजना 3. **असतत लघुगणक**: नियतात्मक असतत लघुगणक एल्गोरिदम में सुधार ## गहन मूल्यांकन ### शक्तियां 1. **सैद्धांतिक नवाचार**: कई गणितीय उपकरणों को चतुराई से संयोजित करके पैरामीटर में महत्वपूर्ण सुधार प्राप्त किया 2. **तकनीकी गहराई**: Harvey-Hittmeir एल्गोरिदम के विस्तार से गहन तकनीकी दक्षता का प्रदर्शन 3. **व्यावहारिक मूल्य**: नियतात्मक गुणनखंडन एल्गोरिदम के लिए बेहतर निर्माण खंड प्रदान किया 4. **प्रमाण कठोरता**: गणितीय तर्क कड़ा है, जटिलता विश्लेषण विस्तृत है ### कमियां 1. **प्रायोगिक सत्यापन**: वास्तविक कार्यान्वयन और प्रदर्शन परीक्षण का अभाव 2. **स्थिर कारक**: $o(1)$ पद व्यावहारिक रूप से नगण्य नहीं हो सकते 3. **प्रयोज्यता रेंज**: कुछ विशेष मामलों (जैसे अभाज्य) के लिए सीमित प्रबंधन ### प्रभाव 1. **सैद्धांतिक योगदान**: नियतात्मक संख्या सिद्धांत एल्गोरिदम के विकास को आगे बढ़ाता है 2. **विधि मूल्य**: प्रदान की गई तकनीकें अन्य संबंधित समस्याओं पर लागू हो सकती हैं 3. **अनुवर्ती अनुसंधान**: गुणनखंडन एल्गोरिदम में आगे के सुधार के लिए आधार तैयार करता है ### प्रयोज्य परिदृश्य 1. **सैद्धांतिक अनुसंधान**: जटिलता सिद्धांत और एल्गोरिदम डिजाइन 2. **क्रिप्टोग्राफी**: नियतात्मक गारंटी की आवश्यकता वाले सुरक्षा अनुप्रयोग 3. **संख्या सिद्धांत गणना**: बड़े पूर्णांक संबंधित गणितीय गणना ## संदर्भ - [Hit18] Markus Hittmeir. A babystep-giantstep method for faster deterministic integer factorization - [Har21] David Harvey. An exponent one-fifth algorithm for deterministic integer factorisation - [HH22b] David Harvey and Markus Hittmeir. A log-log speedup for exponent one-fifth deterministic integer factorisation - [GFHP25] Yiming Gao, Yansong Feng, Honggang Hu, and Yanbin Pan. On factoring and power divisor problems via rank-3 lattices --- यह पेपर नियतात्मक संख्या सिद्धांत एल्गोरिदम के क्षेत्र में महत्वपूर्ण योगदान देता है, चतुर तकनीकी नवाचार के माध्यम से पैरामीटर में महत्वपूर्ण सुधार प्राप्त करता है, और भविष्य के अनुसंधान के लिए मूल्यवान उपकरण और विचार प्रदान करता है।