Category Archives: Bangla

ভোরের কুয়াশাস্নাত রোদের আঁচল
লুকিয়ে রেখো আমার কিছু ব্যর্থতা।
অর্ধরাতের জন্য পুরোনো জৌলুশটুকু বড্ড প্রয়োজন।
আজ আমার মন ভাল নেই।

নৈশব্দ

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

(অসমাপ্ত)

শহর

প্রতিটি ক্লান্ত দিনের শেষে
পরমকাঙ্ক্ষিত বিকেলের মত
তোমাকে আমার প্রয়োজন।

প্রতিটি প্রিয় ছুটির দিনে
আলস্যমাখা দিবানিদ্রার মতো
তোমাকে আমার প্রয়োজন।

একবার এসো না এই শহরে!
তোমাকে আমার বড্ড প্রয়োজন।

কীভাবে প্রোটিন তৈরি হয়?

আগামী কয়েকদিন আমি কিছু জীববিজ্ঞানের বিষয় নিয়ে পোস্ট করব। আমার আনুষ্ঠানিক পড়ার বিষয়ের সাথে এগুলোর খুব একটা সংযোগ নেই, যদিও অনানুষ্ঠানিক একাডেমিক কৌতূহল স্বতঃস্ফূর্তভাবেই ছিল। আমি মোটামুটি নিশ্চিত আগামী তিন মাসের মাঝে এসবের  বেশিরভাগই আমার মনে থাকবে না। তাই এগুলো লিখে রাখার চেষ্টা করা হল। সহজবোধ্যতার খাতিরে কিছু ক্ষেত্রে টপিকগুলো অনেকখানি সরলীকরণ করা হবে। এগুলো কারও কৌতূহল মেটাবার খোরাক হতে পারে, কিন্তু রেফারেন্স হিসেবে মোটেই ব্যবহার উপযোগী নয়। যদি কারও বিস্তারিত জানার ইচ্ছে থাকে, তবে এমাইটির কোর্স ৭.০১২ বা ৭.০১৬ অনলাইনে দেখতে পরামর্শ দেওয়া হল।

প্রোটিন এবং এমিনো এসিড

জীবন নিয়ে আলোচনা শুরু করতে হয় এমিনো এসিড দিয়ে। এগুলো কোষের অসংখ্য ফাংশনর জন্য অপরিহার্য। এমিনো এসিড হচ্ছে কিছু জৈবিক অণু যাদের মাঝে একটি এমিন গ্রুপ (\(-NH_2\)), একটি কার্বক্সিলিক এসিড গ্রুপ (\(-COOH\)) এবং একটি সাইড চেইন (\(-R\)) দেখতে পাওয়া যায়। যদিও প্রায় ৫০০ টির মত এমিনো এসিড এখন পর্যন্ত আবিষ্কৃত হয়েছে, এদের মাঝে মাত্র ২০ টিকে জীবের জেনেটিক কোডে পাওয়া যায়।

