কিভাবে একটি বড় প্রাইম নম্বর তৈরি করবেন | কোয়ান্টা ম্যাগাজিন

প্রাইম সংখ্যাগুলি জটিল জিনিস। আমরা স্কুলে শিখি যে তারা এমন সংখ্যা যার মধ্যে 1 এবং নিজেরাই ব্যতীত অন্য কোন ফ্যাক্টর নেই এবং গণিতবিদরা হাজার হাজার বছর ধরে জানেন যে তাদের মধ্যে অসীম সংখ্যা রয়েছে। কমান্ডের উপর একটি উত্পাদন করা কঠিন হবে বলে মনে হচ্ছে না।

কিন্তু এটা. নির্বিচারে বড় মৌলিক সংখ্যা তৈরি করা উল্লেখযোগ্যভাবে জটিল। আপনার কাছে মূলত দুটি কম্পিউটেশনাল বিকল্প রয়েছে, উভয়ই ত্রুটি রয়েছে। আপনি এলোমেলোতা ব্যবহার করতে পারেন এবং অনুমান করে একটি খুঁজে পেতে পারেন, কিন্তু পদ্ধতিটি অসামঞ্জস্যপূর্ণ — আপনি প্রতিবার একটি ভিন্ন প্রাইম তৈরি করার ঝুঁকি চালান। অথবা আপনি একটি আরো নির্ভরযোগ্য, নির্ধারক অ্যালগরিদম ব্যবহার করতে পারেন, কিন্তু একটি ভারী গণনামূলক খরচে।

মে মাসে কম্পিউটার বিজ্ঞানীদের একটি দল ড দেখিয়েছেন যে এক ধরনের হাইব্রিড পদ্ধতিও কাজ করতে পারে। তারা একটি অ্যালগরিদম প্রকাশ করেছে যা কার্যকরভাবে একটি নির্দিষ্ট দৈর্ঘ্যের একটি মৌলিক সংখ্যা আউটপুট করার জন্য এলোমেলো এবং নির্ধারক পদ্ধতির সমন্বয় করে, অ্যালগরিদমটি বহুবার চালানো হলেও একইটি প্রদানের উচ্চ সম্ভাবনা রয়েছে। অ্যালগরিদম এলোমেলোতা এবং জটিলতাকে আকর্ষণীয় উপায়ে সংযুক্ত করে এবং এটি ক্রিপ্টোগ্রাফির জন্যও উপযোগী হতে পারে, যেখানে কিছু এনকোডিং স্কিম বড় প্রাইম নির্মাণের উপর নির্ভর করে।

"তারা প্রচেষ্টার একটি ক্রম তৈরি করেছে, তাদের প্রত্যেকে একটি ভিন্ন দৈর্ঘ্যের একটি মৌলিক সংখ্যা তৈরি করার চেষ্টা করছে, এবং দেখিয়েছে যে একটি প্রচেষ্টা কাজ করে," বলেন Roei বল, ইনস্টিটিউট ফর অ্যাডভান্সড স্টাডির একজন তাত্ত্বিক কম্পিউটার বিজ্ঞানী যিনি কাজের সাথে জড়িত ছিলেন না। "এটি এমন একটি নির্মাণ যা একটি নির্ধারকভাবে নির্বাচিত প্রাইমকে আউটপুট করে, কিন্তু আপনাকে কয়েন টস করতে এবং প্রক্রিয়ায় এলোমেলো পছন্দ করতে দেয়।"

প্রাইমগুলির জন্য একটি দক্ষ রেসিপি তৈরির চ্যালেঞ্জের শিকড় গভীর। "প্রাইমগুলি কীভাবে বিতরণ করা হয় বা প্রাইমগুলির ফাঁক সম্পর্কে আমরা সত্যিই তেমন কিছু জানি না," বলেছেন ওফার গ্রসম্যান, যিনি সিউডোর্যান্ডম অ্যালগরিদম অধ্যয়ন করেন৷ এবং যদি আমরা জানি না সেগুলি কোথায় পাওয়া যায়, তাহলে স্ক্র্যাচ থেকে একটি মৌলিক সংখ্যা তৈরি করার কোন সহজ উপায় নেই।

