توليد الأعداد الأولية الكبيرة حقا

Question

ألعب وتحاول كتابة تنفيذ RSA. المشكلة هي أنني عالقة في توليد الأرقام الرئيسية الضخمة التي تشارك في توليد زوج رئيسي. هل يمكن لشخص ما أن يشيرني إلى طريقة سريعة لتوليد الأعداد الأولية الضخمة / الأعداد الأولية المحتملة؟

Answer 1

أنت لا تولد أرقام رئيسية بالضبط. يمكنك إنشاء عدد فردي كبير عشوائيا، ثم اختبار ما إذا كان هذا الرقم رئيسا، إن لم يكن إنشاء واحد آخر عشوائيا. هناك بعض القوانين ذات الأرقام الرئيسية التي تنص أساسا على أن احتمالاتك من "ضرب" من خلال المحاولات العشوائية هي (2 / LN N)

على سبيل المثال، إذا كنت تريد رقم رئيس عشوائي 512 بت، فستجد واحدا من 2/512 * LN (2)) تقريبا 1 من كل 177 من الأرقام التي تجربتها ستكون رئيسا.

هناك طرق متعددة لاختبار ما إذا كان عدد رئيسي، واحد جيد هو "اختبار ميلر رابين" كما هو مذكور في إجابة أخرى على هذا السؤال.

أيضا، يحتوي Openssl على فائدة لطيفة لاختبار الأعداد الأولية:

$ openssl prime 119054759245460753
1A6F7AC39A53511 is not prime

Answer 2

نلقي نظرة على كيف TrueCrypt. يفعل ذلك. أيضا، إلقاء نظرة على رابين ميلر لاختبار السريعة الكبرى الكبيرة.

Answer 3

لم تذكر اللغة التي تستخدمها. البعض لديه طريقة للقيام بهذا المدمج. على سبيل المثال، في Java هذا سهل مثل الاتصال nextprobableprime () على biginteger.

Answer 4

الجواب السابق غير صحيح: 2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 = 509 * 59.

أعتقد أن الملصق يسيطر على الإثبات (الحقيقي) على وجود عدد لا يحصى من الأرقام الأولية.

Answer 5

Mono لديه فئة Biginteger هذا مصدر مفتوح مثل Java. يمكنك إلقاء نظرة على تلك. ربما تكون محمولة :) g'luck

Answer 6

هناك خوارزمية بسبب U. Maurer التي تنشئ بشكل عشوائي (على النقيض من الأعداد الأولية المحتملة للغاية) التي تم توزيعها بشكل موزعة بشكل موحد تقريبا على مجموعة من الأعداد الأولية لحجم خاص. لدي تطبيق بيثون له فعالة إلى حد ما في:http://s13.zetaboards.com/crypto/topic/7234475/1/