صعوبة في فهم خطوات قليلة في الدليل: "The Class $ \ Mathscr {H} _ {P و M} $ من وظائف التجزئة هي عالمية"

Question

كنت أذهب من خلال إدخال النص إلى الخوارزميات بواسطة cormen et. آل. حيث صادفت مقتطفات التالية فيما يتعلق بالإثبات المذكور والخطوات التي شعرت بها صعوبة ملحوظ مع $ \ dagger $ $ \ dagger \ dagger $ على التوالي.

تصميم فئة عالمية من وظائف التجزئة

$ P $ هو رقم رئيسي كبير بما يكفي بحيث يكون كل مفتاح $ K $ في النطاق $ 0 $ إلى $ P - 1 $ ، شامل. دع $ z_p $ تشير إلى مجموعة $ \ {0، 1، ...، P - 1 \} $ ودع $ z_p ^ * $ تشير إلى مجموعة $ \ {1، 2، ...، P - 1 \} $ . لأن حجم الكون من المفاتيح أكبر من عدد فتحات $ M $ في جدول التجزئة، لدينا $ p> m $ .

نحن الآن نحدد وظيفة التجزئة $ h_ {a، b} $ لأي $ a \ in z_p ^ * $ وأي $ b \ in z_p $ :

$ h_ {a، b}= ((a.k + b) \ mod p) \ mod m $ .

عائلة جميع وظائف هذه الهجاء:

$$ \ mathscr {h} _ {p، m}={h_ {a، b}: a \ in z_p ^ *، b \ in z_p \} $ $

---

theorem: الفئة $ \ mathscr {h} _ {p، m} $ من وظائف التجزئة هي عالمية.

---

دليل:

النظر في مفتاحين متميزين $ k $ و $ l $ من $ z_p $ ، بحيث $ k \ neq l $ . للحصول على وظيفة تجزئة معينة $ h_ {a، b} $ نترك

$$ R= (AK + B) \ MOD P $$ ،

$$ S= (Al + B) \ MOD P $$ .

نلاحظ أولا أن $ r \ neq s $ . لماذا ا؟ لاحظ أن

$$ R - S= A (K - L) (\ MOD P) $ .

يتبع ذلك $ Г \ Neq S $ لأن $ p $ هو رئيس الوزراء وكلاهما $ $ $ و $ (k - l) $ غير صفري modulo $ P $ ، وبالتالي يجب أن يكون منتجاتهم أيضا غير صفري Modulo $ P $

لذلك، أثناء حساب أي $ h_ {a، b} $ في $ \ mathscr {h} _ {P، M} $ ، مدخلات متميزة $ k $ و $ L $ الخريطة القيم المميزة $ r $ و $ s $ modulo $ p $ ؛ لا توجد تصادم حتى الآن في "مستوى وزارة الدفاع P". علاوة على ذلك، كل من $ p (p - 1) $ الخيارات للزوج $ ( أ، ب) $ مع $ а \ neq 0 $ عائدات مختلفة الزوج الناتج $ (r، s ) $ مع $ r \ neq s $ ، نظرا لأننا يمكن أن نحل ل $ $ $ و $ B $ معطى $ r $ و $ S $ $ ^ \ dagger $ :

$$ A= ((R - S) ((K - L) ^ {- 1} \ Mod P)) \ MOD P $$ / ص>

$$ B= (R - AK) \ MOD P $$ ،

حيث $ ((k - l) ^ {- 1} \ mod p) $ يدل على عكس الضرب الفريد المضاعف، modulo p، من $ k - l $ . نظرا لوجود فقط $ p (p - 1) $ pairs ممكن $ (r، s) $ مع $ г \ NEQ S $ ، هناك مراسلات فردية بين أزواج $ (a، b) $ < / span> مع $ a \ neq 0 $ والأزواج $ (r، s) $ مع $ r \ neq s $ . وبالتالي، لأي زوج معين من المدخلات $ k $ و $ l $ ، إذا اخترنا $ (a، b) $ بشكل موحد عشوائيا من $ z_p ^ * \ times z_p $ ، الزوج الناتج $ (r، s) $ من المرجح أن يكون أي زوج من القيم المميزة modulo p.

