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

সমগ্র সংখ্যার মডুলো একটি উচ্চ ক্রমের উপাদান নির্ধারণমূলকভাবে খুঁজে পাওয়ার বিষয়ে

মৌলিক তথ্য

পেপার আইডি: 2506.07668
শিরোনাম: সমগ্র সংখ্যার মডুলো একটি উচ্চ ক্রমের উপাদান নির্ধারণমূলকভাবে খুঁজে পাওয়ার বিষয়ে
লেখক: জিভ ওজনোভিচ, বেন লি ভোল্ক (ইফি আরাজি কম্পিউটার বিজ্ঞান স্কুল, রাইখম্যান বিশ্ববিদ্যালয়, ইসরায়েল)
শ্রেণীবিভাগ: cs.DS (ডেটা স্ট্রাকচার এবং অ্যালগরিদম), math.NT (সংখ্যা তত্ত্ব)
জমা দেওয়ার সময়: ২০২৫ সালের ১১ জুন (arXiv v3)
পেপার লিঙ্ক: https://arxiv.org/abs/2506.07668

সারসংক্ষেপ

এই পেপারটি একটি নির্ধারণমূলক অ্যালগরিদম উপস্থাপন করে যা সমগ্র সংখ্যা $N$ এবং লক্ষ্য ক্রম $D \geq N^{1/6}$ দেওয়া হলে, অ্যালগরিদম $D^{1/2+o(1)}$ সময়ে চলে এবং হয় একটি উপাদান $a \in \mathbb{Z}_N^*$ খুঁজে পায় যার গুণক ক্রম কমপক্ষে $D$ , অথবা $N$ এর একটি অ-তুচ্ছ উৎপাদক খুঁজে পায়। এই অ্যালগরিদম হিটমেয়ারের অ্যালগরিদম উন্নত করে, যা আরও শক্তিশালী অনুমান $D \geq N^{2/5}$ প্রয়োজন করে। যখন $N$ এর $r$ ঘাত উৎপাদক ( $r \geq 2$ ) থাকে, অ্যালগরিদম অনুমান $D \geq N^{1/6r}$ এর অধীনে একই গ্যারান্টি প্রদান করে।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যার পটভূমি

১. পূর্ণসংখ্যা উৎপাদনের চ্যালেঞ্জ: পূর্ণসংখ্যা উৎপাদন গণনামূলক সংখ্যা তত্ত্বের মূল সমস্যা। বর্তমানে সেরা র্যান্ডম অ্যালগরিদম (যেমন সংখ্যা ক্ষেত্র চালনী) উপ-সূচক জটিলতা রয়েছে, যখন সেরা নির্ধারণমূলক অ্যালগরিদম সম্প্রতি পর্যন্ত দৃঢ় সূচক ছিল।

२. নির্ধারণমূলক অ্যালগরিদমের গুরুত্ব: যদিও তাত্ত্বিকভাবে প্রতিটি র্যান্ডম অ্যালগরিদম বহুপদ ধীরতার সাথে নির্ধারণমূলক অ্যালগরিদম দ্বারা অনুকরণ করা যায়, শর্তহীন ডিরান্ডমাইজেশন ফলাফল পাওয়া জটিলতা তত্ত্ব এবং অ্যালগরিদম ডিজাইনে এখনও গুরুত্বপূর্ণ।

३. উচ্চ ক্রমের উপাদানের ভূমিকা: হিটমেয়ার এবং হার্ভের যুগান্তকারী কাজ দেখায় যে নির্ধারণমূলকভাবে বড় গুণক ক্রমের উপাদান খুঁজে পাওয়া দক্ষ নির্ধারণমূলক উৎপাদন অ্যালগরিদম ডিজাইনের চাবিকাঠি।

গবেষণা প্রেরণা

१. পরামিতি পরিসীমা উন্নতি: হিটমেয়ারের অ্যালগরিদম $D \geq N^{2/5}$ প্রয়োজন করে, এই শর্ত অপেক্ষাকৃত কঠোর এবং অ্যালগরিদমের প্রয়োগের পরিসীমা সীমিত করে।