এমিনো এসিডের চার্ট। (ছবির সোর্স: https://mindfulmedstudent.net/2017/04/19/three-acronym-mnemonics-for-remembering-the-amino-acids/)

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

পেপটাইড বন্ধন। (ছবির সোর্স: http://www.assignmentpoint.com/science/chemistry/peptide-bond.html)

প্রোটিন হচ্ছে এমন এক বা একাধিক পলিপেপটাইড চেইনের সমন্বয়ে গঠিত বিশাল এক জৈবিক অণু। কোন পলিপেপ্টাইড চেইনের যেকোনো অবস্থানে বিশটি এমিনো এসিডের যেকোনোটি বসতে পারে। তাই মাত্র \(30\) টি পলিপেপ্টাইড চেইনের ভিন্ন ভিন্ন কম্বিনেশন হতে পারে \(20^{30}\) টি! যেকোন অর্গানিজমের প্রোটিনে এর চেয়ে বড় পপিপেপ্টাইড চেইন অহরহই দেখা যায়। এজন্যই যেকোন অর্গানিজমে এত ভিন্ন ভিন্ন প্রোটিন পাওয়া সম্ভব। তবে মনে রাখতে হবে শুধু এমিনো এসিডের বৈচিত্র্য নয়, প্রোটিনের ত্রিমাত্রিক আকারও এর কার্যকারীতার পেছনে ভূমিকা পালন করে। এজন্যই অনেক প্রোটিন তাপ, pH প্রভৃতিতে সংবেদনশীল (sensitive) হয়ে থাকে। যেমন- তাপে অনেক প্রোটিনের পলিপেপ্টাইড চেইনগুলো বিমুক্ত হয়ে যায় এবং তাপ সরিয়ে নিলেও আবার সেগুলো পূর্বের অবস্থায় ফেরত আসে না। এজন্যই ডিম সেদ্ধ করলে জমাট বেঁধে যায়।

প্রতিটি প্রোটিন বানানোর রেসিপি লিখা থাকে জীবের ডিএনএ বা আরএনএতে। কিন্তু সব কোষে একই ডিএনএ থাকা সত্ত্বেও সব প্রোটিন সব কোষে তৈরি হয় না। তাই প্রোটিন বানানো বুঝতে হলে আমাদের ডিএনএ এবং আরএনএ সম্পর্কে কিছুটা জেনে নেওয়া প্রয়োজন।

ডিএনএ এবং আরএনএ আসলে কী

যেকোন অর্গানিজমকে আসলে কম্পিউটারের সাথে তুলনা করা যায়। কম্পিউটারে যখন কোন তথ্য সংরক্ষণ করে রাখার প্রয়োজন হয়, আমরা ব্যবহার করি হার্ডডিস্ক। তেমনি করে প্রতিটি জীবের সমস্ত জিনগত তথ্য প্রকৃতি সুরক্ষিত রাখে সেই জীবের ডিএনএতে। হার্ডডিস্কে তথ্য লিখে রাখা হয় 0 আর 1 দিয়ে। আর ডিএনএতে তথ্য লিখে রাখা হয় চারটি নাইট্রোজেনাস বেইস পেয়ার দিয়ে, যাদের নাম এডিনিন (A), থাইমিন (T), গুয়ানিন (G) এবং সাইটোসিন (C). খুব গুরুত্বপূর্ণ তথ্য না হলে আমরা সাধারণত গাদা গাদা ব্যাকআপ রাখি না, কিন্তু ডিএনএর সকল তথ্যের ব্যাকআপ রাখা হয় জীবের প্রতিটি কোষে।

ডিএনএর গঠন। (ছবির সোর্স: https://www.easynotecards.com/notecard_set/59549)

ডিএনএর পূর্ণরূপ হল ডিঅক্সি রাইবোনিউক্লিয়িক এসিড। ডিএনএর তিনটি অংশ– নাইট্রোজেনাস বেইস, পাঁচ কার্বনের একটি বিশেষ চিনি (ডিঅক্সি রাইবোজ) এবং ফসফেট গ্রুপ। ডিএনএতে সাপের মতো দুইটি আঁকাবাঁকা সুতায় ফসফেট গ্রুপ আর চিনির ভিতের ওপর বেইসগুলো সারিবদ্ধভাবে সাজানো থাকে। দুইটি সুতার বিপরীত বেইসগুলো হাইড্রোজেন বন্ধনের কারণে পরস্পরের সাথে যুক্ত। ডিএনএর দুইটি সুতা কমপ্লিমেন্টারি, অর্থাৎ একে অন্যের ছাঁচের মত। এক সুতায় A-র বিপরীতে অন্য সুতায় সবসময় T, এবং C-এর বিপরীতে অন্য সুতায় সবসময় G বসে।

ডিঅক্সি রাইবোজের কার্বনগুলোকে জৈবযৌগের নামকরণের নিয়মে নাম্বার দেওয়া হলে ডিএনএর প্রত্যেকটি সুতার এক মাথায় 5′ বিশিষ্ট কার্বন এবং অন্য মাথায় 3′ বিশিষ্ট কার্বন পড়ে। এই অনুসারে  মাথা দুইটিকে 5′ মাথা এবং 3′ মাথা বলা হয়। তবে  দুইটি কমপ্লিমেন্টারি সুতার একই মাথা বিপরীত দিকে থাকে।

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

ডিএনএ এবং জিন

ডিএনএ একটি জীবের বংশগত সকল তথ্য সংরক্ষণ করে। কিন্তু বেঁচে থাকার জন্য তথ্য শুধু সংরক্ষণ করে রাখাই যথেষ্ট নয়। এই তথ্য ব্যবহারও করতে পারা প্রয়োজন। সেটা কীভাবে করা যায়? উত্তরটা হচ্ছে প্রোটিন বানিয়ে!

একটা অর্গানিজমের সম্পূর্ণ ডিএনএ অনেক লম্বা। যেমন- মানুষের পূর্ণাঙ্গ ডিএনএর দৈর্ঘ্য প্রায় ছয় ফুট! এই সবটুকু ডিএনএতে কিন্তু প্রোটিন বানানোর রেসিপি লিখা থাকে না, বরং কিছু কিছু অংশে থাকে। এগুলোই হচ্ছে জিন (Gene). আরেকটু একাডেমিক ভাষায় জিন হচ্ছে ডিএনএর এমন কোন খন্ড যা ফাংশনাল কোন অণুর কোড ধারণ করে। একটি জিনের বেশ কয়েকটি অংশ:

  1. প্রোমোটার (Promoter)
  2. আন্ট্রান্সলেটেড রিজিয়ন (Untranslated Region or UTR)
  3. ওপেন রিডিং ফ্রেম
  4. টার্মিনেটর
জিনের স্ট্রাকচার। (ছবির সোর্স: https://en.wikipedia.org/wiki/Gene_structure)

এছাড়া ট্রানস্ক্রিপশন ফ্যাক্টর নামের কিছু প্রোটিন কোন জিনের প্রকাশের (expression) জন্য অপরিহার্য। যখন কোষের কোন জিন থেকে প্রোটিন বানানোর প্রয়োজন হয়, অনেকগুলো ভিন্ন ভিন্ন  ট্রান্সক্রিপশন ফ্যাক্টর জিনটির প্রোমোটার অংশে যুক্ত হয়। সব ট্রানস্ক্রিপশন ফ্যাক্টর সব কোষে থাকে না। তাই সব জিন সব কোষে প্রকাশিত হয় না।

প্রোটিন সিন্থেসিস

প্রায় পঞ্চাশটির মত ট্রান্সক্রিপশন ফ্যাক্টর প্রোমোটার অংশে যুক্ত হলে আরএনএ পলিমারেজ (RNA Polymerase) নামের একটি এনজাইম ডিএনএ থেকে সেই জিনের কোড কপি করে মেসেঞ্জার আরএনএ তৈরি করা শুরু করে। তবে ডিএনএতে একটি বিশেষ সিকুয়েন্স পাওয়ার আগে এই কপি করা শুরু হয় না। এই স্থানটির নাম স্টার্ট কোডন (Start Codon). অধিকাংশ অর্গানিজমে এটি হচ্ছে ATG. প্রোমোটার এবং স্টার্ট কোডনের মাঝের অংশটি মেসেঞ্জার আরএনএতে কপি করা হয় না। একে বলে আনট্রান্সলেটেড রিজিয়ন বা ইউটিআর। আরএনএ পলিমারেজ স্টার্ট কোডন থেকে পরের বেইসগুলো একটির পর একটি করে মেসেঞ্জার আরএনএতে কপি করতে থাকে। পরবর্তীতে এনজাইমটি ডিএনএতে একটি বিশেষ স্থানে গেলে কপি করা সমাপ্ত হয়, এবং মেসেঞ্জার আরএনএটি মুক্ত হয়। এই স্থানটির নাম টার্মিনেটর। ইউটিআর এবং টার্মিনেটরের মধ্যবর্তী অংশটির নাম ওপেন রিডিং ফ্রেম।

ওপেন রিডিং ফ্রেমে কিছু স্থান থাকে যেগুলো প্রোটিনের কোন অংশের কোড করে না। এদের বলে ইন্ট্রন (Intron). বাকি অংশগুলোকে বলে এক্সন (Exon). সদ্য সৃষ্ট মেসেঞ্জার আরএনএ থেকে ইন্ট্রনগুলোকে কেটে বাদ দেওয়া হয়, এবং অবশিষ্ট অংশগুলোকে জোড়া লাগানো হয়। মধ্যবর্তী এক বা একাধিক এক্সনও বাদ যেতে পারে। এভাবে একই জিন থেকে কোষ একাধিক প্রোটিন তৈরি করতে পারে। এরপরে মেসেঞ্জার আরএনএগুলোকে বিকৃতির হাত থেকে রক্ষার জন্য 5′ মাথায় একটি ক্যাপ এবং 3′ মাথায় অনেকগুলো A দিয়ে তৈরি একটি লেজ জুড়ে দেওয়া হয়।

এরপর এই পরিপক্ক (mature) মেসেঞ্জার আরএনএগুলো কোষের নিউক্লিয়াস ছেড়ে বাইরে বেরিয়ে আসে। কোষের রাইবোজোম তখন সেই মেসেঞ্জার আরএনএর কোড পড়ে পর পর তিন বেইসের প্রতিটি কম্বিনেশনের  জন্য একটি নির্দিষ্ট এমিনো এসিড সংযুক্ত করে এমিনো এসিডের একটি শেকল  বা পলিপেপ্টাইড চেইন তৈরি করে। এই প্রক্রিয়াটির নাম ট্রান্সলেশন বা অনুবাদ।

 

এমিনো এসিড কোডন চার্ট। (ছবির সোর্স: https://sites.google.com/a/providenceday.org/apbiology/codon-charts-periodic-table)

মেসেঞ্জার আরএনএতে কিছু বিশেষ তিন বেইসের কোড থাকে যারা পলিপেপ্টাইড চেইনের সূচনা ও সমাপ্তি নির্দেশ করে। সূচনা কোড পেলে রাইবোজোম পলিপেপ্টাইড চেইন তৈরি করা শুরু করে, এবং সমাপ্তি কোড পেলে পলিপেপ্টাইড চেইনটিকে রাইবোজোম মুক্ত করে দেয়। পরবর্তীতে এক বা একাধিক পলিপেপ্টাইড চেইনকে বিশেষভাবে ভাঁজ (folding) করে কাঙ্ক্ষিত প্রোটিনের একটি অণু তৈরি হয়। এই প্রোটিনকে প্লাজমা মেমব্রেন বা কোষের বাইরে পাঠানোর প্রয়োজন পড়লে বিভিন্ন পলিপেপ্টাইডের সিগনাল সিকুয়েন্স যুক্ত হয়। কোষে কিছু সিগনাল রিকগনিশন পার্টিকেল (এসআরপি) থাকে যারা এই বিশেষ বিশেষ সিগনাল সিকুয়েন্সের সাথে যুক্ত হয়ে ঠিক ঠিক স্থানে প্রোটিনকে প্রেরণ করতে সাহায্য করে।

এভাবেই তৈরি হয় একেকটি প্রোটিন!

এলোমেলো

তুমি অলস দুপুরে একেলা ঘুঘুর স্বর,
শরতের রোদ, ঈশান কোণের অভিমানী ঝড়।
তুমি প্রতিদিন শেষে আমার পূর্ণ ঘর!

তুমি মেঘের ফাঁকে একটুখানি নীল,
পুরানো বইয়ের ঘ্রাণ, প্রিয় কবিতার অন্ত্যমিল।
তুমি আচমকা তপ্ত মন জুরিয়ে দেওয়া ঝিল!

খন্ডচিন্তা

আমার মনে হয় মানুষের দুঃখবোধ ফিলিংসটার একটা আপার লিমিট আছে।

কথাটা একটু ব্যাখ্যা করি। ধরুন, আপনার প্রিয় কোন মানুষের কথা। তার সাথে একসাথে ঘুরতে ভাল লাগে, কথা বলতে ভাল লাগে, মজা করতে ভাল লাগে। ফট করে যদি একদিন সে দুনিয়া থেকে নাই হয়ে যায়, কেমন লাগবে?

এমন অনেক মানুষ আছে যাদের পুরো ফ্যামিলি তাদের চোখের সামনে মারা গেছে। অনেকে কন্সেন্ট্রেশন ক্যাম্পে মাসের পর মাস অত্যাচারের মধ্য দিয়ে গেছে। অনেকে বারংবার ধর্ষিত হয়েছে। এরা এত কষ্টের পর বেঁচে থাকে কীভাবে?

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

কিন্তু মানুষের আনন্দের ব্যাপারটা অন্যরকম। হাজার হাজার বার ঘোরা হলেও বন্ধুদের নিয়ে ঘুরতে যেতে ভাল লাগে, আড্ডা দিতে ভাল লাগে। নতুন বই পড়তে ভাল্লাগে, মুভি দেখতে ভাল্লাগে। হাজার হাজার meme দেখা হলেও নতুন meme দেখতে ভাল্লাগে। আনন্দের কোন শেষ নেই। আনন্দের মনে হয় কোন আপার লিমিটও নেই।

ইন্টিজার ফ্যাক্টোরাইজেশন: পর্ব ১ পোলার্ডের রো (rho) এলগোরিদম

ইন্টিজার ফ্যাক্টোরাইজেশন পর্ব ০

গত পর্বে আমরা গায়ের জোরে কিছু সংখ্যার উৎপাদক বের করার চেষ্টা করেছিলাম। দুঃখজনকভাবে আমাদের বাচ্চা প্রোগ্রামটি \(20\) ডিজিটের একটি সংখ্যাকে উৎপাদকে বিশ্লেষণ করতে গিয়ে ক্লান্ত হয়ে গিয়েছিল। \(50\) বা \(100\) ডিজিটের কোন সংখ্যাকে উৎপাদকে বিশ্লেষণ করতে হলে সেই প্রোগ্রামের কী অবস্থা হবে ভাব একবার!

মানুষ যখন দেখল বড় বড় সংখ্যার জন্য \(2\) থেকে \(N-1\) [কিংবা \(\sqrt N\)] পর্যন্ত সব সংখ্যা দিয়ে \(N\)-কে এমন ভাগ করা অনেক সময়সাপেক্ষ, তখন তারা ট্রিক খুঁজতে লাগল কী করে আরও কম সংখ্যক সংখ্যা দিয়ে ভাগ করে \(N\)-এর উৎপাদক বের করা যায়। এমন অনেকগুলো ট্রিক রয়েছে, যার মাঝে একটি হল জন্মদিন সমস্যা(পরিশিষ্টে দেখ)। একে কাজে লাগিয়ে জন্ম হয়েছে একটি চালাকচতুর এলগোরিদমের।

পোলার্ডের \(\rho\) এলগোরিদম

মনে কর, আমাদেরকে \(N=55\)-কে উৎপাদকে বিশ্লেষণ করতে হবে। (আমরা যদিও জানি যে \(55\) এর একটি উৎপাদক \(p=5\), তবুও আমরা সেটি এলগোরিদম বের করব।)

আমরা করব কি, র‍্যান্ডম পূর্ণসংখ্যার একটি অসীম ধারা (infinite sequence) \(a_0, a_1, a_2, a_3, a_4,\ldots\) [সংক্ষেপে \(\{a_i\}_{i = 0}^{\infty}\)] থেকে খেয়াল খুশিমত কিছু পদ, যেমন: \(a_0, a_3, a_7, a_{100}\), তুলে নেব। জন্মদিন সমস্যা অনুযায়ী, এই চারটি পদের মাঝে \(\pmod {5}\)-এ কনগ্রুয়েন্ট অন্তত দুটি পদ পাওয়ার সম্ভাবনা\[1-e^{-\frac{4^2}{2\times 5}}\approx 80\%\]এমন দুটি পদ \(a_m\) এবং \(a_n\) যদি সত্যি সত্যি থাকে, তাহলে \[a_m\equiv a_n\pmod{5}\]\[\implies a_m-a_n\equiv 0\pmod{5}\]\[\implies d = \gcd(55, a_m-a_n)\ge 5\] অর্থাৎ, আমরা \(55\)-এর একটি উৎপাদক \(d\) নির্ণয় করে ফেলব। অবশ্য কেউ প্রশ্ন করতেই পারে \(d = 55\) হলে? হ্যাঁ, সেটা হতে পারে। কিন্তু চারটি সংখ্যার মাঝে \(\pmod{55}\)-এ কনগ্রুয়েন্ট দুটি সংখ্যা পাওয়ার সম্ভাবনা মাত্র\[1-e^{-\frac{4^2}{2\times 55}}\approx 13.5\%\]

অতএব, আমরা যদি \(\{a_i\}_{i = 0}^{\infty}\) থেকে প্রতিবার যেকোন দুইটি পদ \(a_i\) এবং \(a_j\) নিয়ে \(\gcd(N, a_i-a_j)\) নির্ণয় করে যেতে থাকি, তাহলে খুবই ভাল সম্ভাবনা আছে যে আমরা \(a_m-a_n\) পেয়ে যাব এবং \(55\)-এর একটি প্রকৃত উৎপাদক \(d\) নির্ণয় করে ফেলব।

তবে ঝামেলা হচ্ছে খাঁটি র‍্যান্ডম সংখ্যার অসীম ধারা ব্যবহার করলে সেটির অনেকগুলো পদ আমাদেরকে মেমরিতে রাখতে হবে, ফলে \(50\) বা \(100\) ডিজিটের কোন সংখ্যার জন্য কোটি কোটি পেটাবাইট মেমরির প্রয়োজন হবে। তাই আমরা এমন কোন সংখ্যার ধারা নেব যার মান প্রকৃতপক্ষে ডিটারমিনিস্টিক, অর্থাৎ সূত্র মেনে চলে, কিন্তু \(\pmod p\)-তে মোটামুটি র‍্যান্ডমলি আসে। (এমন সংখ্যাকে বলে সুডোর‍্যান্ডম সংখ্যা)

উদাহরণস্বরূপ, অসীম ধারা হিসেবে \(a_0=1\), এবং \(a_i=a_{i-1}^2+1\), অর্থাৎ \(1, 2, 5, 26, 677,\ldots\) ধারাটি নেওয়া নেব এবং প্রতিটি পদের জন্য \(\gcd(N, a_i-a_0)\) নির্ণয় করব। লক্ষ্য কর যে, আমাদের \(a_i\)-এর প্রকৃত মানের পরিবর্তে \(a_i\pmod N\) জানলেই চলে।

def rhonaive(N):
    a_0 = d = 1
    a_i = a_0
    while d == 1:
        a_i = (a_i * a_i + 1) % N
        d = gcd(a_i - a_0, N)
    return d

অনেকসময় দেখা যেতে পারে আমাদের নেওয়া সুডোর‍্যান্ডম সংখ্যার ধারাটি “যথেষ্ট র‍্যান্ডম” নয়। তেমন ক্ষেত্রে আমাদের \(a_i = a_{i-1}^2+1\) এর পরিবর্তে আরেকটু জটিল কোন সম্পর্ক ব্যবহার করতে হবে। তাই, সাধারণভাবে(generally) আমরা \(a_i=f(a_{i-1})\) ধরতে পারি যেখানে \(f(x)\) হচ্ছে একটি সুবিধাজনক বহুপদী। যেমন- উপরের প্রোগ্রামে \(f(x)=x^2+1\).

লক্ষ্য কর যে, \(\{a_i\}_{i = 0}^{\infty}\) ধারার প্রতিটি পদ শুধুমাত্র আগের পদের উপর নির্ভরশীল। তাই \(a_m \equiv a_n\pmod p\) একবার পাওয়া গেলে ধারাতে পূর্ববর্তী পদগুলো সাইক্লিকভাবে ঘুরে ফিরে আসতে থাকবে। অর্থাৎ,\(a_{m+i}\equiv a_{n+i}\pmod p\).

তবে এই সাইকেল \(a_0\) থেকে শুরু হতে হবে এমন কোন কথা নেই। যেমন- \(p=29\) এবং \(f(x)=x^2+1\) হলে, \(\pmod p\)-তে \(\{a_i\}_{i = 0}^{\infty}\) ধারাটি হয়

\(i\) \(0\) \(1\) \(2\) \(3\) \(4\) \(5\) \(6\) \(7\) \(8\) \(9\) \(10\) \(11\)
\(a_i\) \(1\) \(2\) \(5\) \(26\) \(10\) \(14\) \(23\) \(8\) \(7\) \(21\) \(\color{red}7\) \(\color{red}{21}\)

দেখতেই পাচ্ছ, \(a_0\)-র কনগ্রুয়েন্ট কোন পদ দ্বিতীয়বার পাওয়া যায়নি। তাই, প্রোগ্রাম ১-এ সবসময় \(a_0\) থেকে সাইকেল শুরু হবে ধরে নেওয়াটা ভুল ছিল।

এমন ধারাতে সাইকেল (অর্থাৎ \(\pmod p\)-তে কনগ্রুয়েন্ট দুটি পদ) নির্ণয় করতে আরেকটু বুদ্ধি খাটাতে হয়। আমি এখানে দুটি এলগোরিদমের কথা বলে দিচ্ছি। প্রথমটি ফ্লয়েডের এলগোরিদম, দ্বিতীয়টি ব্রেন্টের এলগোরিদম।

ফ্লয়েডের এলগোরিদম

মনে কর \(a_i\) ধারার সাইকেলের দৈর্ঘ্য \(l\). \(n\) যদি যথেষ্ট বড় হয়, তবে,\[a_n\equiv a_{n+l}\equiv a_{n+2l}\equiv\cdots\equiv a_{n+kl}\pmod p\]
আমরা যদি যথেষ্ট বড় কোন \(k\)-র জন্য \(n=kl\) নেই, তবে,\[a_n \equiv a_{n+kl}=a_{2kl}=a_{2n}\pmod p\]
অর্থাৎ, \(a_i\) ধারায় এমন অসীম সংখ্যক পদ \(a_n\) আছে যাদের জন্য \(a_n\equiv a_{2n}\pmod p\). সুতরাং \(\gcd(N, a_{2i}-a_i)\) নির্ণয় করে যেতে থাকলেই একটা সময় \(\pmod p\)-তে কনগ্রুয়েন্ট দুটি পদ পাওয়া যাবে। ফ্লয়েডের এলগোরিদম এই ধারণাটি ব্যবহার করে।

ফ্লয়েডের এলগোরিদমে একটি খরগোশ আর একটি কচ্ছপের মাঝে দৌড় প্রতিযোগিতার চলে। কচ্ছপটি ধারার একটি একটি পদে \(a_0, a_1, a_2,a_3,\ldots\) পর্যায়ক্রমে যেতে থাকে। একইসময়ে, খরগোশটি ধারার \(a_0, a_2, a_4, a_6,\ldots\) পদগুলোতে লাফিয়ে লাফিয়ে যেতে থাকে। আমরা খরগোশের অবস্থান এবং কচ্ছপের অবস্থানের পার্থক্যের সাথে \(N\)-এর গসাগু নির্ণয় করতে থাকি। যখনই গসাগু \(1\) এর চেয়ে বড় হয়ে যায়, এলগোরিদমটি টার্মিনেট করে।

def rhofloyd(N):
    #both hare and tortoise at a_0
    tortoise = hare = d = 1
    while d == 1:
        tortoise = f(tortoise) % N #tortoise steps once
        hare = f(f(hare)) % N #hare steps twice
        d = gcd(hare - tortoise, N)
    return d

ব্রেন্টের এলগোরিদম

ব্রেন্টের এলগোরিদমে অনেকগুলো রাউন্ডে খরগোশ আর কচ্ছপের দৌড় প্রতিযোগিতা চলে। প্রতিযোগিতার \(i\)-তম রাউন্ডে খরগোশ আর কচ্ছপ উভয়েই \(a_{2^i}\)-তম পদে অবস্থান করে। প্রতিযোগিতা শুরুর পর খরগোশ তার জায়গায় আরাম করে ঘুম দেয়, আর কচ্ছপটি টুক টুক করে একটি একটি পদ সামনে এগুতে থাকে। আমরা প্রতিবারই খরগোশের অবস্থান এবং কচ্ছপের অবস্থানের পার্থক্যের সাথে \(N\)-এর গসাগু \(d\) নির্ণয় করি। যখন কচ্ছপ খরগোশের চেয়ে \(2^i\) পদ সামনে এগিয়ে যায়, খরগোশের তড়াক করে জেগে ওঠে এবং সে এক লাফে কচ্ছপের অবস্থানে চলে আসে। এরপর প্রতিযোগিতার \(i+1\)-তম রাউন্ড শুরু হয়।

আগের মতই, \(d> 1\) হয়ে গেলে এলগোরিদমটি টার্মিনেট করবে।

লক্ষ্য কর যে, \(i\) এর মান বাড়ার সাথে সাথে \(2^{i}\) এবং \(2^{i+1}\)-এর মধ্যবর্তী পার্থক্যও বাড়তে থাকে। একটা সময় এই পার্থক্য \(\{a_i\}_{i = 0}^\infty\) ধারার সাইকেলের দৈর্ঘ্য \(l\) থেকে বড় হয়ে যায়। তখন কচ্ছপের কোন এক অবস্থানের জন্য খরগোশ ও কচ্ছপের অবস্থানের পার্থক্য হবে ঠিক \(l\)টি পদ। এই অবস্থাতেই আসলে এলগোরিদমটি টার্মিনেট করবে।

def rhobrent(N):
    #both hare and tortoise are at a_(2^0)
    #power is the nearest 2^i behind tortoise
    tortoise = hare = f(1)
    power, lead, d = 1, 0, 1
    while d == 1:
        if lead == power: #tortoise reaches 2^(i+1)-th term
            hare = tortoise #hare jumps to tortoise's position
            power *= 2 #update power
            lead = 0 #reset lead, since both hare and tortoise 
                     #are in the same position now
        tortoise = f(tortoise) % N #tortoise steps once
        lead += 1 #tortoise leads the race by one more step
        d = gcd(hare - tortoise, N)
    return d

ব্রেন্টের এনালাইসিস অনুসারে, ব্রেন্টের এলগোরিদম ফ্লয়েডের এলগোরিদম থেকে \(24\%\) দ্রুততর।

পূর্ণাঙ্গ প্রোগ্রাম

ব্রেন্টের এলগোরিদম দিয়ে যেহেতু সাইকেল শনাক্তকরণ সবচেয়ে দ্রুত করা যায়, তাই সেটি দিয়েই নিচে একটি পূর্ণাঙ্গ প্রোগ্রাম দেওয়া হল।

from fractions import gcd
from time import time

def f(x):
    return (x**2 + x + 1) % N

def rhobrent(N):
    tortoise = hare = f(1)
    power, lead, d = 1, 0, 1
    while abs(d) == 1:
        if lead == power:
            hare, lead = tortoise, 0
            power *= 2
        tortoise = f(tortoise)
        lead += 1
        d = gcd(tortoise - hare, N)
    return d

N = int(raw_input())
exec_time = time()
d = 1 if(-2 < N < 2) else rhobrent(N)
exec_time = time() - exec_time
print d, '*', N / d
print "Execution time: %.3f s" % exec_time
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iso646.h> //and

#define MAX 2147483647

long long f(long long x);
long long gcd(long long a, long long b);
long long rhobrent(long long N);

long long N;

int main(void){
    long long d;
    scanf("%lld", &N);
    clock_t exec_time = clock();
    d = (N < 2 and N > -2) ? 1 : rhobrent(N);
    exec_time = clock() - exec_time;
    double t = (double) exec_time / CLOCKS_PER_SEC;
    printf("%lld * %lld\n", d, N/d);
    printf("Execution time: %.3lf s\n", t);
    return 0;
}

long long f(long long x){
    if(x < MAX) 
        return (x * x + x + 1) % N;
    long long y = x, output = x + 1;
    while(y > 0){
        if(y % 2 == 1)
            output += x;
        x *= 2;
        y /= 2;
        output %= N;
        x %= N;
    }
    return output;
}

long long gcd(long long a, long long b){
    long long r;
    while(b != 0){
        r =  a % b;
        a = b;
        b = r;
    }
    return (a > 0) ? a : -a;
}

long long rhobrent(long long N){
    long long tortoise = f(1), hare = f(1), power = 1, lead = 0, d = 1;
    while(d == 1){
        if(lead == power){
            hare = tortoise;
            power *= 2;
            lead = 0;
        }
        tortoise = f(tortoise);
        lead++;
        d = gcd(N, tortoise - hare);
    }
    return d;
}

নোট:

  1. উপরের কোডে \(f(x)=x^2+x+1\) এবং ফাংশানের ভেতরেই \(N\) দিয়ে মডুলাসের কাজ শেষ করা হয়েছে।
  2. প্রায় সকল আধুনিক কম্পাইলারে long long int-এর ব্যাবধী \([-2^{63}, 2^{63})\). তাই সি প্রোগ্রামে \(f(x)\) ফাংশনটি ঠিকঠাকমত কাজ করার জন্য \[x^2+x+1\leq 2^{63}-1\Longrightarrow x<2^{31.5}-1\] হতে হবে। এজন্য \(x \ge 2^{31}\) -এর জন্য \(y = x\) নামের একটি নতুন ভেরিয়েবল নিয়ে এর প্রতিটি বিটের সাথে আলাদাভাবে \(x\)-এর গুণফল বের করে সেই সমষ্টির মডুলাস নেওয়া হয়েছে।
  3. \(\pmod N\) এবং \(\pmod p\)-তে \(N\)-এর সাইকেল একই হলে উপরের প্রোগ্রাম \(N\) কৃত্রিম হওয়া সত্বেও এর উৎপাদক খুঁজে পাবে না। এরকম হলে \(f(x)\) পলিনোমিয়ালটি পরিবর্তন করে আবার চেষ্টা করতে পার।

কমপ্লেক্সিটি

মনে কর, \(\{a_i\}_{i=0}^{\infty}\) একটি সত্যিকারে র‍্যান্ডম ধারা। জন্মদিনের সমস্যা অনুযায়ী, \(\pmod p\)-তে কনগ্রুয়েন্ট দুটি পদ পাওয়ার সম্ভাবনা \(99\%\) হতে হলে \(\sqrt{-2\times\ln(1-0.99)}\sqrt{p}\)-টি পদ নিতে হবে। অতএব, রো এলগোরিদমের কমপ্লেক্সিটি \(O(\sqrt p)\leq O\left(N^{\frac 1 4}\right)\). [অর্থাৎ \(N\) সংখ্যাটিতে \(k\)টি ডিজিট থাকলে রো এলগোরিদমের রানটাইম \(O\left(10^{\frac k 4}\right)\)]
গতপর্বের চেয়ে আরেকটু ভালো বাউন্ড, তাই না? পরবর্তী পর্বে আমরা জন পোলার্ডেরই আরেকটি এলগোরিদম দেখব, যেটির নাম \(p-1\) এলগোরিদম

পরিশিষ্ট

জন্মদিন সমস্যা

তোমার ফেসবুক ফ্রেন্ডলিস্টে নূন্যতম কতজন থাকলে একথা নিশ্চিত করে বলা যাবে যে অন্তত দুইজন ফ্রেন্ডের জন্মদিন একই তারিখে হওয়ার সম্ভাবনা \(99\%\)?

মনে কর, তোমার ফ্রেন্ডলিস্টে \(m\) জন ফ্রেন্ড আছে, এবং কোন ফ্রেন্ডের জন্মদিন ২৯ ফেব্রুয়ারি নয়। কোন একজন ফ্রেন্ডের জন্মদিন ৬ অক্টোবর হলে আর কোন ফ্রেন্ডের জন্মদিন ৬ অক্টোবর না হওয়ার সম্ভাবনা \(1-\frac {1}{365}\). আরেক ফ্রেন্ডের জন্মদিন মনে কর ৪ আগস্ট। সুতরাং, তৃতীয় কোন ফ্রেন্ডের জন্মদিন ৬ অক্টোবর বা ৪ আগস্ট না হওয়ার সম্ভাবনা \(1-\frac {2}{365}\). অতএব, \(m\) জন ফ্রেন্ডের ভিন্ন ভিন্ন দিনে জন্মদিন পড়ার সম্ভাবনা \[\left(1-\frac {1}{365}\right)\cdots\left(1-\frac {m-1}{365}\right)\]
তাহলে, অন্তত দুজন ফ্রেন্ডের জন্মদিন একই দিনে পড়ার সম্ভাবনা \[1 – \left(1-\frac {1}{365}\right)\cdots\left(1-\frac {m-1}{365}\right)\]
\(x\)-এর মান \(0\)-এর কাছাকাছি হলে আমরা টেইলরের সিরিজ থেকে \(1-x\approx e^{-x}\) লিখতে পারি। এভাবে উপরের সম্ভাবনাটিকে সরল করে লিখা যায় \[1-e^{-\frac {1}{365}}\cdot e^{-\frac {2}{365}}\cdots e^{-\frac {m-1}{365}}\]\[\approx 1-e^{-\frac{m^2}{2\times 365}}\]এখন \(1-e^{-\frac{m^2}{2\times 365}}\ge 0.99\) হতে হলে \[m\ge \sqrt{-2\times 365\ln(1-0.99)}\approx 58\] হতে হবে।

তোমার ফ্রেন্ডলিস্টে মাত্র \(58\) জন মানুষ থাকলেই তুমি \(99\%\) গ্যারান্টি দিয়ে বলতে পারবে যে অন্তত দুইজনের জন্মদিন একই তারিখে! এই বিখ্যাত সমস্যাটির নাম জন্মদিন সমস্যা

লক্ষ্য কর জন্মদিনের সমস্যার সমাধান থেকে এটা বলা যায় যে, \(0\) থেকে \(N-1\) এর মাঝে \(m\) সংখ্যা নিলে কোন একটি সংখ্যা অন্তত দুইবার নেওয়ার সম্ভাবনা \(1-e^{-\frac{m^2}{2N}}\).

ইন্টিজার ফ্যাক্টোরাইজেশন পর্ব ০

ইন্টিজার ফ্যাক্টোরাইজেশন: পর্ব ১ পোলার্ডের রো (rho) এলগোরিদম

আমরা কেন ইন্টিজার ফ্যাক্টোরাইজেশন করি

ইন্টেজার ফ্যাক্টোরাইজেশন অর্থ হচ্ছে একটা পূর্ণসংখ্যাকে উৎপাদকে বিশ্লেষণ করা। যেমন \(36 = 4\times 9\). এখানে \(4\) আর \(36\) উভয়েই \(36\)-এর উৎপাদক।

ছোটবেলায় আমাদের সবাই ইন্টেজার ফ্যাক্টোরাইজেশন করতাম। কেন জানো? পরীক্ষায় নম্বর পাওয়ার জন্য! প্রশ্নে একটা সংখ্যা দেওয়া থাকত আর আমরা দুই থেকে শুরু করে একটা একটা সংখ্যা দিয়ে প্রশ্নে দেওয়া সংখ্যাটাকে ভাগ দিতাম। যখন ভাগ যেত, তখন বোঝা যেত যে একটা উৎপাদক (বা গুণনীয়ক) পেয়ে গেছি। খুবই রুটিনমাফিক একটা কাজ, তাই না?

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

কিন্তু সমস্যা কি জানো? কম্পিউটার খুব বোকা। যদি আমি বলি, “কম্পিউটার, আমার একটা হিসেবে \(731\)-এর উৎপাদকে বিশ্লেষণ লাগবে। তুমি চট করে সেটা বের করে দাও তো দেখি!”, সে হা করে বসে থাকবে। কারণ সে তো আর জানে না কীভাবে উৎপাদকে বিশ্লেষণ করতে হয়!

কম্পিউটারকে দিয়ে উৎপাদকে বিশ্লেষণ করানোর জন্য তাকে তোমার প্রাইমারির বাচ্চাদের মত একটু একটু করে বুঝিয়ে বলতে হবে, “কম্পিউটার, \(2\) থেকে \(730\) পর্যন্ত প্রতিটি সংখ্যা দিয়ে \(731\)-কে ভাগ দাও। যদি কোনটা দিয়ে নিঃশেষে ভাগ যায়, তবে সেই সংখ্যা এবং ভাগফল আমাকে দেখাও।”

def factor(N):
    for d in range(2, abs(N) + 1):
        if N % d == 0: return d

N = int(raw_input())
d = 1 if(2 > N > -2) else factor(N)
print d, '*', N / d

কম্পিউটার যেহেতু বাংলা পারে না, তাই সে বোঝে এমন একটি ভাষা পাইথনে আমরা আমাদের কথাগুলো লিখেছি। এই কোডে একটি পূর্ণসংখ্যা \(N\)-কে ইনপুট হিসেবে দেওয়া হবে। আর কম্পিউটার সাথে সাথে \(N\)-কে উৎপাদকে বিশ্লেষণ করে খুশিমনে আমাদের জানিয়ে দেবে। যত বড় সংখ্যাই হোক না কেন, আমাদের ছেলেবেলায় শেখা নিয়ম দিয়ে তার উৎপাদক বের করা সম্ভব।

উপরের প্রোগ্রামে \(731\) ইনপুট দিলে কম্পিউটার আমাদের বলে দেবে যে \(731 = 17\times 43\).

এবার একটা কাজ কর। উপরের প্রোগ্রামটি চালিয়ে \(N = 18446744073709551619\) ইনপুট দাও। কী হল?

প্রোগ্রামটি আর থামছে না।

এর কারণ হচ্ছে উপরের প্রোগ্রামে কম্পিউটারকে \(2\) থেকে \(N-1\) পর্যন্ত সকল সংখ্যা দিয়েই \(N\)-কে ভাগ (প্রকৃতপক্ষে মডুলাস নির্ণয়) করতে হচ্ছে। কম্পিউটারের প্রতিটা ভাগ করতে কিছুটা সময় লাগে। তাই \(N\) যত বড় হবে, কম্পিউটারকে তত বেশি সংখ্যা দিয়ে ভাগ করতে হবে, এবং প্রোগ্রামের রান করতে সময় (রানটাইম) বেশি লাগবে। রানটাইম \(N\)-এর সাথে পাল্লা দিয়ে কত দ্রুত বাড়বে সেটার একটা ধারণাও আমরা পেতে পারি।

ধর \(N\) সংখ্যাটিতে \(k\) সংখ্যক ডিজিট আছে। আমরা আসন্নভাবে \(N\approx 10^k\) ধরতে পারি। যদি \(N\) একটি মৌলিক সংখ্যা হয়, তবে প্রোগ্রাম ১-এ \(N\)-কে \(2\) থেকে \(N-1\) পর্যন্ত সকল সংখ্যা দিয়েই ভাগ করা হবে। যদি প্রতিবার ভাগ করতে সর্বোচ্চ \(c\) পরিমাণ সময় লাগে, তবে উপরের প্রোগ্রামটি রান করতে সর্বোচ্চ \(Nc=10^{k}c\) সময় লাগবে। এর অর্থ হচ্ছে, ডিজিটের সংখ্যা বাড়ার সাথে সাথে উপরের প্রোগ্রামের রানটাইমও সূচকীয়ভাবে বৃদ্ধি পায়। [বা, বিগ O নোটেশনে উপরের প্রোগ্রামের রানটাইম \(O(10^{k})\)]

প্রোগ্রামিং-এ রানটাইম সূচকীয়ভাবে বাড়া খুবই দুঃখের একটি কথা। কারণ ইনপুটের একটুখানি পরিবর্তনে প্রোগ্রামের রানটাইমে রাতদিন পরিবর্তন হয়ে যেতে পারে।

মনে কর তোমার কাছে যদি কোন মহাক্ষমতাধর সুপার কম্পিউটার আছে যে \(200\) ডিজিটের একটা সংখ্যার উৎপাদকে বিশ্লেষণ প্রোগ্রাম ১ দিয়ে \(1\) সেকেন্ডে বের করতে পারে। তাহলে \(210\) ডিজিটের একটা সংখ্যার উৎপাদকে বিশ্লেষণ করতে কম্পিউটারটির সময় লাগবে \(10^{210-200}=10^{10}\) সেকেন্ড \(\approx 317\) বছর!

আমদের জীবনটা খুব ছোট, জানো? একটা প্রোগ্রামের আউটপুট দেখে যাওয়ার জন্য আমাদের \(317\) বছর বেঁচে থাকা সম্ভব না। তাই খুব ফাস্ট কোন এলগোরিদম দরকার।

প্রোগ্রাম ১-কেই অনেকখানি ফাস্ট বানানো যায় যদি আমরা \(N-1\) এর পরিবর্তে \(\sqrt{N}\) পর্যন্ত প্রতিটা সংখ্যা দিয়ে ভাগ দেই। কেননা প্রতিটি কৃত্রিম সংখ্যার \(\sqrt N\)-এর মাঝেই অন্তত একটা উৎপাদক থাকে। আর যদি উৎপাদক না পাওয়া যায়, তবে সংখ্যাটি প্রাইম। এই পরিবর্তনের ফলে আমাদের এলগোরিদমের রানটাইম হবে \(10^{\frac k 2}c\) [বা \(O\left(10^{\frac k 2}\right)\)]. কিন্তু এটাও যে সূচকীয় হারে বাড়ে!

এর থেকে ফাস্ট কি কোন এলগোরিদম নেই? উত্তরটা হচ্ছে, হ্যাঁ আছে। তবে সেটি জানতে হলে তোমার মডুলার এরিথমেটিক সম্পর্কে হালকা পাতলা ধারণা লাগবে।

যদি \(a\) এবং \(b\) কে \(n\) দিয়ে ভাগ করলে একই ভাগশেষ থাকে, তাহলে আমরা লিখি \(a \equiv b\pmod{n}\). এটাকে পড়া হয় \(a\) is congruent to \(b\) modulo \(n\). যেমন: \(57\equiv 112\pmod{55}\).

লক্ষ্য কর যে, যদি \(n\) দিয়ে \(a\)-কে ভাগ করলে \(r\) ভাগশেষ থাকে, তবে \(a\equiv r\pmod{n}\) লিখা যায়। যেমন: \(57\equiv 2\pmod{55}\).

যেকোন পূর্ণসংখ্যাকে যদি \(55\) দিয়ে ভাগ কর, তবে তুমি \(0\) থেকে \(54\) এর মাঝে কোন একটি ভাগশেষ পাবে। তাহলে, তুমি যদি অনেকগুলো র‍্যান্ডম পূর্ণসংখ্যার নাও, এদের মাঝে \(\pmod {55}\)-এ কনগ্রুয়েন্ট, অর্থাৎ \(55\) দিয়ে ভাগ করলে একই ভাগশেষ থাকে, এমন দুটি পূর্ণসংখ্যা পাওয়ার কিছুটা সম্ভাবনা থাকে, তাই না? যত বেশি সংখ্যা নেবে, এই সম্ভাবনাও তত বাড়বে।

আবার, একই সংখ্যাগুলির মাঝে \(\pmod {5}\)-এ কনগ্রুয়েন্ট দুটি সংখ্যা পাওয়ার সম্ভাবনাও থাকে। কিন্তু এই সম্ভাবনা \(\pmod{55}\)-এ কনগ্রুয়েন্ট হওয়ার সম্ভাবনার চেয়ে অনেক বেশি। কেননা, \(\pmod{5}\)-এ তো খালি \(0\) থেকে \(4\) পর্যন্ত ভাগশেষ আসতে পারে।

এই ধারণাকে ব্যবহার করে উৎপাদকে বিশ্লেষণের একটি চমৎকার এলগোরিদম রয়েছে, যার নাম পোলার্ডের রো(\(\rho\)) এলগোরিদম। পরবর্তী পর্বে এটি নিয়ে আলোচনা করব।

আমার প্রিয় স্বপ্নেরা

আমার প্রিয় স্বপ্নেরা!
রোজ বেড়ে ওঠো দেবদারুর শাখার মত।
তোমাদের প্রতীক্ষায় ক্লান্ত কবিতারা
ফিনিক্স পাখির মত বার বার জন্ম নিক
দুইশ ছয়টি হাড়ের এই কাঠামোতে।
একদিন ইকারাসের মত ডানা মেলে উড়ে যাব।
সত্যিই!