تحليل بولارد p−1
يجد عاملًا لعدد مركب عندما يكون لأحد عوامله الأولية p عدد p − 1 ناعم: العدد 1003 بحدّ 16 ينقسم إلى 17 و59، لأن 17 − 1 يساوي 16. وإن لم يظهر شيء فارفع الحد. مجانًا في متصفحك.
- مجاني
- يعمل في متصفحك
- دون تسجيل
- بياناتك لا تغادر جهازك
شغّل الأداة مجانًا
مثال محلول
- N
- 1003
- الحد
- 16
- العامل
- 17
- العامل المرافق
- 59
- الأساس
- 2
طريقة بولارد p ناقص واحد خوارزمية كلاسيكية لتحليل الأعداد الصحيحة تجد عاملاً غير تافه لمقياس مركّب n عندما يمتلك عامل أولي واحد على الأقل p من عوامل n خاصية أن p ناقص واحد ناعم بالنسبة لحد B مختار — أي أن كل قوة أولية في تحليل p ناقص واحد لا تتجاوز B. يلتقي طلاب نظرية الأعداد الابتدائية ومتنافسو CTF ومتعلمو التشفير بهذه الخوارزمية حين يدرسون لماذا يجب أن تتجنب مقاييس RSA الأعداد الأولية ذات دوال أويلر الناعمة. تنفّذ هذه القدرة بحثاً حتمياً للمرحلة الأولى من بولارد p−1: تبني جداء قوى أولية حتى B، وترفع أساساً صغيراً إلى ذلك الأس بمقياس n، وتعيد القاسم المشترك الأكبر لتلك القوة ناقص واحد مع n كلما كان الناتج عاملاً حقيقياً.
كيف يجد بولارد p−1 عاملاً من p−1 ناعم
ثبّت عدداً صحيحاً مركّباً n وحدّ نعومة موجباً B. ملاحظة بولارد بسيطة: إذا كان p قاسماً أولياً لـ n وكانت كل قوة أولية تقسم p ناقص واحد لا تتجاوز B، فإن المضاعف المشترك الأصغر للأعداد من واحد إلى B يكون مضاعفاً لـ p ناقص واحد. وبموجب مبرهنة فيرما الصغيرة، أي أساس a أولي نسبياً مع p يحقق أن a مرفوعاً إلى p ناقص واحد يطابق واحداً بمقياس p، وبالتالي a مرفوعاً إلى ذلك المضاعف الكبير يطابق واحداً بمقياس p أيضاً.
حساب القوة نفسها بمقياس n وأخذ القاسم المشترك الأكبر للنتيجة ناقص واحد مع n غالباً ما يعطي p أو عاملاً غير تافه آخر. عملياً لا تبني التنفيذ المضاعف المشترك الأصغر كاملاً صراحة؛ بل تغربل الأعداد الأولية حتى B، ولكل أولي q ترفع المُراكِم الجاري إلى أعلى قوة لـ q لا تتجاوز B، كله بمقياس n. بعد كل خطوة قوة أولية تقيّم القاسم المشترك الأكبر للمُراكِم ناقص واحد مع n.
أي قاسم وسيط غير تافه يُعاد فوراً. إذا انهار القاسم إلى n نفسه، يحاول مسار استعادة أدق على أسس أصغر عزل عامل أولي واحد قبل التخلي عن ذلك الأساس. تُجرَّب عدة أسس صغيرة حتى لا تخفي مراتب سيئة الحظ للأساس اثنين عاملاً كان ليكون B-ناعماً.
الطريقة ليست خوارزمية تحليل كاملة: تعيد عاملاً غير تافه والعامل المرافق المطابق. من يحتاج تحليلاً أولياً كاملاً يمكنه تغذية كل قطعة مركّبة لأداة تحليل أولي أو رفع B وإعادة التشغيل. النجاح مضمون فقط في إعداد p−1 الناعم؛ العوامل الأولية الكبيرة لـ p ناقص واحد تفرض B أكبر أو خوارزمية أخرى مثل طريقة المنحنيات الإهليلجية أو الغربال التربيعي.
أين تجني واجهة عامل p−1 قيمتها
تستخدم مقررات التشفير بولارد p−1 لإظهار لماذا الأعداد الأولية ذات السوابق الناعمة خطرة في توليد معاملات RSA وDiffie–Hellman؛ وأداة حية تقبل n وB تمكّن المدرّس من إظهار انقسام في الصف دون كتابة الرفع المعياري يدوياً. تحتاج منصات CTF والواجبات أوراكل حتمياً إما يعيد عاملاً موثّقاً لشبه أولي كلاسيكي مثل ألف وثلاثة بحد ستة عشر، أو يرفض الحدود الصغيرة جداً حتى يقيّم المصححون العوامل الصحيحة وتعليلات الفشل الصحيحة معاً. يمكن لمهندسي الأمن الذين يدققون توليد مفاتيح قديماً غربلة مقاييس مرشحة بحثاً عن عوامل بـ p−1 ناعم قبل أن تصل إلى الإنتاج.
مؤلفو الدفاتر الذين لديهم مسبقاً روتين تحليل أولي عام ما زالوا يستفيدون من نقطة نهاية p−1 صريحة عندما يكون الدرس هو الطريقة نفسها لا قائمة العوامل الكاملة. أبقِ n ضمن حد الأرقام، واختر B كبيراً بما يكفي لتغطية أكبر عامل أولي لـ p ناقص واحد لبعض أولي p يقسم n، فتحصل على عوامل قابلة للتكرار للتعليم وكتابات CTF والتدقيق الخفيف دون نصب حزمة جبر حاسوبي كاملة.
حالات الاستخدام
سلامة المقاييس المرشحة
غربل مقاييس RSA أو Diffie–Hellman المرشحة بحثاً عن عوامل بـ p−1 ناعم قبل النشر دون استيراد حزمة تحليل كاملة.
الأسئلة الشائعة
ما طريقة تحليل بولارد p−1؟
خوارزمية مرحلة أولى تحسب قوة ناعمة كبيرة لأساس بمقياس n وتعيد gcd(a^M − 1, n). تجد عاملاً p عندما يكون p−1 ناعماً بالنسبة للحد B المختار.
متى تفشل الطريقة في إيجاد عامل؟
عندما يكون n أولياً، أو لكل عامل أولي p من n قاسم أولي لـ p−1 أكبر من B، أو عندما لا تعزل الاستعادة عاملاً حقيقياً.
هل تعيد التحليل الأولي الكامل؟
لا. تعيد عاملاً غير تافه والعامل المرافق n/factor (الأصغر أولاً). حلّل كل قطعة بأداة تحليل أولي إن احتجت كل القوى الأولية.
ما الحد الذي ينبغي أن أختاره؟
ابدأ بحد صغير وارفعه إن لم يظهر أي عامل. يجب أن يغطي الحد كل قوة أولية في p − 1 لعامل أولي واحد على الأقل من عددك. يُقبل أي عدد صحيح من 2 إلى 50,000.
كم خانة يمكن أن يحتوي العدد؟
حتى 18 خانة، مكتوبًا كعدد صحيح بلا فواصل أو مسافات. الأعداد الزوجية تعيد العامل 2 فورًا، أما العدد الأولي فلا يعطي عاملًا لأنه لا يوجد ما يُقسم.
أدوات ذات صلة
للمطوّرين — الوصول عبر API
كل ما في هذه الصفحة متاح برمجيًا. هذا القسم موجّه للفرق التقنية التي تريد ربط الأداة بأنظمتها الخاصة؛ بقية المستخدمين يمكنهم استخدام الأداة أعلاه مباشرة دون الحاجة لقراءة ما يلي.
الـEndpoint
صادِق على طلبك بترويسة Bearer، وأرسل طلب POST واحدًا لتدخل مهمتك قائمة التنفيذ فورًا؛ ثم تستلم النتيجة عبر webhook أو رابط موقّع.
استدعِ الخدمة من بيئتك
curl -X POST https://api.kit.forhosting.com/numth/pollard-p-minus-one \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":"1003","bound":16}'const res = await fetch("https://api.kit.forhosting.com/numth/pollard-p-minus-one", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": "1003",
"bound": 16
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/pollard-p-minus-one",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": "1003",
"bound": 16
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/pollard-p-minus-one", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":"1003","bound":16}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":"1003","bound":16}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/pollard-p-minus-one", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)مثال على الطلب
{
"n": "1003",
"bound": 16
}مثال على الاستجابة
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.pollard_p_minus_one",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}الواجهة غير متزامنة: تستلم task_id فور الإرسال، ويمكنك الاستعلام عن الحالة بمعدل طلب واحد في الثانية.
الأسعار
السعر معلن كما تراه: لا tokens ولا نظام نقاط؛ وإن فشلت المهمة فلن تُحاسَب عليها.
الأخطاء
| HTTP | الرمز | المعنى |
|---|---|---|
401 | unauthorized | مفتاح الوصول مفقود أو غير صالح؛ تحقق من ترويسة Bearer في طلبك. |
402 | insufficient_balance | رصيدك لا يكفي لتنفيذ هذه المهمة؛ أعد شحن الرصيد ثم أعد المحاولة. |
404 | unknown_type | نوع المهمة المطلوب غير موجود في الكتالوج — راجع الاسم المرسل في الطلب. |
429 | rate_limited | تجاوزت الحد المسموح من الطلبات؛ انتظر قليلًا ثم أعد المحاولة. |
ملاحظات تقنية
عندما يكون الحد ضيقاً جداً، أو يكون n أولياً، أو تقاوم كل العوامل الطريقة، تفشل المهمة بـ invalid_input بدلاً من اختراع عامل. يشترك المسار المجاني في المتصفح وواجهة API المدفوعة في وحدة BigInt نقية واحدة، فلا تختلف فحوصات الواجبات والأتمتة أبداً.
عقد الإدخال وشكل الاستجابة وأوضاع الفشل
الحقل n هو العدد الصحيح المراد تحليله: عدد صحيح آمن في JavaScript أو سلسلة عشرية بسيطة بلا فواصل أو مسافات أو ترميز علمي، بحد أدنى رقمين وبحد أقصى ثمانية عشر رقماً عشرياً. مثال: n يساوي ألف وثلاثة وbound يساوي ستة عشر يعيد العامل سبعة عشر والعامل المرافق تسعة وخمسين لأن سبعة عشر ناقص واحد يساوي ستة عشر وهو ستة عشر-ناعم. إذا كان n زوجياً يُعاد العامل اثنان فوراً دون بحث كامل للمرحلة الأولى. أرسل كائن JSON بطريقة POST بحقلين إلزاميين. الحقل bound هو حد النعومة B، عدد صحيح من اثنين إلى خمسين ألفاً؛ وتُقبل الأسماء البديلة B وb وsmoothness_bound وsmoothness للراحة. عند النجاح يعيد الجسم n كسلسلة عشرية وbound كعدد صحيح، ثم يبلغ عن factor وcofactor كسلسلتين عشريتين مع أصغر عامل أولاً، والأساس الذي أنتج العامل، وmethod مضبوطاً على السلسلة الثابتة pollard_p_minus_one. الحقول الناقصة وغير الصحيحة والأعداد n دون اثنين وbound خارج النطاق المنشور وn أطول من ثمانية عشر رقماً تفشل بـ invalid_input ولا تُفوتر. عندما تنهي المرحلة الأولى كل الأسس دون عامل حقيقي — مثلاً n أولي، أو كل عامل أولي p له قاسم أولي لـ p ناقص واحد أكبر من B — يفشل المعالج أيضاً بـ invalid_input ورسالة بأن بولارد p−1 لم يجد عاملاً غير تافه ضمن الحد، داعياً إلى رفع B أو تجربة n آخر. هذا الفشل تصميم منتج مقصود: نجاح صامت بعامل واحد أو n سيكسر الأتمتة التي تعامل أي استجابة مئتين على أنها انقسام حقيقي.
أين تجني واجهة عامل p−1 قيمتها
ولأن التنفيذ parse نقي من المستوى A، تكلف كل مكالمة ناجحة السعر الأساسي المنشور $0.002 بلا رموز نموذج ولا شبكة صادرة، والتحقق الفاشل لا يستهلك الرصيد أبداً.
حالات التكامل
عروض صفية لـ p−1 الناعم
أظهر كيف ينتج حد B يغطي p−1 لعامل أولي في شبه أولي انقساماً غير تافه، بأمثلة كلاسيكية مثل n=1003 مع B=16.
مصححات CTF وواجبات آلية
قيّم تمارين بولارد p−1 بأوراكل حتمي يعيد العامل عندما يكفي B وinvalid_input عندما يكون الحد ضيقاً جداً.
أسئلة تقنية
ما المدخلات التي تطلبها API؟
الحقل n (عدد صحيح ≥ 2 و≤ 18 رقماً) والحقل bound (نعومة B من 2 إلى 50000). تشمل الأسماء البديلة number/value لـ n وB/smoothness_bound لـ bound.
كم تكلفة تحليل بولارد p−1؟
أداة المتصفح مجانية. طلبات API تستخدم رصيد KIT المدفوع مسبقاً بسعر $0.002 لكل مكالمة ناجحة؛ الإدخال غير الصالح والحدود الفاشلة لا تُفوتر.