२. উৎপাদন অ্যালগরিদম উন্নতি: হার্ভে-হিটমেয়ার উৎপাদন অ্যালগরিদমে, উচ্চ ক্রমের উপাদান খুঁজে পাওয়ার ধাপ $N^{1/5+o(1)}$ সময়ে চলে, অ্যালগরিদমের একটি বোতলনেক হয়ে ওঠে।

३. তাত্ত্বিক তাৎপর্য: ডিরান্ডমাইজেশন তাত্ত্বিক কম্পিউটার বিজ্ঞানের একটি গুরুত্বপূর্ণ সমস্যা, এবং সংখ্যা তত্ত্ব অ্যালগরিদমে ডিরান্ডমাইজেশন অর্জন গভীর তাত্ত্বিক তাৎপর্য রাখে।

মূল অবদান

१. পরামিতি উন্নতি: লক্ষ্য ক্রমের প্রয়োজনীয়তা $D \geq N^{2/5}$ থেকে $D \geq N^{1/6}$ এ হ্রাস করা, অ্যালগরিদমের প্রযোজ্যতার পরিসীমা উল্লেখযোগ্যভাবে প্রসারিত করা।

२. চলার সময় বজায় রাখা: পরামিতি প্রয়োজনীয়তা শিথিল করার সময়, $D^{1/2+o(1)}$ এর চলার সময় জটিলতা বজায় রাখা।

३. $r$ ঘাত ক্ষেত্রের অপ্টিমাইজেশন: যখন $N$ এর $r$ ঘাত উৎপাদক থাকে, প্রয়োজনীয়তা আরও $D \geq N^{1/6r}$ এ হ্রাস করা।

४. উৎপাদন অ্যালগরিদম উন্নতি: নতুন উৎপাদন উপ-প্রোগ্রাম প্রদান করা, পরিচিত অবশিষ্ট শ্রেণী তথ্যের অধীনে উৎপাদনকরণ পদ্ধতি উন্নত করা।

५. তাত্ত্বিক সরঞ্জাম: ক্রমাগত পূর্ণসংখ্যায় নির্দিষ্ট সর্বসম্মতি শর্ত পূরণকারী উপাদানের সংখ্যার আরও কঠোর সীমানা প্রমাণ করা।

পদ্ধতি বিস্তারিত

কাজের সংজ্ঞা

ইনপুট: সমগ্র সংখ্যা $N$ এবং লক্ষ্য ক্রম $D \geq N^{1/6}$ আউটপুট: হয় $\mathbb{Z}_N^*$ এ গুণক ক্রম কমপক্ষে $D$ সহ উপাদান $a$ , অথবা $N$ এর একটি অ-তুচ্ছ উৎপাদক সময় জটিলতা: $D^{1/2+o(1)}$

অ্যালগরিদম স্থাপত্য

প্রধান অ্যালগরিদম কাঠামো (অ্যালগরিদম ४.१)

অ্যালগরিদম পুনরাবৃত্তিমূলক অনুসন্ধান কৌশল ব্যবহার করে, প্রধান পদক্ষেপগুলি অন্তর্ভুক্ত করে:

१. প্রাক-প্রক্রিয়াকরণ: ছোট উৎপাদক পরীক্ষা করতে স্ট্রাসেন পদ্ধতি ব্যবহার করা २. পুনরাবৃত্তিমূলক অনুসন্ধান: $a = 2, 3, 4, \ldots$ এর জন্য অনুসন্ধান করা ३. ক্রম গণনা: উন্নত বেবি-স্টেপ জায়ান্ট-স্টেপ পদ্ধতি ব্যবহার করা ४. তথ্য সংগ্রহ: পরিবর্তনশীল $M$ বজায় রাখা যা পরীক্ষিত উপাদান ক্রমের ন্যূনতম সাধারণ গুণিতক রেকর্ড করে ५. চূড়ান্ত উৎপাদন: যখন $M$ যথেষ্ট বড় হয় নতুন উৎপাদন অ্যালগরিদম ব্যবহার করা

