🔢 mathematics

Ours go to 211: Euler pseudoprimes to 47 prime bases (from Carmichael numbers)

تصنف هذه الورقة أعداد كارمايكل لتطوير خوارزمية سريعة لتوليد الأعداد الزائفة الأولية لـ "أويلر" المركبة، مما أدى في النهاية إلى اكتشاف مثال قياسي يحطم الأرقام القياسية يجتاز اختبار "سولوفاي-ستراسن" لأول 47 أساساً أولياً حتى الرقم 211.

المؤلفون الأصليون: Alejandra Alcantarilla Sánchez, Jolijn Cottaar, Tanja Lange, Benne de Weger

نُشر 2026-02-26

📖 4 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Alejandra Alcantarilla Sánchez, Jolijn Cottaar, Tanja Lange, Benne de Weger

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل أنك حارس أمن في بنك عالي التأمين (نظام كمبيوتر يستخدم التشفير مثل RSA). مهمتك هي التحقق مما إذا كان الزائر الذي يدعي أنه "عدد أولي" (رقم خاص وغير قابل للتجزئة وضروري للأمن) يقول الحقيقة حقاً.

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

المشكلة: المزورون المحترفون

اكتشف هؤلاء المؤلفون، وهم فريق من علماء الرياضيات، "المزور المحترف" الأسمى. أرادوا إيجاد عدد مركب يمكنه خداع الاختبار الأمني لأكبر عدد ممكن من الرموز (القواعد).

لقد اكتشفوا أن أفضل المزورين يأتون من عائلة محددة من الأعداد تسمى أعداد كارمايكل. هذه الأعداد مخادعة للغاية لدرجة أنها تجتاز "اختبار فيرما" الأساسي لكل الرموز الممكنة. لكن المؤلفين أرادوا الذهاب إلى أبعد من ذلك؛ أرادوا أعداداً تجتاز "اختبار أويلر" الأكثر تقدماً للعديد من الرمود المحددة.

الاستراتيجية: بناء "مزور خارق"

بدلاً من البحث عن هذه الأعداد واحداً تلو الآخر (وهو ما يشبه البحث عن إبرة في كومة قش)، أدرك المؤلفون أنه يمكنهم بناءها.

تخيل أنك تبني قلعة من قطع الليغو (Lego):

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

التشبيه: حفلة "المنتحلين"

تخيل حفلة حيث يحاول الجميع التظاهر بأنهم نوع معين من كبار الشخصيات (VIP) (أي عدد أولي).

الأشخاص العاديون (الأعداد المركبة): يتم كشفهم فوراً عند طرح سؤال بسيط عليهم.
أعداد كارمايل: هم ممثلون جيدون. يمكنهم الإجابة على أي سؤال تقريباً بشكل صحيح.
هدف المؤلفين: أرادوا إيجاد الممثل الذي يمكنه الإجابة على كل الأسئلة بشكل صحيح، حتى أصعب الأسئلة التي يطرحها كبار الشخصيات الـ 47.

أدرك المؤلفون أنك إذا أخذت ممثلين جيدين في الإجابة على الأسئلة من 1 إلى 37، و"زوجتهما" (ضربتهما في بعضهما)، فإن "طفلهما" (العدد الجديد) من المرجح أن يكون جيداً في الإجابة على الأسئلة من 1 إلى 40 أو 41. ومن خلال اختيار أي الممثلين سيتم تزويجهم بعناية، خلقوا سلالة من المنتحلين الذين أصبحوا أفضل وأفضل في الكذب.

النتيجة: المنتحل الأسمى

باستخدام طريقتهم، وجد الفريق عدداً مخادعاً للغاية لدرجة أنه اجتاز الاختبار الأمني لأول 47 قاعدة أولية.

لوضع هذا في المنظور:

الاختبار يتحقق مما إذا كان العدد أولياً عبر طرح أسئلة بناءً على الأعداد 2، 3، 5، 7، 11، 13، إلخ.
العدد الذي وجدوه نجح في خداع الاختبار لجميع هذه القواعد، وصولاً إلى العدد الأولي رقم 47، وهو 211.