সময়ের সাথে সাথে, গবেষকরা উল্লিখিত পদ্ধতিগুলি তৈরি করেছেন। সহজ উপায় শুধু অনুমান করা হয়. আপনি যদি 1,000 সংখ্যা সহ একটি প্রাইম চান, উদাহরণস্বরূপ, আপনি এলোমেলোভাবে একটি 1,000-সংখ্যার সংখ্যা চয়ন করতে পারেন এবং তারপরে এটি পরীক্ষা করতে পারেন। "যদি এটি প্রাইম না হয়, আপনি শুধু অন্য একটি চেষ্টা করুন, এবং অন্যটি, এবং যতক্ষণ না আপনি একটি খুঁজে পান," বলেন রাহুল সান্থানম, অক্সফোর্ড বিশ্ববিদ্যালয়ের একজন কম্পিউটার বিজ্ঞানী এবং নতুন গবেষণাপত্রের সহ-লেখক। "যেহেতু অনেক প্রাইম আছে, এই অ্যালগরিদম আপনাকে এমন কিছু সংখ্যা দেবে যা উচ্চ সম্ভাবনার সাথে প্রাইম হবে, তুলনামূলকভাবে অল্প সংখ্যক পুনরাবৃত্তির পরে।" কিন্তু এলোমেলোতা ব্যবহার করার অর্থ আপনি সম্ভবত প্রতিবার একটি ভিন্ন নম্বর পাবেন, তিনি বলেছিলেন। আপনার যদি সামঞ্জস্যের প্রয়োজন হয় তবে এটি একটি সমস্যা হতে পারে — যদি বলুন, আপনি সুরক্ষার একটি ক্রিপ্টোগ্রাফিক পদ্ধতি ব্যবহার করছেন যা বড় প্রাইমগুলির প্রাপ্যতার উপর নির্ভর করে।

অন্য পদ্ধতি হল একটি নির্ধারক অ্যালগরিদম নিয়ে যাওয়া। আপনি একটি প্রারম্ভিক বিন্দু বেছে নিতে পারেন এবং প্রাথমিকতার জন্য পর্যায়ক্রমে নম্বর পরীক্ষা করা শুরু করতে পারেন। অবশেষে আপনি একটি খুঁজে পেতে নিয়তি করেছেন, এবং আপনার অ্যালগরিদম ধারাবাহিকভাবে প্রথমটি খুঁজে বের করবে। তবে এটি কিছুটা সময় নিতে পারে: আপনি যদি 1,000 সংখ্যা সহ একটি মৌলিক সংখ্যা খুঁজছেন, এমনকি 2 সহ একটি গণনাও⁵⁰⁰ পদক্ষেপগুলি - যা মহাবিশ্বের বয়সের চেয়ে অনেক বেশি সময় নেবে - সাফল্যের গ্যারান্টি দেওয়ার জন্য যথেষ্ট নয়।

2009 সালে, গণিতবিদ এবং ফিল্ডস পদক বিজয়ী টেরেন্স টাও আরও ভাল করতে চেয়েছিলেন। তিনি গণিতবিদদের একটি গণনামূলক সময়সীমার মধ্যে একটি নির্দিষ্ট আকারের প্রাইম খুঁজে বের করার জন্য একটি নির্ধারক অ্যালগরিদম নিয়ে আসার জন্য চ্যালেঞ্জ করেছিলেন।

