جافا BigInteger الأعداد الأولية

Question

أنا أحاول أن توليد عشوائي عدد الوزراء من نوع BigInteger ، وهذا هو بين min و max القيمة التي كنت العرض.

أنا على بينة من BigInteger.probablePrime(الباحث bitlength عشوائية), ولكن أنا لا أعرف كيف أو حتى إذا كان bitlength يترجم ماكس/دقيقة قيمة أنتج رئيس الوزراء.

شكرا Steven1350

Answer 1

وBigInteger.probablePrime(bitLength, random) يجري لإرجاع (المحتمل) مقتبل طول الشيء المحدد. أن يترجم إلى قيمة الحد الأقصى من 2 ^ bitlength - 1 والحد الأدنى من 2 ^ (bitlength - 1). بقدر ما أنا أكره ذلك كإجابة، هو على الأرجح أفضل رهان إلا إذا كنت تريد أن تبدأ الخوض في نظرية الأعداد.

وماذا عملتم القيام به هو معرفة أطوال بت هذا النطاق الخاص بك يدعو، ثم تمريرها إلى probablePrime() حتى نعود رئيس الوزراء هذا في نطاق الحق.

Answer 2

jprete الجواب لا بأس إذا كانت نسبة ماكس/دقيقة ليست قريبة من 1.

إذا كان لديك نطاق ضيق ، وأفضل رهان هو على الارجح فقط أن تفعل شيئا من هذا القبيل ما يلي:

// this is pseudocode:
//
// round min down to multiple of 6, max up to multiple of 6
min6 = floor(min/6);
max6 = ceil(max/6);
maybePrimeModuli = [1,5];
do 
{
   b = generateRandom(maybePrimeModuli.length);
   // generate a random offset modulo 6 which could be prime
   x = 6*(min6 + generateRandom(max6-min6)) + b;
   // generate a random number which is congruent to b modulo 6
   // from 6*min6 to 6*max6-1
   // (of the form 6k+1 or 6k+5)

   // the other choices 6k, 6k+2, 6k+3, 6k+4 are composite 
} while not isProbablePrime(x);

على كثافة الأعداد الأولية مرتفع إلى حد ما عموما ، انها في الاساس 1 في log(x) ، لذلك يجب أن لا تضطر إلى تكرار كثير من الأحيان للعثور على عدد الوزراء.(فقط كمثال:عن أرقام حول 10²³, واحد في كل 52 الصحيحه على متوسط عدد الوزراء.رمز أعلاه يزعج فقط مع 2 من أصل كل 6 أرقام, إذا كنت في نهاية المطاف حلقات متوسطه 17 مرة عن أرقام حول 10²³.)

فقط تأكد من أن لديك جيدة بريماليتي اختبار و جافا BigInteger واحد.

باعتبارها ممارسة للقارئ ، تمديد الدالة أعلاه لذلك بتصفية المزيد من الأرقام المركبة في وقت مبكر باستخدام 30k + x (modulo 30, هناك 22 المعاملات التي هي دائما المركب فقط 8 المتبقية يمكن أن يكون رئيس الوزراء) ، أو 210 ألف + x.

تحرير:انظر أيضا الولايات المتحدة للبراءات #7149763 (OMFG!!!)