هذا العدد هو "عدد مركب" (يمكن تقسيمه)، لكنه مصمم بدقة متناهية لدرجة أنه يبدو تماماً مثل العدد الأولي للاختبارات القياسية المستخدمة في التشفير. لقد صمد أمام 47 جولة من الاستجواب دون أن يخطئ.

لماذا يهم هذا؟

قد تسأل نفسك، "لماذا نريد إيجاد أعداد مزيفة؟"

الأمن: يساعدنا ذلك في فهم مدى قوة تشفيرنا حقاً. إذا تمكن المتسللون من إنشاء هذه "المزورات الخارقة"، فقد يتمكنون من خداع الأنظمة لقبول مفاتيح مزيفة، مما يؤدي لكسر الأمن.
الرياضيات: يوضح لنا هذا حدود اختباراتنا. فهو يثبت أنه بينما الاختبارات الاحتمالية (الاختبارات التي تتحقق من قواعد عشوائية قليلة) آمنة عادةً، إلا أنها ليست مثالية.
عامل "الحظ": تشير الورقة البحثية إلى أن اختبار "سولوفاي-ستراسن" لديه فرصة بنسبة 50% لكشف الكاذب في المرة الواحدة، بينما اختبار "ميلر-رابين" لديه فرصة بنسبة 75%. كان عدد المؤلفين جيداً جداً لدرجة أنه نجا من 47 جولة من رمي العملة بنسبة 50/50، وهو أمر نادر جداً من الناحية الإحصائية (مثل رمي العملة وظهور "الوجه" 47 مرة متتالية).

الملخص

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

إليك ملخص تقني مفصل للورقة البحثية بعنوان "أعدادنا تصل إلى 211: الأعداد الأولية الزائفة لأويلر إلى 47 أساساً أولياً".

1. بيان المشكلة

تتناول الورقة البحثية تحدي بناء الأعداد الأولية الزائفة لأويلر (Euler pseudoprimes) التي تصمد أمام اختبار سولوفاي-ستراسن (Solovay-Strassen) لعدد كبير من الأسس الأولية المتتالية.

السياق: تعتمد أنظمة التشفير بالمفتاح العام (مثل RSA) على توليد أعداد أولية كبيرة. وبما أن اختبارات الأولية الحتمية مكلفة حاسوبياً، تُستخدم اختبارات احتمالية مثل سولوفاي-ستراسن أو ميلر-رابين.
التهديد: إذا تمكن خصم من تقديم عدد مركب (عدد زائف) يجتاز هذه الاختبارات للعديد من الأسس، فيمكنه اختراق النظام.
الهدف: يهدف المؤلفون إلى إيجاد أعداد مركبة $n$ تحقق معيار أويلر $\left(\frac{a}{n}\right) \equiv a^{(n-1)/2} \pmod n$ لأكبر عدد ممكن من الأسس الأولية المتتالية بدءاً من 2.
المقارنة: بينما يكون احتمال الفشل في اختبار ميلر-رابين بحد أقصى $1/4$ لكل أساس، فإن احتمال الفشل في سولوفاي-ستراسن هو $1/2$ كحد أقصى. يسعى المؤلفون إلى دفع حدود عدد الأسس التي يمكن للعدد المركب أن "يخدعها" في اختبار سولوفاي-ستراسن.

2. المنهجية

يستخدم المؤلفون نهجاً متعدد المراحل يجمع بين التصنيف النظري، والتصفية، والضرب التكراري.

أ. تصنيف أعداد كارمايكل (Carmichael Numbers)

يحدد المؤلفون أعداد كارمايكل باعتبارها المرشح الأساسي للأعداد الأولية الزائفة لأويلر لأنها أعداد أولية زائفة لجميع الأسس المغايرة لـ $n$ . ويقدمون نظام تصنيف يعتمد على دالة كارمايكل لاندا $\lambda(n)$ والمؤشر (index) $i(n) = (n-1)/\lambda(n)$ :