সেই সময়সীমা বহুপদী সময় হিসাবে পরিচিত। একটি অ্যালগরিদম বহুপদী সময়ে একটি সমস্যা সমাধান করে যদি এটি গ্রহণ করা পদক্ষেপগুলির সংখ্যা একটি বহুপদী ফাংশনের চেয়ে বেশি না হয় n, ইনপুটের আকার। (একটি বহুপদী ফাংশন এমন পদগুলিকে অন্তর্ভুক্ত করে যেগুলির ভেরিয়েবলগুলিকে ধনাত্মক পূর্ণসংখ্যা শক্তিতে উত্থাপিত করে, যেমন n² অথবা 4n³.) মৌলিক সংখ্যা নির্মাণ প্রসঙ্গে, n আপনি চান প্রাইম সংখ্যার সংখ্যা বোঝায়। গণনামূলকভাবে বলতে গেলে, এর জন্য খুব বেশি খরচ হয় না: কম্পিউটার বিজ্ঞানীরা বহুপদী সময়ে অ্যালগরিদম দ্বারা সহজে সমাধান করা সমস্যাগুলি বর্ণনা করেন। বিপরীতে, একটি কঠিন সমস্যা, সূচকীয় সময় নেয়, যার মানে এটি একটি সূচকীয় ফাংশন দ্বারা আনুমানিক বেশ কয়েকটি পদক্ষেপের প্রয়োজন (যার মধ্যে 2 এর মতো পদ রয়েছেⁿ).

কয়েক দশক ধরে, গবেষকরা এলোমেলোতা এবং কঠোরতার মধ্যে সংযোগটি তদন্ত করেছেন। যদি আপনি এলোমেলোতার অনুমতি দেন তবে প্রাথমিক সংখ্যা নির্মাণের সমস্যাটিকে সহজ বলে মনে করা হত — এবং প্রতিবার আলাদা নম্বর পেয়ে সন্তুষ্ট হন — এবং কঠিন যদি আপনি নির্ধারকতার উপর জোর দেন।

কেউ এখনও টাও-এর চ্যালেঞ্জ মেটাতে পারেনি, কিন্তু নতুন কাজ কাছাকাছি আসে। এটি ম্যাসাচুসেটস ইনস্টিটিউট অফ টেকনোলজির কম্পিউটার বিজ্ঞানী শফি গোল্ডওয়াসার এবং এরান গ্যাট দ্বারা 2011 সালে প্রবর্তিত একটি পদ্ধতির উপর ব্যাপকভাবে আকর্ষণ করে। তারা "সিউডোডেটারমিনিস্টিক" অ্যালগরিদমগুলি বর্ণনা করেছে — অনুসন্ধান সমস্যার জন্য গাণিতিক রেসিপি, যেমন বড় প্রাইমগুলি সন্ধান করা, যা এলোমেলোতার সুবিধাগুলিকে কাজে লাগাতে পারে এবং উচ্চ সম্ভাবনার সাথে, এখনও প্রতিবার একই উত্তর তৈরি করে৷ তারা রেসিপিতে র্যান্ডম বিটের দক্ষতা ব্যবহার করবে, যা ফলাফলে ডি-এলোমেলো হয়ে যাবে, নির্ধারক দেখাবে।

গবেষকরা তখন থেকেই সিউডোডেটারমিনিস্টিক অ্যালগরিদম অন্বেষণ করছেন। 2017 সালে, ওয়ারউইক বিশ্ববিদ্যালয়ের সান্থানাম এবং ইগর অলিভেরা (যারা নতুন কাজেও অবদান রেখেছিলেন) বর্ণিত প্রাইম নির্মাণের জন্য একটি সিউডোডেটারমিনিস্টিক পদ্ধতি যা এলোমেলোতা ব্যবহার করে এবং দৃঢ়ভাবে নির্ণয়বাদী দেখায়, কিন্তু এটি "উপ-এক্সপোনেনশিয়াল" সময়ে কাজ করে — সূচকীয় সময়ের চেয়ে দ্রুত, কিন্তু বহুপদী সময়ের চেয়ে ধীর। তারপর 2021 সালে, বলুন এবং লিজি চেন, ক্যালিফোর্নিয়া বিশ্ববিদ্যালয়ের একজন কম্পিউটার বিজ্ঞানী, বার্কলে, অন্বেষণ একটি ছদ্ম র্যান্ডম নম্বর জেনারেটর তৈরি করতে কীভাবে একটি কঠিন সমস্যা ব্যবহার করবেন (একটি অ্যালগরিদম যা একটি এলোমেলো আউটপুট থেকে আলাদা করা যায় না এমন একটি স্ট্রিং তৈরি করে)। "[আমরা] কঠোরতা এবং সিউডোর্যান্ডমনেসের মধ্যে একটি নতুন সংযোগ খুঁজে পেয়েছি," চেন বলেছেন।

