خوارزميات البحث عن عدد أولي

"أكبر عدد أولي هو ^32582657 -1 . وأؤكد بكل فخر أنني تذكرت جميع أرقامه ... بشكل ثنائي ".
كارل بوميرانس

يطلق على العدد الطبيعي أولي إذا كان له مقسومان مختلفان: واحد ونفسه. كانت مهمة العثور على الأعداد الأولية تطارد علماء الرياضيات لفترة طويلة جدًا. لفترة طويلة لم يكن لهذه المشكلة أي تطبيق عملي مباشر ، لكن كل شيء تغير مع ظهور تشفير المفتاح العام. تتناول هذه المقالة عدة طرق للبحث عن الأعداد الأولية ، سواء ذات الاهتمام الأكاديمي البحت أو المستخدمة اليوم في التشفير.

غربال إراتوستينس

غربال إراتوستين - خوارزمية اقترحها عالم الرياضيات اليوناني القديم إراتوستينس. تتيح لك هذه الطريقة العثور على جميع الأعداد الأولية أقل من رقم معين n . جوهر الأسلوب هو على النحو التالي. خذ مجموعة من الأرقام من 2 إلى ن . شطب جميع الأرقام قابلة للقسمة على 2 ، باستثناء 2. من المجموعة (نحذفها) ، سننتقل إلى الرقم "غير المحذوف" التالي - 3 ، ونشطب مرة أخرى كل ما هو قابل للقسمة على 3. نمر إلى الرقم المتبقي التالي - 5 ، وهكذا حتى نصل الى ن . بعد تنفيذ الخطوات أعلاه ، ستبقى الأرقام الأولية فقط في القائمة الأصلية.

الخوارزمية يمكن تحسينها قليلاً. بما أن أحد مقسومات الرقم المركب n إلزامي $$$\ leqslant \ sqrt {n}$ يمكن إيقاف الخوارزمية بعد حذف الأرقام التي يمكن تقسيمها $$$\ sqrt {n}$ .

شكل توضيحي لعملية الخوارزمية من ويكيبيديا:


تعقيد الخوارزمية هو $$$O (n \ log \ log n)$ في نفس الوقت ، لتخزين المعلومات حول الأرقام التي تم شطبها ، يجب توفره $$$O (n)$ الذاكرة.

هناك عدد من التحسينات لتقليل هذه المؤشرات. تتمثل الخدعة التي يطلق عليها " معاملات العجلة" في تضمين الأرقام الأصلية في القائمة الأصلية فقط وهي أعداد كبيرة من الجرائم ذات الأعداد الأولية القليلة (على سبيل المثال ، أقل من 30). من الناحية النظرية ، يقترح أن تأخذ الأولى البسيطة حتى حوالي $$$\ sqrt {\ log n}$ . هذا يقلل من تعقيد الخوارزمية في $$$\ log \ log n$ الوقت. بالإضافة إلى ذلك ، يتم استخدام تجزئة ما يسمى لتقليل استهلاك الذاكرة. تنقسم مجموعة الأرقام الأولية إلى مقاطع من الحجم $$$\ leqslant \ sqrt {n}$ ولكل قطعة ، يتم تطبيق غربال إراتوستين بشكل منفصل. يتم تقليل استهلاك الذاكرة ل $$$O (\ sqrt {n})$ .

اتكين غربال

اقترح Atkin و Bershtein خوارزمية أفضل لغربلة الأرقام المركبة ، وكان يطلق عليها Atkin Sieve . تعتمد هذه الطريقة على الخصائص الثلاثة التالية للأعداد الأولية.

الملكية 1

إذا كان n هو رقم موجب وليس مضاعفاً لمربع العدد الأولي ومثل هذا $$$n \ equiv 1 (\ mod 4)$ . ثم n أولي إذا وفقط عدد جذور المعادلة $$$4x ^ 2 + y ^ 2 = n$ الغريب.

الملكية 2

إذا كان n هو رقم موجب وليس مضاعفاً لمربع العدد الأولي ومثل هذا $$$n \ equiv 1 (\ mod 6)$ . ثم n أولي إذا وفقط عدد جذور المعادلة $$$3x ^ 2 + y ^ 2 = n$ الغريب.

