প্রিমিটিভ রুট#

সংজ্ঞা#

মডুলার পাটিগণিতে, একটি সংখ্যা $g$ কে n এর মডুলোতে প্রিমিটিভ রুট বলা হয় যদি $n$ এর সাথে সহমৌলিক প্রতিটি সংখ্যা $g$ এর কোনো ঘাতের সাথে $n$ মডুলোতে সর্বসম হয়। গাণিতিকভাবে, $g$ হলো n এর মডুলোতে প্রিমিটিভ রুট যদি এবং কেবলমাত্র যদি যেকোনো পূর্ণ সংখ্যা $a$ এর জন্য যেখানে $\gcd(a, n) = 1$, এমন একটি পূর্ণ সংখ্যা $k$ থাকে যেন:

$g^k \equiv a \pmod n$

$k$ কে তখন $g$ ভিত্তিক $a$ এর ইনডেক্স বা ডিসক্রিট লগারিদম বলা হয় $n$ মডুলোতে। $g$ কে $n$ মডুলোতে পূর্ণ সংখ্যাদের গুণন গ্রুপের জেনারেটর-ও বলা হয়।

বিশেষত, $n$ মৌলিক সংখ্যা হলে, প্রিমিটিভ রুটের ঘাতগুলো $1$ থেকে $n-1$ পর্যন্ত সব সংখ্যার মধ্য দিয়ে যায়।

অস্তিত্ব#

$n$ এর মডুলোতে প্রিমিটিভ রুট থাকে যদি এবং কেবলমাত্র যদি:

• $n$ হলো ১, ২, ৪, অথবা
• $n$ হলো একটি বিজোড় মৌলিক সংখ্যার ঘাত $(n = p^k)$, অথবা
• $n$ হলো একটি বিজোড় মৌলিক সংখ্যার ঘাতের দ্বিগুণ $(n = 2 \cdot p^k)$।

এই উপপাদ্যটি গাউস ১৮০১ সালে প্রমাণ করেছিলেন।

অয়লার ফাংশনের সাথে সম্পর্ক#

ধরি $g$ হলো $n$ এর মডুলোতে একটি প্রিমিটিভ রুট। তাহলে আমরা দেখাতে পারি যে ক্ষুদ্রতম সংখ্যা $k$ যার জন্য $g^k \equiv 1 \pmod n$ সেটি হলো $\phi (n)$। তাছাড়া, উল্টোটাও সত্য, এবং এই তথ্যটি এই নিবন্ধে প্রিমিটিভ রুট খুঁজতে ব্যবহৃত হবে।

এছাড়াও, $n$ এর মডুলোতে প্রিমিটিভ রুটের সংখ্যা, যদি কোনোটি থাকে, $\phi (\phi (n) )$ এর সমান।

প্রিমিটিভ রুট খোঁজার অ্যালগরিদম#

একটি সরল অ্যালগরিদম হলো $[1, n-1]$ রেঞ্জের সব সংখ্যা বিবেচনা করা। এবং তারপর প্রতিটি সংখ্যা প্রিমিটিভ রুট কিনা তা পরীক্ষা করা, এর সব ঘাত হিসাব করে দেখা যে সেগুলো সব আলাদা কিনা। এই অ্যালগরিদমের কমপ্লেক্সিটি $O(g \cdot n)$, যা অনেক ধীর হবে। এই বিভাগে আমরা বেশ কিছু সুপরিচিত উপপাদ্য ব্যবহার করে একটি দ্রুততর অ্যালগরিদম প্রস্তাব করছি।

আগের বিভাগ থেকে আমরা জানি যে যদি ক্ষুদ্রতম সংখ্যা $k$ যার জন্য $g^k \equiv 1 \pmod n$ সেটি $\phi (n)$ হয়, তাহলে $g$ একটি প্রিমিটিভ রুট। যেহেতু $n$ এর সাথে সহমৌলিক যেকোনো সংখ্যা $a$ এর জন্য, অয়লারের উপপাদ্য থেকে আমরা জানি যে $a ^ { \phi (n) } \equiv 1 \pmod n$, তাই $g$ প্রিমিটিভ রুট কিনা পরীক্ষা করতে, $\phi (n)$ এর চেয়ে ছোট সব $d$ এর জন্য পরীক্ষা করা যথেষ্ট যে $g^d \not \equiv 1 \pmod n$। তবে, এই অ্যালগরিদমও এখনো অনেক ধীর।