টুকরোগুলি অবশেষে 2023 সালের বসন্তে একত্রিত হয়েছিল কম্পিউটেশনাল জটিলতার উপর একটি বুটক্যাম্প বার্কলেতে সিমন্স ইনস্টিটিউট ফর দ্য থিওরি অফ কম্পিউটিং-এ, যখন গবেষকরা অতীতের ফলাফলগুলি একসাথে বুনতে সমস্যাটির উপর একসাথে কাজ শুরু করেছিলেন। নতুন কাজের জন্য, চেন বলেছেন, হ্যানলিন রেন - অক্সফোর্ডের একজন কম্পিউটার বিজ্ঞানী এবং একজন সহ-লেখক - একটি অভিনব উপায়ে সানথানাম-অলিভেইরা পদ্ধতির সাথে চেন-টেলের ফলাফলকে একত্রিত করার প্রাথমিক ধারণা ছিল৷ তারপর পুরো দলটি নতুন কাগজ তৈরি করার জন্য ধারণাগুলিকে আরও সম্পূর্ণরূপে বিকাশ করেছিল।

সানথানাম বলেছেন, ফলস্বরূপ সিউডোডেটারমিনিস্টিক অ্যালগরিদম, বহুপদী সময়ে মৌলিক সংখ্যা তৈরি করতে অতীতের কাজ দেখার নতুন উপায় ব্যবহার করেছে। এটি প্রমাণিতভাবে একটি নির্দিষ্ট দৈর্ঘ্যের একটি মৌলিক সংখ্যা আউটপুট করার জন্য এলোমেলোতা ব্যবহার করেছে এবং সরঞ্জামটি এলোমেলো অনুমানের চেয়ে আরও সঠিক এবং নির্ধারক ক্রাঞ্চিংয়ের চেয়ে গণনাগতভাবে আরও দক্ষ।

নতুন অ্যালগরিদমটিও অসাধারণভাবে সহজ, সানথানাম বলেন, এবং এটি সার্চ সমস্যার একটি বিস্তৃত পরিসরে প্রয়োগ করা যেতে পারে — প্রকৃতপক্ষে, সংখ্যার যে কোনো ঘন উপসেট, যেমন মৌলিক, যার জন্য সদস্যপদ বহুপদী সময়ে নির্ধারণ করা যেতে পারে। কিন্তু এটা নিখুঁত নয়। অ্যালগরিদম অসীমভাবে অনেক ইনপুট দৈর্ঘ্যের জন্য কাজ করে, কিন্তু এটি সমস্ত দৈর্ঘ্যের সংখ্যাকে কভার করে না। এর কিছু মান এখনও থাকতে পারে n সেখানে যার জন্য অ্যালগরিদম নির্ধারকভাবে একটি প্রাইম তৈরি করে না।

"এই ছোট সতর্কতা থেকে পরিত্রাণ পেতে এটি দুর্দান্ত হবে," গ্রসম্যান বলেছিলেন।

সানথানাম বলেন, চূড়ান্ত লক্ষ্য হল এমন একটি অ্যালগরিদম খুঁজে বের করা যার জন্য এলোমেলোতার প্রয়োজন নেই। কিন্তু সেই অনুসন্ধান খোলা থাকে। "নিশ্চয়তাবাদ আমরা ব্যবহার করতে চাই," তিনি বলেন.

কিন্তু তিনি এও উল্লেখ করেছেন যে সিউডোর্যান্ডম প্রক্রিয়াগুলি শক্তিশালী সরঞ্জাম, এবং প্রাইম নির্মাণের মতো প্রকল্পগুলি গণিত, কম্পিউটার বিজ্ঞান, তথ্য তত্ত্ব এবং অন্যান্য ক্ষেত্রগুলির ধারণাগুলিকে সংযুক্ত করার জন্য তাদের ব্যবহার করার একটি উপায়।

"এই উজ্জ্বল পর্যবেক্ষণগুলি অন্য কোথায় নিয়ে যাবে তা চেষ্টা করা এবং চিন্তা করা উত্তেজনাপূর্ণ," টেল বলেছেন।