الفئة (أ): $i(n)$ زوجي. تمتلك هذه الأعداد أكبر عدد ممكن من الكاذبين لأويلر ( $\frac{1}{2}\phi(n)$ ). جميع الكاذبين لديهم رمز جاكوبي (Jacobi symbol) بقيمة $+1$ .
الفئة (ب): $i(n)$ فردي. وتتفرع إلى B1 و B2 بناءً على التقييم الـ 2-آدي (2-adic valuation) للعوامل الأولية. بشكل عام، تحتوي الفئة (ب) على عدد أقل من الكاذبين لأويلر مقارنة بالفئة (أ).
الرؤية الجوهرية: لتعظيم عدد الأسس الناجية، يركز المؤلفون بشكل شبه حصري على أعداد كارمايكل من الفئة (أ).

ب. استراتيجية الضرب

تعتمد الخوارزمية الجوهرية على الخاصية الضربية لرمز جاكوبي.

الأعداد الزائفة الذرية (Atomic Pseudoprimes): يبدأ المؤلفون بأعداد كارمايكل "ذرية" (تلك التي لا تتكون من حاصل ضرب أعداد كارمايكل أخرى) تصمد حتى أساس معين $a$ (تحديداً $a \ge 37$ ) ولا تمتلك عوامل أولية صغيرة (أصغر عامل $> 150$ ).
البناء التكراري: يقومون بضرب عددين من الأعداد الأولية الزائفة لأويلر، $n_1$ و $n_2$ ، لإنشاء عدد مركب أكبر $n = n_1 n_2$ .
هيئة "نفس الأساس" (The "Same Base" Heuristic): يثبت المؤلفون (التمهيد 13) أنه إذا كان كل من $n_1$ $n_{1}$ و $n_2$ $n_{2}$ ينتميان إلى الفئة (أ) ويصمدان حتى نفس الأساس الأولي $a$ $a$ ، فإن ناتجهما $n$ $n$ (إذا ظل عدداً من كارمايكل في الفئة أ) سيصمد تلقائياً حتى الأساس الأولي التالي $b$ $b$ .
- التعليل: بالنسبة للأسس $\le a$ ، يكون لـ $n_1$ و $n_2$ رمز جاكوبي بقيمة $+1$ ، لذا يكون حاصل ضربهما $+1$ . بالنسبة للأساس التالي $b$ ، يكون لكل من $n_1$ و $n_2$ رمز جاكوبي بقيمة $-1 $(لأنهما يفشلان عند$ b $بشكل فردي)، لذا يكون حاصل ضربهما$ (-1) \times (-1) = +1$، مما يسمح للعدد المركب بالنجاح.
التصفية: لضمان الكفاءة والصحة، تقوم الخوارزمية بتصفية المدخلات لضمان:
1. أن كلا العاملين في الفئة (أ).
2. أن يحقق حاصل الضرب الشروط اللازمة للبقاء في الفئة (أ) (بناءً على التقييمات الـ 2-آدية لـ $n-1$ و $\lambda(n)$ ).
3. أن يكون حاصل الضرب خالياً من المربعات (شرط لأعداد كارمايكل).
4. أن يكون أصغر عامل أولي كبيراً بما يكفي لتجنب الفشل الفوري عند الأسس الصغيرة.

ج. تنفيذ الخوارزمية

طور المؤلفون الخوارزمية 1، والتي:

تأخذ مدخلين من المجموعات $epsp_{N_1}(a)$ و $epsp_{N_2}(a)$ (مجموعات الأعداد الزائفة التي تصمد حتى الأساس $a$ ).
تتحقق من شرط التقييم الـ 2-آدي للتنبؤ ما إذا كان حاصل الضرب سيكون من الفئة (أ).
تتحقق من أن حاصل الضرب هو عدد من كارمايكل ( $\lambda(n) | n-1$ ).
تتحقق من رمز جاكوبي للأس الأولي التالي لتحديد حد النجاح الجديد.
تكرر هذه العملية لبناء أعداد أكبر (على سبيل المثال، $epsp_4$ ، $epsp_8$ ، $epsp_{16}$ ).

3. المساهمات الرئيسية