الملكية 3

إذا كان n هو رقم موجب وليس مضاعفاً لمربع العدد الأولي ومثل هذا $$$n \ equiv 11 (\ mod 12)$ . ثم n أولي إذا وفقط عدد جذور المعادلة $$$3x ^ 2-y ^ 2 = n$ الغريب.

تم توفير دليل على هذه الخصائص في هذه المقالة .

في المرحلة الأولى من الخوارزمية ، يكون غربال Atkin عبارة عن صفيف A بحجم n مليء بالأصفار. لتحديد الأعداد الأولية ، كل شيء $$$x ، y <\ sqrt n$ . لكل هذا الزوج يتم حسابها $$$4x ^ 2 + y ^ 2$ . $$$3x ^ 2 + y ^ 2$ . $$$3x ^ 2-y ^ 2$ وقيمة عناصر الصفيف $$$A [4x ^ 2 + y ^ 2]$ . $$$A [3x ^ 2 + y ^ 2]$ . $$$A [3x ^ 2-y ^ 2]$ يزيد بمقدار واحد. في نهاية الخوارزمية ، تكون مؤشرات جميع عناصر الصفيف التي لها قيم فردية إما أرقام أولية أو مربعات لعدد أولي. في الخطوة الأخيرة من الخوارزمية ، يتم شطب مربعات الأرقام المتبقية في المجموعة.

يتبع من وصف الخوارزمية أن التعقيد الحسابي لمنخل Atkin واستهلاك الذاكرة $$$O (n)$ . عند استخدام معاملات العجلة وتقسيمها ، يتم تقليل تقدير التعقيد للخوارزمية إلى $$$O (n / \ log \ log n)$ ، واستهلاك الذاكرة يصل إلى $$$O (\ sqrt {n})$ .

أعداد مرسين واختبار لوقا ليمير

بطبيعة الحال ، مع مثل هذه المؤشرات من التعقيد ، لا يمكن استخدام غربال Atkin الأمثل للبحث عن أعداد كبيرة بالفعل. لحسن الحظ ، هناك اختبارات سريعة لمعرفة ما إذا كان عدد معين أولي. على عكس خوارزميات الغربال ، فإن مثل هذه الاختبارات ليست مصممة للبحث عن جميع الأعداد الأولية ، فهي فقط قادرة على معرفة بعض الاحتمالات فيما إذا كان عدد معين أولي.

إحدى طرق الاختبار هذه هي اختبار Luc-Lemer . هذا اختبار حاسم وغير مشروط للبساطة. هذا يعني أن اجتياز الاختبار يضمن بساطة الرقم. لسوء الحظ ، تم تصميم الاختبار فقط للأرقام من نوع خاص $$$2 ^ p-1$ حيث p رقم طبيعي. وتسمى هذه الأرقام أرقام مرسين.

يدعي اختبار Luke-Lemer أن عدد مرسين $$$M_p = 2 ^ p-1$ رئيس الوزراء إذا وفقط إذا كان رئيس الوزراء و $$$M_p$ تقسيم بالتساوي $$$(p-1)$ عضو في التسلسل $$$S_k دولا$ ضبط متكرر: $$$S_1 = 4 ، S_k = S_ {k-1} ^ 2-2$ إلى $$$ك> 1 دولا$ .

للحصول على الرقم $$$M_p$ ع طول بت التعقيد الحسابي للخوارزمية هو $$${\ displaystyle O (p ^ {3})}$ .

بسبب بساطة وحتمية الاختبار ، فإن الأعداد الأولية المعروفة هي أعداد مرسين. أكبر عدد أولي معروف اليوم هو $$$2 ^ {82،589،933} -1$ ، يتكون ترميزه العشري من 24،862،048 رقمًا. يمكنك معجب بهذا الجمال هنا .

نظرية فيرما واختبار ميلر رابين

لا يُعرف الكثير من أعداد مرسين الأولية ، لذا فإن تشفير المفتاح العام يتطلب طريقة مختلفة للبحث عن الأعداد الأولية. إحدى هذه الطرق هي اختبار بساطة فيرما . إنها مبنية على نظرية فيرما الصغيرة ، التي تنص على أنه إذا كانت n أولية ، فبالنسبة لأي n لا يقبل القسمة على n ، $$$a ^ {n-1} \ equiv 1 {\ pmod {n}}$ . يمكن العثور على دليل النظرية على ويكيبيديا .