মূল প্রযুক্তিগত উন্নতি

१. ক্রমাগত মূলের সীমানা উন্নতি (দাবি २.६)

বড় পূর্ণসংখ্যা N, ℓ এর জন্য, যদি N এর প্রধান উৎপাদক p > 2ℓ থাকে,
তাহলে m = 10√ℓ ক্রমাগত পূর্ণসংখ্যা {a, a+1, ..., a+m} এ,
অবশ্যই উপাদান b বিদ্যমান থাকে যেমন b^ℓ ≢ 1 (mod N)

এটি হিটমেয়ার অ্যালগরিদমে $O(M)$ অনুসন্ধান জটিলতা $O(\sqrt{M})$ এ উন্নত করে।

२. অবশিষ্ট শ্রেণী উৎপাদন অ্যালগরিদম (উপপাদ্য ३.२) $N$ এবং $s \geq N^α$ দেওয়া ( $α \leq 1/(4r)$ , $\gcd(N,s) = 1$ ), অ্যালগরিদম $N^{1/(4r)-α+o(1)}$ সময়ে $p \equiv 1 \pmod{s}$ পূরণকারী সমস্ত $r$ ঘাত উৎপাদক খুঁজে পেতে পারে।

প্রযুক্তিগত উদ্ভাবন পয়েন্ট

१. বহুপদী নির্মাণের উন্নতি

হার্ভে-হিটমেয়ার অ্যালগরিদমের ভিত্তিতে, মৌলিক বহুপদী $f(x) = x + P$ থেকে উন্নত করা: $g(x) = x + s' + s'(P - \tilde{P})$ যেখানে $s'$ হল $s$ মডুলো $N$ এর বিপরীত, $\tilde{P}$ হল $P$ মডুলো $s$ এর অবশিষ্ট।

२. অনুসন্ধান স্থানের হ্রাস

প্রধান উৎপাদক $p \equiv 1 \pmod{s}$ এর তথ্য ব্যবহার করে, মূল অনুসন্ধানের আকার $H$ থেকে প্রায় $H/s$ এ হ্রাস করা, এভাবে অনুসন্ধান ব্যবধান সংখ্যা $s$ গুণ কমানো।

३. LLL জালি ভিত্তি হ্রাসের প্রয়োগ

বহুপদী সিস্টেম নির্মাণ: $f_i(x) = \begin{cases} N^{m-\lfloor i/r \rfloor} g(x)^i, & 0 \leq i < rm \\ g(x)^i, & rm \leq i < d \end{cases}$

LLL অ্যালগরিদমের মাধ্যমে সংক্ষিপ্ত ভেক্টর খুঁজে পাওয়া, লক্ষ্য মূলে ছোট সহগ এবং শূন্য সহ বহুপদীর সাথে সংশ্লিষ্ট।

পরীক্ষামূলক সেটআপ

তাত্ত্বিক বিশ্লেষণ কাঠামো

এই পেপারটি প্রধানত তাত্ত্বিক বিশ্লেষণ পরিচালনা করে, গাণিতিক প্রমাণের মাধ্যমে অ্যালগরিদমের সঠিকতা এবং জটিলতা যাচাই করে:

१. সঠিকতা প্রমাণ: অ্যালগরিদম প্রতিটি সমাপ্তি পয়েন্টে সঠিক ফলাফল আউটপুট করে তা প্রমাণ করা २. জটিলতা বিশ্লেষণ: প্রতিটি পদক্ষেপের সময় জটিলতা বিস্তারিত বিশ্লেষণ করা ३. পরামিতি অপ্টিমাইজেশন: তাত্ত্বিক বিশ্লেষণের মাধ্যমে সর্বোত্তম পরামিতি সেটিং নির্ধারণ করা

মূল লেম্মা যাচাইকরণ