التصنيف النظري: تصنيف دقيق لأعداد كارمايكل إلى الفئات (أ)، (ب1)، و(ب2)، مع تقديم أعداد دقيقة للكاذبين لأويلر لكل فئة. يثبت هذا أن الفئة (أ) هي الهدف الأمثل لبناء أعداد زائفة قوية.
خوارزمية البناء: خوارزمية تكرارية سريعة تضرب الأعداد الأولية الزائفة لأويلر الموجودة لتوليد أعداد أكبر، مستفيدة من خاصية "السالب المزدوج" لرموز جاكوبي لتوسيع نطاق الأسس الناجية.
النتائج المحطمة للأرقام القياسية: بناء عدد أولي زائف لأويلر يصمد أمام أول 47 أساساً أولياً (حتى 211).
التحليل الإحصائي: إحصائيات شاملة حول توزيع هذه الأعداد، بما في ذلك فئات بقاياها بمقياس 120 (تظهر انحيازاً قوياً نحو $n \equiv 1 \pmod{120}$ ) وخصائص قابلية القسمة لـ $n-1$ .

4. النتائج

الرقم القياسي: وجد المؤلفون عدداً مركباً يتكون من 1230 بت يصمد أمام اختبار سولوفاي-ستراسن لجميع الأسس الأولية من 2 حتى 211.
- وهذا يقابل أول 47 أساساً أولياً.
- العدد هو حاصل ضرب عدة أعداد كارمايكل أصغر تم بناؤها عبر خوارزميتهم.
الأرقام القياسية المتوسطة:
- نواتج ضرب عددين من الأعداد الذرية ( $epsp_2$ ) وصلت إلى الأساس 139.
- نواتج ضرب 4 أعداد ذرية ( $epsp_4$ ) وصلت إلى الأساس 191.
- نواتج ضرب 8 أعداد ذرية ( $epsp_8$ ) وصلت إلى الأساس 199.
تحليل الفشل: لاحظ المؤلفون أنه مع زيادة عدد العوامل، تزدัง احتمالية أن يكون حاصل الضرب غير خالٍ من المربعات بشكل كبير بسبب العوامل الأولية المشتركة في أعداد كارمايكل الذرية الأساسية. وقد حد هذا قدرتهم على بناء أعداد أكبر (مثل $epsp_{32}$ ) دون العثين على مدخلات ذرية جديدة.
اكتشاف بديل: تقدم الورقة باختصار أعداد "سوفي جيرمينوس" الزائفة (حاصل ضرب $p$ و $2p-1$ حيث كلاهما أولي) كفئة ثانوية من الأعداد ذات الأعداد الكبيرة من الكاذبين لأويلر ( $\phi(n)/4$ )، رغم أنها لم تحقق نتائج أفضل من نواتج الفئة (أ) من أعداد كارمايكل في هذه الدراسة.

5. الأهمية

الآثار التشفيرية: يوضح هذا العمل أنه يمكن خداع اختبارات الأولية الاحتمالية، وتحديداً سولوفاي-ستراسن، بواسطة أعداد مركبة مبنية بعناية لعدد كبير من الأسس. وبينما يُفضل ميلر-رابين عموماً بسبب معدل فشله الأقل ( $1/4$ مقابل $1/2$ )، إلا أن هذا البحث يسلط الضوء على الحدود النظرية للاختبارات الاحتمالية في ظل ظروف معادية.
الكفاءة الخوارزمية: توفر الورقة مخططاً لتوليد أعداد زائفة "صعبة" بكفاءة. إن استراتيجية ضرب الأعداد التي تفشل عند نفس الأساس لإنشاء عدد ينجح عند ذلك الأساس هي وسيلة فعالة لبناء أمثلة مضادة لاختبارات الأولية.
الرؤية الرياضية: يوفر تصنيف أعداد كارمايكل حسب فردية مؤشرها والتقييمات الـ 2-آدية رؤى هيكلية جديدة حول توزيع الكاذبين لأويلر، مما يؤكد أن أعداد الفئة (أ) هي المرشحات "الأفضل" لهذا الضعف التشفيري المحدد.

باخت-صار، نجحت الورقة في دفع حدود الأعداد الأولية الزائفة لأويلر المعروفة إلى 47 أساساً من خلال الجمع بين التصنيف النظري وخوارزمية الضرب التكراري، مما يثبت أنه يمكن هندسة الأعداد المركبة لتمثيل الأعداد الأولية بدقة عالية لنطاق كبير من الأسس.