বিগ ইন্টিজার ৩

সম্ভাব্য-মৌলিক সংখ্যা
আমাদের অনেক সময় প্রাইম নাম্বার বের করার প্রয়োজন হতে পারে। বিশেষ করে ক্রিপ্টোগ্রাফীর জন্য প্রাইম নাম্বার জেনারেট করা অনেক জরুরি। একটি বিগ-ইন্টিজার সম্ভাব্য প্রাইম নাম্বার কি না তাও আমরা বের করতে পারি। এজন্য BigInteger ক্লাসে isProbablePrime() মেথড আছে। মেথডটিতে probabilistic primality টেস্টের জন্য Miller–Rabin অ্যালগরিদম ব্যবহার করা হয়েছে। মেথডটি প্যারামিটারে certainty হিসেবে একটি ইন্টিজার ভ্যালু নিয়ে থাকে এবং একটি বুলিয়ান ডাটা রিটার্ন করে। certainty দিয়ে অসম্ভাব্যতার হার বের করা হয়। তারপর তা থেকে সম্ভাব্যতার হার বের করা হয়। সম্ভাব্যতার হার বের করা হয় (1 – 0.5certainty) এভাবে। কোনো একটি সংখ্যা প্রাইম নাম্বার হবার সম্ভাব্যতা যদি এই মানকে অতিক্রম করে তাহলে মেথড টি true রিটার্ন করে, অন্যথায় false রিটার্ন করে। অর্থাৎ certainty এর মান যত বড় হবে, সম্ভাব্যতার হার তত বাড়বে। আবার অন্য দিকে সম্ভাব্যতার হার যত বাড়বে, প্রোগ্রামের এক্সিকিউশন টাইম ততো বেশি লাগবে। তাই এটা ব্যবহারকারীর উপর নির্ভর করে যে সে কতটুকু সময়ের মধ্যে কত সম্ভাব্যতার প্রাইম নাম্বার চায়।
কোন একটি সংখ্যা n, certainty c-এর সাপেক্ষে প্রাইম কি না, বের করতে হলে আমাদের লিখতে হবে –
boolean flag = n.isProbablePrime(c);

আবার কোনো একটি সংখ্যার পরবর্তি কোন সংখ্যাটি একটি সম্ভাব্য প্রাইম, তা বের করার জন্য বিগ ইন্টিজারে আছে nextProbablePrime() মেথড। মেথডটি একটি সম্ভাব্য প্রাইম নাম্বার রিটার্ন করে এবং রিটার্ন করা নাম্বারটি একটি কম্পোজিট নাম্বার হবার সম্ভাব্যতা থাকে 2-100 এর কম। কোনো একটি সংখ্যা n-এর পরবর্তি সম্ভাব্য প্রাইম সংখ্যাটি বের করতে হলে আমাদের লিখতে হবে-
BigInteger ans = n .nextProbablePrime();

আমাদের অনেক সময় র‍্যান্ডম প্রাইম নাম্বারের দরকার হতে পারে। বিগ ইন্টিজারে র‍্যান্ডম ভাবেও সম্ভাব্য প্রাইম নাম্বার জেনারেট করা যায়। এজন্য বিগ ইন্টিজারে probablePrime() মেথড আছে। মেথডটি প্যারামিটারে bitLength হিসেবে একটি ইন্টিজার এবং rnd হিসেবে একটি র‍্যান্ডম ডাটা নিয়ে থাকে। মেথডটির রিটার্ন করা নাম্বারটি এই bitLength-সংখ্যক বিটের হবে। মেথডটি কল করার সময় এর মান সব সময় 2 বা তার বেশি হতে হবে। আর rnd হচ্ছে একটি র‍্যান্ডম বিট সোর্স, একটি সম্ভাব্য প্রাইম নাম্বার রিটার্ন করার জন্য যার primality টেস্ট করা হয়। মেথডটি একটি সম্ভাব্য প্রাইম নাম্বার রিটার্ন করে এবং রিটার্ন করা নাম্বারটি একটি কম্পোজিট নাম্বার হবার সম্ভাব্যতা থাকে 2^-100 এর কম। এখন আমাদের যদি n সংখ্যক বিটের একটি র‍্যান্ডম সম্ভাব্য প্রাইম নাম্বার বের করতে হয়, তাহলে আমাদের লিখতে হবে –
Random rnd = new Random();
BigInteger ans =  BigInteger.probablePrime(n, rnd);

Facebook Comments

Leave a Reply