লেম্মা २.५ (ফোর্বস ইত্যাদি): বহুপদী সিস্টেম মূলের সংখ্যা সীমানা
দাবি २.६: ক্রমাগত পূর্ণসংখ্যায় সর্বসম্মতি শর্ত পূরণ না করা উপাদানের অস্তিত্ব
দাবি ३.३: অবশিষ্ট শ্রেণী সীমাবদ্ধতার অধীনে মূল আকারের সীমানা

পরীক্ষামূলক ফলাফল

তাত্ত্বিক ফলাফল

१. প্রধান উপপাদ্য (উপপাদ্য १.१):

পরামিতি প্রয়োজনীয়তা: $D \geq N^{1/6}$ (বনাম হিটমেয়ারের $N^{2/5}$ )
চলার সময়: $D^{1/2+o(1)}$ (অপরিবর্তিত)

२. $r$ ঘাত ক্ষেত্র (উপপাদ্য ४.२):

পরামিতি প্রয়োজনীয়তা: $D \geq N^{1/6r}$
চলার সময়: $D^{1/2+o(1)}$

३. উৎপাদন অ্যালগরিদম (উপপাদ্য ३.२):

শর্ত: $s \geq N^α$ , $α \leq 1/(4r)$
চলার সময়: $N^{1/(4r)-α+o(1)}$

জটিলতা উন্নতি

অনুসন্ধান পদক্ষেপ: $O(M)$ থেকে $O(\sqrt{M})$ এ উন্নত
পরামিতি পরিসীমা: সূচক $2/5$ থেকে $1/6$ এ হ্রাস
উৎপাদন দক্ষতা: পরিচিত অবশিষ্ট তথ্যের সময় উল্লেখযোগ্যভাবে উন্নত

অ্যালগরিদম	পরামিতি প্রয়োজনীয়তা	চলার সময়	বছর
হিটমেয়ার	$D \geq N^{2/5}$	$D^{1/2+o(1)}$	२०१८
GFHP	$D \geq N^{1/4r}$	$D^{1/2+o(1)}$	२०२५
এই পেপার	$D \geq N^{1/6}$	$D^{1/2+o(1)}$	२०२५

উপসংহার এবং আলোচনা

প্রধান সিদ্ধান্ত

१. সফলভাবে উচ্চ ক্রমের উপাদান অনুসন্ধানের পরামিতি প্রয়োজনীয়তা $N^{2/5}$ থেকে $N^{1/6}$ এ হ্রাস করা २. $D^{1/2+o(1)}$ এর সর্বোত্তম চলার সময় বজায় রাখা ३. নির্ধারণমূলক উৎপাদন অ্যালগরিদমের জন্য আরও ভাল উপ-প্রোগ্রাম প্রদান করা

সীমাবদ্ধতা

१. প্রধান সংখ্যার ক্ষেত্র: অ্যালগরিদম প্রধান সংখ্যা ইনপুটের জন্য উপকারী আউটপুট উৎপাদন করতে পারে না २. পরামিতি সীমাবদ্ধতা: এখনও $D \geq N^{1/6}$ এর নিম্ন সীমানা প্রয়োজন ३. ব্যবহারিক দক্ষতা: তাত্ত্বিক উন্নতি ব্যবহারিক প্রয়োগে কার্যকারিতা যাচাইকরণ প্রয়োজন

ভবিষ্যত দিকনির্দেশনা

१. १/५ বাধা অতিক্রম করা: উৎপাদন অ্যালগরিদমে এই অ্যালগরিদম প্রয়োগ আরও উন্নতি আনতে পারে २. প্রধান ক্ষেত্র জেনারেটর: $\mathbb{Z}_p^*$ এর জেনারেটর নির্ধারণমূলকভাবে খুঁজে পাওয়া ३. বিচ্ছিন্ন লগারিদম: নির্ধারণমূলক বিচ্ছিন্ন লগারিদম অ্যালগরিদম উন্নত করা