اختبار بساطة فيرما هو اختبار احتمالي ، والذي يتكون من تعداد العديد من القيم إذا كان واحد منهم على الأقل يرضي عدم المساواة $$$a ^ {n-1} \ not \ equiv 1 \ pmod n$ ، ثم الرقم n مركب. خلاف ذلك ، ن هو على الارجح رئيس الوزراء. كلما زادت قيم المستخدم المستخدمة في الاختبار ، زاد احتمال أن n أولي.

لسوء الحظ ، هناك أرقام مركبة ن للمقارنة $$$a ^ {n-1} \ equiv 1 {\ pmod {n}}$ يحمل للجميع رئيس متبادل مع ن . وتسمى هذه الأرقام أرقام كارمايكل . تسمى الأرقام المركبة التي تنجح بنجاح في اختبار Fermat باسم Fermat-simple Fermat. عدد فيرمات البسيط الزائف لا حصر له ، وبالتالي فإن اختبار فيرما ليس الطريقة الأكثر موثوقية لتحديد الأعداد الأولية.

اختبار ميلر رابين

يمكن تحقيق نتائج أكثر موثوقية من خلال الجمع بين نظرية فيرمات الصغيرة وحقيقة أنه لا توجد جذور أخرى للمعادلة بالنسبة إلى برايم. $$$x ^ 2 \ equiv 1 \ pmod p$ باستثناء 1 و -1. يعدد اختبار Miller-Rabin العديد من قيم a ويتحقق من صحة الشروط التالية.

اسمحوا ع أن يكون رئيس الوزراء و $$$p-1 = 2 ^ sd$ ، إذن لأي شرط واحد على الأقل صحيح:

1. $$$a ^ {d} \ equiv \ pm1 {\ pmod {p}}$
2. يوجد عدد صحيح من هذا القبيل $$$a ^ {2 ^ {r} d} \ equiv -1 {\ pmod {p}}$

بواسطة نظرية فيرما $$$a ^ {p-1} \ equiv1 \ pmod p$ و منذ $$$p-1 = 2 ^ sd$ من خاصية جذور المعادلة $$$x ^ 2 \ equiv 1 \ pmod p$ يترتب على ذلك أنه إذا وجدنا أن أحد الشروط غير راضٍ ، فإن p هو رقم مركب. إذا تم استيفاء أحد الشروط ، فسيتم استدعاء الرقم ( أ ) كشاهد بساطة الرقم n وفقًا لميلر ، وربما يكون الرقم n نفسه أوليًا.

كلما زاد عدد الشهود على البساطة ، زاد احتمال أن يكون n أولي. وفقًا لنظرية رابين ، فإن احتمال أن يشهد رقمًا عشوائيًا ( أ) أن يشهد بساطة الرقم المركب تقريبًا $$ .

لذلك ، إذا تحققنا من الأرقام العشوائية أ ، فإن احتمال أخذ الرقم المركب أولي $$$\ approx (1/4) ^ k$ .

تعقيد الخوارزمية $$$O (k \ log ^ 3p)$ حيث k هو عدد الشيكات.

نظرًا لسرعته ودقته العالية ، يتم استخدام اختبار Miller-Rabin على نطاق واسع في البحث عن الأعداد الأولية. تستخدم العديد من مكتبات التشفير الحديثة هذا الاختبار فقط عند التحقق من الأرقام الكبيرة للتأكد من بساطتها ، وكما أظهر مارتن ألبريشت في عمله ، فإن هذا لا يكفي دائمًا.

لقد كان قادرًا على إنشاء مثل هذه الأرقام المركبة التي نجحت في اختبار البساطة في المكتبات OpenSSL و CryptLib و JavaScript Big Number والعديد غيرها.

Luke Test and Baillie - PSW Test