ثم يتبع ذلك احتمال أن مفاتيح مفاتيح مميزة $ k $

ND $ L $ collide يساوي احتمال أن $ r \ equiv s (\ mod m) $ عندما $ r $ and $ S $ يتم اختيارها بشكل عشوائي كقيم مميزة لمضود $ P $ . للحصول على قيمة معينة من $ r $ ، من $ p - 1 $ ممكن القيم المتبقية ل $ S $ ، وعدد القيم $ S $ مثل هذا $ S \ NEQ R $ و $ s \ equib r (\ mod m) $ هو على الأكثر $ ^ {\ dagger \ dagger} $

$$ \ lceil P / m \ rceil - 1 <(p + m - 1) / m) - 1 $ $$= (P-1) / M $$ .

الاحتمال أن $ s $ clipides مع $ r $ عند انخفاض معدل modulo $ M $ هو في معظم $ ((P - l) / m) / (p - 1)= 1 / m $ .

لذلك، لأي زوج من القيم المميزة $ k، l \ in z_p $ ،

$$ pr \ {h_ {a، b} (k)= h_ {a، b} (l) \} \ leq 1 / m $

بحيث $ \ mathscr {h} _ {p، m} $ هو في الواقع عالمي.

---

شكوك:

لم أستطع فهم العبارات التالية في الدليل:

$ \ dagger $ : كل من $ p (p - 1) $ خيارات الزوج $ (a، b) $ مع $ а \ neq 0 $ غلة مختلفة الزوج الناتج $ (r، s) $ مع $ r \ neq s $ ، لأننا نستطيع حلها $ $ و $ B $ معطى $ r $ < / span> و $ S $

لماذا، "يمكننا حل ل $ $ و $ B $ معطى $ r $ و $ S $ " $ \ implies $ "كل من $ p (p - 1) $ الخيارات للزوج $ (a، b) $ مع $ а \ Neq 0 $ عائدات مختلفة زوج ناتج $ (r، s) $ مع $ Г \ NEQ S $ "

---

$ \ dagger \ dagger $ : للحصول على قيمة معينة من $ r $ ، من $ p - 1 $ ممكن القيم المتبقية مقابل $ S $ ، عدد القيم $ S $ مثل $ s \ neq r $ and $ s \ EquiV R (\ MOD M) $ هو على الأكثر $ \ lceil p / m \ rceil - 1 $ .

كيف نحصل على مصطلح $ \ lceil p / m \ rceil - 1 $ ؟

Answer 1

نريد أن نظهر أنه في حالة $ k_1 \ neq k_2 \ in \ mathbb {z} _p $ ثم

$ \ pr \ limits _ {(a، b) \ in \ mathbb {z} _p ^ * \ times \ mathbb {z} _p} [AK_1 + B \ equiV AK_2 + B \ PMOD M] \ Le \ Frac {1} {m} $ .

حيث يتم تسبيل كل من الجمع والضرب في $ \ mathbb {z} _p $ .

نبدأ بإظهار أنه في حالة $ a \ sim u (z_p ^ *) $ و $ b \ sim u (z_p) $ إذن لجميع $ k_1 \ neq k_2 \ in \ mathbb {z} _p $ ، $ (AK_1 + B، AK_2 + B) $ يتم توزيعها بشكل موحد عبر $ \ {(x، y) \ in \ mathbb {z} _p ^ 2 | X \ NEQ Y \} $ (IE $ h (k_1) $ و $ h (k_2) $ موحدة بشكل مشترك فوق أزواج مع إدخالات مختلفة، حيث توجد العشوائية أكثر من اختيار $ H $ ). هذا فوري من حقيقة أنه لكل $ (c_1، c_2) \ in \ mathbb {z} _p ^ 2 $ مع $ c_1 \ Neq c_2 $ ، نظام المعادلات الخطية التالية:

$ \ ابدأ {align *} & AK_1 + B= C_1 \\ & AK_2 + B= C_2 \ نهاية {محاذاة *} $

لديه حل فريد من نوعه عبر المتغيرات $ (a، b) \ in z_p ^ * \ times \ mathbb {z} _p $ . طرح المعادلة الثانية من أول عوائد $ a (k_1-k_2)= c_1-c_2 $ ، منذ $ k_1-k_2 دولار $ غير صفري، يمكننا أن نضاعف كلا الجانبين من قبل عكسها والحصول على $ a= (k_1-k_2) ^ {- 1} (c_1-c_2) $ وبعد إذا $ c_1 \ neq c_2 $ ، فهذا هو حل غير صفري ل $ $ ، ويمكننا استخراج $ B $ من أي من المعادلات. وبالتالي، لكل زوج $ (c_1، c_2) $ مع $ c_1 \ neq c_2 $ هناك فريدة $ (a، b) \ in z_p ^ * \ times \ mathbb {z} _p $ مثل هذا $ \ big (big ( H_ {A، B} (k_1)، h_ {a، b} (k_2) \ big)= (c_1، c_2) $ . هذا يستقر سؤالك الأول.

الآن، تقسيم $ \ mathbb {z} _p $ في $ \ lceil p / m \ rceil $ الدلاء، $ b_1، ...، b_ {l=lceil p / m \ rceil} $ كما يلي: $ b_1={0،1، ...، M-1 \}، b_2={m، m + 1، ...، 2m-1 \} $ ، ...، < Span Class="حاوية الرياضيات"> $ b_l={m \ lloroor p / m \ rfloor، m \ lceil p / m \ rceil + 1، ...، P-1 \} $ . لاحظ أن كل دلو ما عدا الأخير هو ذو حجم $ M $ ، ولا توجد عنصرين في نفس الدلو المعادلة المعادلة المعدلة $ م $ . نستنتج أن عدد أزواج مختلفة في $ \ {(x، y) \ in \ mathbb {z} _p ^ 2 | X \ NEQ Y \} $ التي هي ما يعادلها modulo $ m $ هو على الأكثر $ p (\ lceil P / M \ RCEIL-1) $ ، منذ ذلك بعد اختيار العنصر الأول، تركت مع $ \ lceil p / m \ rceil-1 $ العناصر للاختيار من بينها (يجب عليك اختيار دلو مختلف ويوفر كل دلو على الأكثر مرشحا واحدا). أذكر أن $ \ big (h_ {a، b} (k_1)، h_ {a، b} (k_2) \ big) \ sim u (\ {(x، y) \ في \ mathbb {z} _p ^ 2 | x \ neq y \}) $ ، حتى نستنتج أخيرا:

$ \ pr \ londits _ {(a، b) \ in \ mathbb {z} _p ^ * \ times \ mathbb {z} _p} \ left [h_ {a، ب} (k_1)= h_ {a و b} (k_2) \ pmod m \ righer]=frac {p (\ lceil p / m \ rceil-1)} {p (p-1)} \ le \ frac {1} {m} $

لاحظ أن السماح $ $ لاتخاذ القيمة $ 0 $ فقط يجعل تحليلنا أسهل الآن $ \ big (h (k_1)، h (k_2) \ big) $ هو موحدة مشتركة عبر $ \ mathbb { z}} _p ^ $ ، ولكن هناك احتمال إضافي ل $ \ frac {1} {p} $ that $ A= 0 $ ، وستكون الخلاص لدينا ما يعادل modulo $ m $ ، لذلك في هذه الحالة، سيكون لدينا لتسوية $ o (\ frac {} {m}) $ ملزمة على احتمال الاصطدام.