গভীর মূল্যায়ন

সুবিধা

१. তাত্ত্বিক উদ্ভাবন: একাধিক গাণিতিক সরঞ্জাম চতুরভাবে সংমিশ্রিত করে পরামিতির উল্লেখযোগ্য উন্নতি অর্জন করা २. প্রযুক্তিগত গভীরতা: হার্ভে-হিটমেয়ার অ্যালগরিদমের সম্প্রসারণ গভীর প্রযুক্তিগত দক্ষতা প্রদর্শন করে ३. ব্যবহারিক মূল্য: নির্ধারণমূলক উৎপাদন অ্যালগরিদমের জন্য আরও ভাল নির্মাণ ব্লক প্রদান করা ४. প্রমাণ কঠোরতা: গাণিতিক যুক্তি কঠোর, জটিলতা বিশ্লেষণ বিস্তারিত

অপূর্ণতা

१. পরীক্ষামূলক যাচাইকরণ: ব্যবহারিক বাস্তবায়ন এবং কর্মক্ষমতা পরীক্ষার অভাব २. ধ্রুবক উপাদান: $o(1)$ পদ ব্যবহারিকভাবে উপেক্ষণীয় নাও হতে পারে ३. প্রযোজ্যতা পরিসীমা: নির্দিষ্ট ক্ষেত্রে (যেমন প্রধান সংখ্যা) পরিচালনা সীমিত

প্রভাব

१. তাত্ত্বিক অবদান: নির্ধারণমূলক সংখ্যা তত্ত্ব অ্যালগরিদমের উন্নয়ন এগিয়ে নিয়ে যাওয়া २. পদ্ধতি মূল্য: প্রদত্ত প্রযুক্তি অন্যান্য সম্পর্কিত সমস্যায় প্রযোজ্য হতে পারে ३. পরবর্তী গবেষণা: উৎপাদন অ্যালগরিদম আরও উন্নতির ভিত্তি স্থাপন করা

প্রযোজ্য পরিস্থিতি

१. তাত্ত্বিক গবেষণা: জটিলতা তত্ত্ব এবং অ্যালগরিদম ডিজাইন २. ক্রিপ্টোগ্রাফি: নির্ধারণমূলক গ্যারান্টি প্রয়োজনীয় নিরাপদ প্রয়োগ ३. সংখ্যা তত্ত্ব গণনা: বড় পূর্ণসংখ্যা সম্পর্কিত গাণিতিক গণনা

সংদর্ভ

Hit18 মার্কাস হিটমেয়ার। দ্রুত নির্ধারণমূলক পূর্ণসংখ্যা উৎপাদনের জন্য একটি বেবিস্টেপ-জায়ান্টস্টেপ পদ্ধতি
Har21 ডেভিড হার্ভে। নির্ধারণমূলক পূর্ণসংখ্যা উৎপাদনের জন্য একটি সূচক এক-পঞ্চম অ্যালগরিদম
HH22b ডেভিড হার্ভে এবং মার্কাস হিটমেয়ার। সূচক এক-পঞ্চম নির্ধারণমূলক পূর্ণসংখ্যা উৎপাদনের জন্য একটি লগ-লগ গতি বৃদ্ধি
GFHP25 ইমিং গাও, ইয়ানসং ফেং, হংগ্যাং হু এবং ইয়ানবিন প্যান। র্যাঙ্ক-३ জালির মাধ্যমে উৎপাদন এবং শক্তি ভাজক সমস্যা

এই পেপারটি নির্ধারণমূলক সংখ্যা তত্ত্ব অ্যালগরিদম ক্ষেত্রে গুরুত্বপূর্ণ অবদান রাখে, চতুর প্রযুক্তিগত উদ্ভাবনের মাধ্যমে পরামিতির উল্লেখযোগ্য উন্নতি অর্জন করে এবং ভবিষ্যত গবেষণার জন্য মূল্যবান সরঞ্জাম এবং চিন্তাভাবনা প্রদান করে।