ল্যাগ্রাঞ্জের উপপাদ্য থেকে আমরা জানি যে $n$ মডুলোতে যেকোনো সংখ্যার ১ এর ইনডেক্স অবশ্যই $\phi (n)$ এর একটি ভাজক হতে হবে। সুতরাং, $\phi (n)$ এর সব প্রকৃত ভাজক $d \mid \phi (n)$ এর জন্য পরীক্ষা করাই যথেষ্ট যে $g^d \not \equiv 1 \pmod n$। এটি ইতিমধ্যে অনেক দ্রুত অ্যালগরিদম, কিন্তু আমরা আরো ভালো করতে পারি।

$\phi (n) = p_1 ^ {a_1} \cdots p_s ^ {a_s}$ উৎপাদক বিভাজন করি। আমরা প্রমাণ করি যে পূর্ববর্তী অ্যালগরিদমে, শুধুমাত্র $\frac { \phi (n) } {p_j}$ আকারের $d$ এর মানগুলো বিবেচনা করাই যথেষ্ট। প্রকৃতপক্ষে, ধরি $d$ হলো $\phi (n)$ এর যেকোনো প্রকৃত ভাজক। তাহলে, স্পষ্টতই, এমন $j$ আছে যেন $d \mid \frac { \phi (n) } {p_j}$, অর্থাৎ $d \cdot k = \frac { \phi (n) } {p_j}$। তবে, যদি $g^d \equiv 1 \pmod n$ হয়, তাহলে আমরা পাবো:

$g ^ { \frac { \phi (n)} {p_j} } \equiv g ^ {d \cdot k} \equiv (g^d) ^k \equiv 1^k \equiv 1 \pmod n$

অর্থাৎ $\frac {\phi (n)} {p_i}$ আকারের সংখ্যাগুলোর মধ্যে অন্তত একটি থাকবে যেখানে শর্ত পূরণ হবে না।

এখন আমাদের কাছে প্রিমিটিভ রুট খোঁজার একটি সম্পূর্ণ অ্যালগরিদম আছে:

• প্রথমে, $\phi (n)$ বের করুন এবং এর উৎপাদক বিভাজন করুন।

• তারপর $g \in [1, n]$ এর সব সংখ্যার মধ্য দিয়ে যান, এবং প্রতিটি সংখ্যার জন্য, এটি প্রিমিটিভ রুট কিনা পরীক্ষা করতে, আমরা নিচের কাজটি করি:

  • সব $g ^ { \frac {\phi (n)} {p_i}} \pmod n$ হিসাব করুন।
  • যদি সব হিসাবকৃত মান $1$ থেকে ভিন্ন হয়, তাহলে $g$ একটি প্রিমিটিভ রুট।

  এই অ্যালগরিদমের রানটাইম হলো $O(Ans \cdot \log \phi (n) \cdot \log n)$ (ধরে নিচ্ছি $\phi (n)$ এর $\log \phi (n)$ টি ভাজক আছে)।

Shoup (১৯৯০, ১৯৯২) প্রমাণ করেছেন, সাধারণীকৃত রিম্যান অনুমান ধরে নিয়ে, $g$ হলো $O(\log^6 p)$।

ইমপ্লিমেন্টেশন#

নিচের কোড ধরে নেয় যে মডুলো p একটি মৌলিক সংখ্যা। যেকোনো p এর মানের জন্য এটি কাজ করাতে, $\phi (p)$ এর হিসাব যোগ করতে হবে।

int powmod (int a, int b, int p) {
	int res = 1;
	while (b)
		if (b & 1)
			res = int (res * 1ll * a % p),  --b;
		else
			a = int (a * 1ll * a % p),  b >>= 1;
	return res;
}

int generator (int p) {
	vector<int> fact;
	int phi = p-1,  n = phi;
	for (int i=2; i*i<=n; ++i)
		if (n % i == 0) {
			fact.push_back (i);
			while (n % i == 0)
				n /= i;
		}
	if (n > 1)
		fact.push_back (n);

	for (int res=2; res<=p; ++res) {
		bool ok = true;
		for (size_t i=0; i<fact.size() && ok; ++i)
			ok &= powmod (res, phi / fact[i], p) != 1;
		if (ok)  return res;
	}
	return -1;
}