خوارزمية Pohlig -Hellman لحساب اللوغاريتمات المنفصلة

Question

أنا أعمل على ترميز خوارزمية Pohlig-Hellman ، لكنني أواجه مشكلة أفهم الخطوات في الخوارزمية بناءً على تعريف الخوارزمية.

الذهاب عن طريق ويكي خوارزمية:

أعلم أن الجزء الأول 1) هو حساب العامل الرئيسي لـ P -1 - وهو أمر جيد.

ومع ذلك ، لست متأكدًا مما أحتاج إلى القيام به في الخطوات 2) حيث تقوم بحساب الآثار المشتركة:

Let x2 = c0 + c1(2). 
125(180/2) = 12590 1 mod (181) so c0 = 0.
125(180/4) = 12545 1 mod (181) so c1 = 0.
Thus, x2 = 0 + 0 = 0.

و 3) وضع المعاملات معا وحل في نظرية الباقي الصينية.

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

ملاحظة: لقد فعلت الكثير من البحث عن هذا وقرأت S. Pohlig و M. Hellman (1978). "خوارزمية محسّنة لحساب اللوغاريتمات على GF (P) وأهميتها التشفير ولكنها لا تزال غير منطقية بالنسبة لي.

شكرا لك مقدما

تحديث: كيف يبقى Q (125) ثابتًا في هذا المثال.

حيث يبدو كما هو الحال في هذا المثال وكأنه يحسب كل من كل الوقت.

لأكون أكثر تحديداً ، لا أفهم كيف يتم حساب ما يلي: الآن قسّم 7531 على A^C0 للحصول على7531(a^-2) = 6735 mod p.

Answer 1

لنبدأ بالفكرة الرئيسية وراء Pohlig-Hellman. افترض أننا تم إعطاؤنا Y و G و P وأننا نريد العثور على X ، من هذا القبيل

y == g^x (وزارة الدفاع P).

(أنا أستخدم == للإشارة إلى علاقة معادلة). لتبسيط الأشياء ، أفترض أيضًا أن ترتيب G هو p-1 ، أي أصغر k إيجابي مع 1 == g^ك (وزارة الدفاع P) هو k = p-1.

طريقة غير فعالة للعثور على X ، ستكون ببساطة تجربة جميع القيم في النطاق 1 .. P-1. أفضل إلى حد ما هو "خطوة عملاقة خطوة الأطفال" الطريقة التي تتطلب o (p^0.5) عمليات حسابية. كلتا الطريقتين بطيئة للغاية بالنسبة للكبير. يعد Pohlig-Hellman تحسنًا كبيرًا عندما يكون لـ P-1 العديد من العوامل. أي افترض ذلك

p-1 = nr

ثم ما يقترحه Pohlig و Hellman هو حل المعادلة

ذ^ن == (ز^ن)^ض(وزارة الدفاع P).

إذا أخذنا لوغاريتمات على أساس G على كلا الجانبين ، فهذا هو نفسه مثل

سجل_ز(y) == سجل_ز(ذ^ن) == NZ (MOD P-1).

يمكن تقسيم n ، العطاء

سجل_ز(y) == z (mod r).

وبالتالي x == z (mod r).

هذا تحسن ، حيث يتعين علينا فقط البحث في نطاق 0 .. R-1 لحل z. ومرة أخرى ، يمكن استخدام "خطوة العملاقة للأطفال" لتحسين البحث عن z. من الواضح أن القيام بذلك مرة واحدة ليس حلاً كاملاً بعد. أي على المرء أن يكرر الخوارزمية أعلاه لكل عامل رئيسي R من P-1 ثم استخدام نظرية الباقي الصينية للعثور على X من الحلول الجزئية. هذا يعمل بشكل جيد إذا كان P-1 مربعًا مجانيًا.

إذا كان P-1 قابلاً للقسمة بواسطة قوة أولية ، فيمكن استخدام فكرة متماثلة. على سبيل المثال ، لنفترض أن p-1 = mq^ك. في الخطوة الأولى ، نحسب z بحيث x == z (mod q) كما هو موضح أعلاه. بعد ذلك نريد تمديد هذا إلى حل x == z '(mod q²). على سبيل المثال إذا p-1 = mq² ثم هذا يعني أنه يتعين علينا العثور على z 'من هذا القبيل

ذ^م == (ز^م)^{z '} (وزارة الدفاع P).

نظرًا لأننا نعلم بالفعل أن z '== z (mod q) ، يجب أن يكون z' في المجموعة {z ، z+q ، z+2q ، ... ، z+(q-1) q}. مرة أخرى ، يمكننا إما إجراء بحث شامل عن Z 'أو تحسين البحث باستخدام "خطوة عملاقة للأطفال". يتم تكرار هذه الخطوة لكل أسس Q ، وهذا هو من معرفة x mod q^أنا نحن نشتق بشكل متكرر x mod q^أنا+1.

Answer 2

أنا أرفعها بنفسي الآن (جافا). أنا أستخدم Pollard-Rho للعثور على العوامل الأولية الصغيرة لـ P-1. ثم باستخدام Pohlig-Hellman لحل مفتاح DSA الخاص. y = g^x. أواجه نفس المشكلة..

تحديث: "لكي أكون أكثر تحديداً ، لا أفهم كيف يتم حساب ما يلي: الآن قسّم 7531 على A^C0 للحصول على 7531 (A^-2) = 6735 mod p."

إذا وجدت modinverse لـ^c0 ، فسيكون منطقيًا

يعتبر