لتجنب الثغرات الأمنية ذات الصلة بالمواقف التي يتم فيها تقديم رقم مركب تم إنشاؤه بواسطة المهاجم كقائم أولية ، يقترح Martin Albrecht استخدام اختبار Baillie - PSW . على الرغم من أن اختبار Baillie - PSW احتمالي ، حتى الآن ، لم يتم العثور على أرقام مركبة نجحت في اجتياز هذا الاختبار. للعثور على هذا العدد في عام 1980 ، وعد مؤلفو الخوارزمية بمكافأة قدرها 30 دولارًا. لم يتم المطالبة بالجائزة.

فحص عدد من الباحثين جميع الأرقام حتى $$$2 ^ {64}$ وليس رقم مركب واحد اجتاز اختبار Baillie - PSW. لذلك ، للأرقام أقل $$$2 ^ {64}$ يعتبر الاختبار حتمية.

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

اختبار لوقا الزائف القوي

تسلسل لوك هي أزواج من تسلسل تكرار $$$\ {U_ {n} (P، Q) \}، \ {V_ {n} (P، Q) \}$ وصفها التعبيرات:

$$

$${\ displaystyle U_ {0} (P، Q) = 0 ، \ quad U_ {1} (P، Q) = 1 ، \ quad U_ {n + 2} (P، Q) = P \ cdot U_ {n +1} (P، Q) -Q \ cdot U_ {n} (P، Q)، \، n \ geq 0}$$

$$

$${\ displaystyle V_ {0} (P، Q) = 2 ، \ quad V_ {1} (P، Q) = P ، \ quad V_ {n + 2} (P، Q) = P \ cdot V_ {n +1} (P، Q) -Q \ cdot V_ {n} (P، Q)، \، n \ geq 0}$$

سمح $$$U_n (P ، Q)$ و $$$V_n (P ، Q)$ هي متواليات Lucas ، حيث تفي الأعداد الصحيحة P و Q بالشرط $$${\ displaystyle D = P ^ {2} -4Q \ neq 0}$

نحسب رمز جاكوبي : $$$\ left ({\ frac {D} {p}} \ right) = \ varepsilon$ .

البحث عن مثل هذه r ، s التي المساواة $$$n-ε = 2 ^ rs$

بالنسبة لـ prime n ، يحمل أحد الشروط التالية:

1. ن الانقسامات $$$U_s$
2. ن الانقسامات $$$V_ {2 ^ js}$ لبعض ي <ص

خلاف ذلك ، n مركب.

احتمال أن يتجاوز العدد المركب n بنجاح اختبار Luc لزوج معين من المعلمات P، Q لا يتجاوز 4/15. لذلك ، بعد تطبيق أوقات الاختبار k ، يكون هذا الاحتمال $$$(4/15) ^ k$ .

ينتج عن اختبارات Miller-Rabin و Luke مجموعات منفصلة من الأرقام الزائفة البسيطة ، على التوالي ، إذا نجح الرقم p في الاختبارين ، فهو بسيط. بناءً على هذه الخاصية ، يعتمد اختبار Baillie - PSW.

استنتاج

اعتمادًا على المهمة ، يمكن استخدام طرق مختلفة للعثور على الأعداد الأولية. على سبيل المثال ، عند البحث عن أعداد كبيرة من Mersenne ، أولاً ، باستخدام غربال Eratosthenes أو Atkin ، يتم تحديد قائمة من الأعداد الأولية بحدود معينة ، لنفترض أنه يصل إلى $$$10 ^ 8$ . ثم ، لكل رقم p من القائمة ، باستخدام اختبار Luc-Lemer ، يتم فحصه للتأكد من بساطته $$$M_p = 2 ^ p-1$ .

لإنشاء رقم أولي كبير لأغراض التشفير ، يتم تحديد رقم عشوائي a والتحقق منه بواسطة اختبار Miller-Rabin أو Baillie - PSW الأكثر موثوقية. وفقًا لنظرية توزيع الأعداد الأولية ، بالنسبة للرقم الذي تم اختياره عشوائيًا من 1 إلى n ، تكون فرصة الأعداد الأولية متساوية تقريبًا $$${\ frac {1} {\ ln n}}$ . لذلك ، للعثور على عدد أولي من 1024 بت ، يكفي فرز حوالي ألف خيار.

مصادر PS

يمكن عرض تنفيذ جميع الخوارزميات الموصوفة على Go على GitHub .