مقالات

5: المؤشرات = اللوغاريتمات المنفصلة


تحدثنا عن مجموعة فرعية دورية ( left ) من (( ZZ / n ZZ) ^ * ) تم إنشاؤها بواسطة عنصر (a ) في إثبات نسختنا من نظرية لاغرانج [thm: orddividesphi] ، في الطريق إلى نظرية أويلر [thm: eulers]. وهنا بعض الأمثلة:

مجموعات فرعية دورية لـ (( ZZ / n ZZ) ^ * ) لـ (n = 2 ، النقاط ، 8 )
(ن) (phi (n) ) (( ZZ / n ZZ) ^ * )(أ) ( يسار <أ يمين> ) ( ord_n (أ) )
21({1})1({1})1
32({1, 2})1({1})1
2 ( {2، 2 ^ 2 equiv1 } )2
42({1, 3})1({1})1
3 ( {3، 3 ^ 2 equiv1 } )2
54({1, 2, 3, 4})1({1})1
2 ( {2، 2 ^ 2 equiv4، 2 ^ 3 equiv3، 2 ^ 4 equiv1 } )4
3 ( {3، 3 ^ 2 equiv4، 3 ^ 3 equiv2، 3 ^ 4 equiv1 } )4
4 ( {4، 4 ^ 2 equiv1 } )2
62({1, 5})1({1})1
5 ( {5، 5 ^ 2 equiv1 } )2
76({1, 2, 3, 4, 5, 6})1({1})1
2 ( {2، 2 ^ 2 equiv4، 2 ^ 3 equiv1 } )3
3 ( {3، 3 ^ 2 equiv2، 3 ^ 3 equiv6، 3 ^ 4 equiv4، 3 ^ 5 equiv5، 3 ^ 6 equiv1 } )6
4 ( {4، 4 ^ 2 equiv2، 4 ^ 3 equiv1 } )3
5 ( {5، 5 ^ 2 equiv4، 5 ^ 3 equiv6، 5 ^ 4 equiv2، 5 ^ 5 equiv3، 5 ^ 6 equiv1 } )6
6 ( {6، 6 ^ 2 equiv1 } )2
84({1, 3, 5, 7})1({1})1
3 ( {3، 3 ^ 2 equiv1 } )2
5 ( {5، 5 ^ 2 equiv1 } )2
7 ( {7، 7 ^ 2 equiv1 } )2

كل مجموعة من هذه المجموعات الفرعية الدورية ( left ) لها حجم - هو الترتيب ( ord_n (a) ) لمولدها - الذي يقسم حجم المحيط (( ZZ / n ZZ) ^ * ) ، كما نعلم سيحدث من نظرية أويلر [thm: أويلرز].

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

فقط لمعرفة ما إذا كانت تلك العبارات العامة المحتملة تحمل بعض الشيء ، دعنا نحسب مثالين آخرين. بالنسبة إلى هذه ، نعطي فقط أحجام (( ZZ / n ZZ) ^ * ) و ( left ) ، وليس قوائم كاملة بعناصرها ، للحفاظ على المساحة ومنذ عناصر (( ZZ / n ZZ) ^ * ) يمكن العثور عليها في العمود المسمى “ (a )”:

مجموعات فرعية دورية لـ (( ZZ / n ZZ) ^ * ) لـ (n = 16 ) و (n = 17 )
(ن) (phi (n) ) (a in ( ZZ / n ZZ) ^ * ) ( ord_n (أ) )
16811
34
54
72
92
114
134
152
171611
28
316
44
516
616
716
88
98
1016
1116
1216
134
1416
158
162

تخميناتنا (القوى الكبيرة لـ (2 ) ليست جيدة ؛ الأخرى (n ) ، خاصةً الأولية ، جيدة) لا تزال صحيحة. بالطبع ، أي كمية محدودة من الأدلة لبيان رياضي عام غير حاسمة للغاية ....

الآن إلى التحليل الرسمي.


آلة حاسبة لوغاريتم منفصلة

تتمثل مشكلة اللوغاريتم المنفصل في إيجاد الأس في التعبير Base Exponent = Power (modulus).

يعمل هذا التطبيق الصغير لكل من الوحدات الأولية والمركبة. القيد الوحيد هو أن القاعدة والمقياس والقوة والمعاملة يجب أن تكون أساسية نسبيًا.

في هذا الإصدار من حاسبة اللوغاريتم المنفصل ، يتم تنفيذ خوارزمية Pohlig-Hellman فقط ، وبالتالي فإن وقت التنفيذ يتناسب مع الجذر التربيعي لأكبر عامل أولي للمعامل ناقص 1. يعمل التطبيق الصغير في فترة زمنية معقولة إذا كان هذا العامل أقل من 10 17.

سأضيف خوارزمية حساب التفاضل والتكامل قريبًا. هذه الخوارزمية لها وقت تشغيل فرعي.


القسم 8.5. اللوغاريتمات المنفصلة

اللوغاريتمات المنفصلة أساسية لعدد من خوارزميات المفتاح العام ، بما في ذلك تبادل مفاتيح Diffie-Hellman وخوارزمية التوقيع الرقمي (DSA). يقدم هذا القسم لمحة موجزة عن اللوغاريتمات المنفصلة. للقارئ المهتم ، يمكن العثور على المزيد من التطورات التفصيلية لهذا الموضوع في [ORE67] و [LEVE90].

صلاحيات العدد الصحيح ، Modulo n

تذكر من نظرية أويلر [المعادلة (8.4)] أنه بالنسبة لكل من a و n التي تعتبر عددًا أوليًا نسبيًا:

أ و (ن) 1 (mod حيث f (n) ، دالة أويلر الكلية ، هي عدد الأعداد الصحيحة الموجبة الأقل من n والأعداد الأولية نسبيًا لـ n. الآن ضع في اعتبارك التعبير الأكثر عمومية:

إذا كان a و n عددًا أوليًا نسبيًا ، فهناك على الأقل عدد صحيح واحد يفي بالمعادلة (8.10) ، أي m = f (n). يُشار إلى الأس الأقل الموجب m الذي تحمل المعادلة (8.10) بعدة طرق:

الأس الذي ينتمي إليه (تعديل ن)

طول الفترة الناتجة عن أ

لمعرفة هذه النقطة الأخيرة ، ضع في اعتبارك قوى 7 ​​، modulo 19:

= 49 = 2 × 19 + 11

= 343 = 18 × 19 + 1

= 2401 = 126 × 19 + 7

= 16807 = 884 × 19 + 11

لا جدوى من الاستمرار لأن التسلسل يتكرر. يمكن إثبات ذلك من خلال ملاحظة أن 7 3 1 (mod 19) وبالتالي 7 3+ 7 3 7 7 m مثل 7 م /> 1 (mod 19).

يوضح الجدول 8.3 جميع قوى a ، modulo 19 لجميع موجبات a & lt 19. يشار إلى طول التسلسل لكل قيمة أساسية من خلال التظليل. لاحظ ما يلي:

تنتهي جميع المتتاليات بالرقم 1. وهذا يتفق مع منطق الفقرات القليلة السابقة.

طول التسلسل يقسم f (19) = 18. أي أن عددًا صحيحًا من التسلسلات يحدث في كل صف من الجدول.

بعض المتتاليات بطول 18. في هذه الحالة ، يُقال أن العدد الصحيح الأساسي يولد (عن طريق القوى) مجموعة من الأعداد الصحيحة غير الصفرية المقياس 19. يسمى كل عدد صحيح جذرًا بدائيًا للمعامل 19.

الجدول 8.3. صلاحيات الأعداد الصحيحة ، Modulo 19

بشكل عام ، يمكننا أن نقول أن أعلى أس ممكن يمكن أن ينتمي إليه رقم (عصري ن) هو f (ن). إذا كان الرقم بهذا الترتيب ، فيُشار إليه على أنه جذر بدائي من تكمن أهمية هذه الفكرة في أنه إذا كان a جذرًا بدائيًا لـ n ، فإن صلاحياته

مميزة (mod n) وكلها أولية نسبيًا لـ n. على وجه الخصوص ، بالنسبة للرقم الأولي p ، إذا كان a هو الجذر البدائي لـ p ، إذن

مميزة (mod p). بالنسبة للعدد الأولي 19 ، فإن جذوره الأولية هي 2 و 3 و 10 و 13 و 14 و 15.

ليست كل الأعداد الصحيحة لها جذور بدائية. في الواقع ، الأعداد الصحيحة الوحيدة ذات الجذور البدائية هي تلك التي على شكل 2 و 4 و p a و 2 p a ، حيث p هي أي شرطة فردية و a عدد صحيح موجب. الإثبات ليس بسيطًا ولكن يمكن العثور عليه في العديد من كتب نظرية الأعداد ، بما في ذلك [ORE76].

لوغاريتمات الحساب النمطي

مع الأعداد الحقيقية الموجبة العادية ، فإن دالة اللوغاريتم هي معكوس الأس. توجد وظيفة مماثلة للحساب النمطي.

دعونا نستعرض بإيجاز خصائص اللوغاريتمات العادية. يتم تعريف اللوغاريتم لرقم ما على أنه القوة التي يجب رفع بعض الأساس الموجب إليها (باستثناء 1) من أجل مساواة الرقم. أي بالنسبة للقاعدة x وللقيمة y:

تشمل خصائص اللوغاريتمات ما يلي:

ضع في اعتبارك جذرًا بدائيًا a لبعض الأعداد الأولية p (يمكن تطوير الحجة لـ nonprimes أيضًا). ثم نعلم أن قوى a من 1 إلى (p 1) تنتج كل عدد صحيح من 1 إلى (p 1) مرة واحدة بالضبط. ونعلم أيضًا أن أي عدد صحيح ب يرضي

ب p) بالنسبة لبعض r ، حيث 0 (من خلال تعريف الحساب النمطي. ويترتب على ذلك أنه بالنسبة لأي عدد صحيح b والجذر البدائي a للرقم الأولي p ، يمكننا العثور على الأس الفريد مثل هذا

ب ع) حيث 0 ([صفحة 251]

يشار إلى هذا الأس أنا باللوغاريتم المنفصل من الرقم b للقاعدة a (mod p). نشير إلى هذه القيمة على أنها dlog أ ( ب ). [9]

[9] تشير العديد من النصوص إلى اللوغاريتم المنفصل باسم فهرس . لا يوجد تدوين متفق عليه بشكل عام لهذا المفهوم ، ناهيك عن اسم متفق عليه.

هذا مثال باستخدام معامل غير أساسي ، n = 9. هنا f (n) = 6 و a = 2 هو جذر بدائي. نحسب القوى المختلفة لـ a ونجد

2 4 7 (mod 9)

2 5 5 (mod 9)

2 6 1 (mod 9)

هذا يعطينا الجدول التالي للأرقام مع لوغاريتمات منفصلة معينة (mod 9) للجذر a = 2:


5: المؤشرات = اللوغاريتمات المنفصلة

اللوغاريتمات المنفصلة هي لوغاريتمات محددة فيما يتعلق بمجموعات دورية مضاعفة. إذا جي هي مجموعة دورية مضاعفة و ز هو منشئ جي ، إذن من تعريف المجموعات الحلقية ، نعرف كل عنصر ح في جي يمكن كتابتها كـ ز x بالنسبة للبعض x . اللوغاريتم المنفصل للقاعدة ز من ح في المجموعة جي يعرف بأنه x . على سبيل المثال ، إذا كانت المجموعة ض 5 * ، والمولد هو 2 ، ثم اللوغاريتم المنفصل لـ 1 هو 4 لأن 2 4 & # 8801 1 mod 5.

يتم تعريف مشكلة اللوغاريتم المنفصل على النحو التالي: معطى مجموعة جي ، مولد ز للمجموعة وعنصر ح من جي ، لإيجاد اللوغاريتم المنفصل للقاعدة ز من ح في المجموعة جي . مشكلة اللوغاريتم المنفصلة ليست دائما صعبة. تعتمد صعوبة إيجاد اللوغاريتمات المنفصلة على المجموعات. على سبيل المثال ، الاختيار الشائع للمجموعات لأنظمة التشفير المنفصلة القائمة على اللوغاريتم هو ض ص * حيث p هو عدد أولي. ومع ذلك، إذا ص & # 87221 هو نتاج أعداد أولية صغيرة ، ثم يمكن لخوارزمية Pohlig & # 8211Hellman حل مشكلة اللوغاريتم المنفصلة في هذه المجموعة بكفاءة عالية. لهذا السبب نريد دائما ص ليكون رئيسًا آمنًا عند الاستخدام ض ص * كأساس لأنظمة التشفير المنفصلة القائمة على اللوغاريتم. الشرط الآمن هو عدد أولي يساوي 2 ف +1 أين ف هو عدد أولي كبير. هذا يضمن ذلك ص -1 = 2 ف عامل أولي كبير بحيث لا تستطيع خوارزمية Pohlig & # 8211Hellman حل مشكلة اللوغاريتم المنفصلة بسهولة. حتى في ص هو رئيس آمن ، هناك خوارزمية أسية فرعية تسمى حساب التفاضل والتكامل. هذا يعني ص يجب أن يكون كبيرًا جدًا (عادةً على الأقل 1024 بت) لجعل أنظمة التشفير آمنة.


حساب العوامل الأولية واللوغاريتمات المنفصلة: من حساب التفاضل والتكامل إلى حساب Xedni

تعد مشكلة عامل العدد الصحيح (IFP) ، ومسألة اللوغاريتم المنفصل للحقل المحدود (DLP) ومسألة اللوغاريتم المنفصل للمنحنى الإهليلجي (ECDLP) في الأساس المشكلات الرياضية الثلاثة الوحيدة التي تعتمد عليها أنظمة تشفير المفتاح العمومي العملية. على سبيل المثال ، يعتمد نظام تشفير RSA الأكثر شهرة على IFP ، ويعتمد معيار التوقيع الرقمي للحكومة الأمريكية ، DSS ، على DLP ، في حين أن ECC (تشفير منحنى إهليلجي) وخوارزمية التوقيع الرقمي منحنى إهليلجي (ECDSA) تستند إلى ECDLP. يعتمد أمان أنظمة التشفير هذه على الاستعصاء الحسابي لهذه المشكلات الرياضية الثلاثة. في هذه الورقة ، سنقدم مسحًا للطرق المختلفة لحل IFP / DLP وخاصة مشكلات ECDLP. وبشكل أكثر تحديدًا ، سنناقش أولاً كيفية استخدام حساب التفاضل والتكامل بالإضافة إلى خوارزميات الكم لحل IFP / DLP. ثم سنوضح لماذا لا يمكن استخدام حساب الفهرس لحل ECDLP. أخيرًا ، سنقدم طريقة جديدة ، حساب التفاضل والتكامل xedni ، بسبب جوزيف سيلفرمان ، للهجوم على ECDLP ، سيتم أيضًا معالجة بعض المشكلات المفتوحة واتجاهات البحث الجديدة.


خوارزمية لوغاريتمية Shor & # 39s المنفصلة مع QFT بقاعدة أولية صغيرة

لنفترض أنك استبدلت كلاً من QFTs في خوارزمية اللوغاريتم المنفصلة لـ Shor مع QFTs أبسط مع قاعدة أولية صغيرة w. هل تستخرج هذه الخوارزمية وحدة اللوغاريتم المنفصلة ث؟ يبدو أنه كذلك ، بشرط أن تضمن أن اللوغاريتم المنفصل الكامل ليس كبيرًا جدًا ، وأن Hadamards في السجل الثاني تولد فقط نطاقًا أصغر من القيم ، $ max (b) $ بحيث أن $ max (b) max ( alpha) & lt p-1 $ ، حيث $ alpha $ هو اللوغاريتم المنفصل الكامل. على سبيل المثال ، إذا كان $ max (b) $ = $ max ( alpha) $ = $ frac <2 ^ < lfloor log p rfloor >> <64> $ ، فإن خوارزمية Shor المعدلة ستخرج $ ألفا وزارة الدفاع ث $. ستنتهي دائرة شور المعدلة بالحالة:

النطاق المقيد $ b $ يعمل للسبب التالي. إذا كتبنا $ y equiv g ^ k $ (يمكن كتابة قوة $ x $ كقوة $ g $) ، ثم $ a-rb equiv k mod (p-1) $ و

$ a = rb + k - (p-1) lfloor frac r الطابق $

يجب أن يحتوي $ a $ على النطاق الكامل $ 2 ^ < lceil log p rceil> $ و $ b $ يجب أن يقتصر على $ max (b) $. هذه ليست مشكلة لأن أي $ a $ سيحصل على $ k $ والذي يتراوح من $ إلى $ p-1 $ ، لذلك سيكون لدى $ a $ و $ b $ حلول دائمًا. يجب اختيار $ r $ في التعويض ليكون في النطاق $ [0، max (r)] $ لتجنب الأخطاء في أخذ المعامل الثاني.

بعد Shor ، السعة هي $ frac <1>> sum_^ exp big ( frac <2 pi i>(brc + kc + bd-c (p-1) lfloor frac r طابق) كبير) $

أخرج العامل $ exp (2 pi i frac) $ الذي لا يؤثر على الاحتمالية والحصول على

$ V $ صغير تلقائيًا كما هو الحال في الخوارزمية العادية. بالنسبة إلى $ T $ ، فإن هذين $ c و d $ مثل $ rc + d = 0 mod w $ يشفر نمط الفترة $ w $. $ فارك <_w> & lt 1 $ ، لذا إذا $ frac & lt & lt 1 $ ، فإن الأسي لجميع المصطلحات سيكون قريبًا من 1 للأزواج $ c ، d $ مثل أن $ rc + d = 0 mod w $ ، بحيث تكون المبالغ $ max (b) + 1 $ جميعها بنّاءة . إذا كان $ rc + d neq 0 mod w $ ، فإن $ exp ( frac <2 pi i>bT) $ سيحتوي على مصطلحات مثل "cycled through" مثل $ exp ( frac <2 pi i>max (b)) $ ، وسيضمن التداخل المدمر أن مجموعها يساوي صفرًا تقريبًا.

من نظرية الباقي الصيني ، يمكن استخدام دورات متعددة بأعداد أولية صغيرة مختلفة لإعادة بناء اللوغاريتم المنفصل بأكمله. لاحظ أن الدائرة الأولية الصغيرة لها نفس التعقيد المقارب مثل دائرة اللوغاريتم المنفصلة الكاملة وستتطلب تشغيل O (n) لبناء اللوغاريتم بأكمله ، لذلك سيكون أبطأ بكثير في الممارسة. جميع الملاحظات مأخوذة من الورقة الأصلية لبيتر شور ، باستثناء $ alpha $.


دع $ p $ يكون رئيسًا. نقول أن $ g $ هو أ جذر بدائي من $ p $ (أو أحيانًا modulo $ p $) ، إذا كانت القوى $ g ^ 1 $ ، $ g ^ 2 $ ، $ g ^ 3 $ ، $ dots $ ، $ g ^تتطابق $ ، في بعض الترتيب ، مع $ 1 $ ، $ 2 $ ، $ 3 $ ، $ dots $ ، $ p-1 $ (modulo $ p $). أو بعبارات أبسط ، عندما نفكر في الباقي عند قسمة $ g ^ k $ على $ p $ ، فإن جميع الأرقام بين $ 1 و $ p-1 $ هي باقٍ (لا يمكن أن يكون $).

لاحظ أنه من خلال نظرية فيرمات ، $ g ^ equiv 1 pmod

$ ، لذا بعد $ g ^$ ، صلاحيات $ g $ تبدأ من جديد من جديد modulo $ p $ ، لذا $ g ^ p equiv g $، $ g ^ equiv g ^ 2 $ وهكذا.

إذا رأيت بعض نظرية المجموعات ، فيمكننا أن نقول بالتناوب أن $ g $ هو جذر بدائي لـ $ p $ إذا كان $ g $ هو a مولد كهرباء للمجموعة المضاعفة للكائنات غير الصفرية المقياس $ p $.

يمكن إثبات ذلك باستخدام الأدوات الأولية أن كل رئيس له جذر بدائي. الدليل ليس بهذه السهولة. الأعداد الأولية الكبيرة $ p $ لها العديد من الجذور البدائية.

هنا مثال صغير. لنفترض أن $ p = 7 دولارات ، وأخذ $ g = 2 $. صلاحيات $ 2 $ ، modulo $ 7 $ ، هي $ 2 $ ، $ 4 $ ، $ 1 $ ، $ 2 $ ، $ 4 ، $ dots $. لذلك لا نحصل على كل شيء ، 2 دولار ليست جذرًا أوليًا لـ 7 دولارات. الآن خذ $ g = 3 $. صلاحيات $ 3 $ ، modulo $ 7 $ ، هي $ 3 $ ، $ 2 $ ، $ 6 $ ، $ 4 $ ، $ 5 $ ، $ 1 $ ، $ 3 $ ، $ dots $ ، لذلك نحصل على كل شيء ، $ 3 $ هو جذر بدائي 7 دولارات.

لنفترض أن $ g $ جذرًا بدائيًا معروفًا لـ $ p $ ، وافترض أن $ a $ أعلى نسبيًا لـ $ p $. بعد ذلك ، حسب التعريف ، يوجد عدد صحيح فريد $ k $ ، مع $ 1 le k le p-1 $ ، مثل $ g ^ k equiv a pmod p $ (يستخدم بعض الأشخاص le k le p- 2 دولار بدلاً من ذلك ، أفضل ذلك ، لا يهم كثيرًا).

كان الرقم $ k $ يُطلق عليه اسم فهرس $ a $ بالنسبة للجذر البدائي $ g $. في الآونة الأخيرة ، وبشكل عام في علوم الكمبيوتر ، يُطلق على $ k $ اسم لوغاريتم منفصل $ a $ (بالنسبة للجذر البدائي $ g $).

هذه "اللوغاريتمات المنفصلة" لها خصائص شكلية تشبه إلى حد كبير اللوغاريتمات العادية. لاحظ على وجه الخصوص أن اللوغاريتمات المنفصلة هي الأس، تمامًا مثل اللوغاريتمات العادية.

ما هي جيدة من أجله: هنا سوف ألقي نظرة على سبب استخدامها في التشفير. إذا كنت تعرف $ g $ و $ k $ ، فهو كذلك سهل حسابيًا لحساب الباقي عند قسمة $ g ^ k $ على $ p $ ، حتى عندما يكون $ p $ عددًا أوليًا ضخمًا. نحن نستخدم ال الطريقة الثنائية للأس (ابحث عن هذا) أو أحد الأقارب.

ولكن بالنظر إلى $ g $ و $ a $ ، يبدو أنها حسابية صعب جدا للعثور على $ k $ بين $ 1 $ و $ p-1 $ مثل $ g ^ k equiv a pmod p $. بعبارة أخرى ، يبدو أن إيجاد اللوغاريتم المنفصل عند تضمين عدد أولي كبير جدًا أمر صعب للغاية من الناحية الحسابية.

هذا يجعل معامل الأُس $ p $ وظيفة "trap-door" مفيدة ، ويسهل القيام بها ، ولكن من الصعب التراجع عنها ، نوعًا ما مثل ضرب عددين أوليين (سهل) وعوامل ناتج من عددين أوليين كبيرين (يبدو صعبًا جدًا).

نأمل أن يعطي هذا نظرة عامة على اللوغاريتم المنفصل. أنا حقا لا أستطيع إضافة أي شيء عن تفاصيل Diffie Hellman. لسبب واحد ، هناك مجموعة من إجراءات DH.

باختصار ، السبب الرئيسي لفائدة اللوغاريتم المنفصل هو الخصائص الجبرية الجميلة ، جنبًا إلى جنب مع تأثير "باب المصيدة".


5: المؤشرات = اللوغاريتمات المنفصلة

حل مسائل اللوغاريتم المنفصلة بطريقة حساب التفاضل والتكامل.

استخدم Git أو checkout مع SVN باستخدام عنوان URL للويب.

اعمل بسرعة مع CLI الرسمي. يتعلم أكثر.

بدء تشغيل GitHub Desktop

إذا لم يحدث شيء ، فقم بتنزيل GitHub Desktop وحاول مرة أخرى.

بدء تشغيل GitHub Desktop

إذا لم يحدث شيء ، فقم بتنزيل GitHub Desktop وحاول مرة أخرى.

إطلاق Xcode

إذا لم يحدث شيء ، قم بتنزيل Xcode وحاول مرة أخرى.

إطلاق برنامج Visual Studio Code

سيتم فتح مساحة التشفير الخاصة بك بمجرد أن تصبح جاهزة.

حدثت مشكلة أثناء تحضير مساحة الكود ، يرجى المحاولة مرة أخرى.


مشكلة اللوغاريتم المنفصل

إذا هو رئيس و ، نحن نكتب إذا استوفي . مشكلة إيجاد مثل هذا العدد الصحيح لاجل منحه (مع ) هل مشكلة سجل منفصل.

تعتبر مشكلة اللوغاريتم المتقطع مشكلة حرجة في نظرية الأعداد ، وهي مشابهة من نواحٍ عديدة لمسألة تحليل العوامل الصحيحة. إذا كان من الممكن حساب السجلات المنفصلة بكفاءة ، فسيكون من الممكن كسر العديد من مخططات التشفير غير القابلة للكسر. ومع ذلك ، على الرغم من أن معظم علماء الرياضيات وعلماء الكمبيوتر يعتقدون أن DLP غير قابل للحل ، فمن الصعب إثبات هذا التخمين ، لأن مثل هذا الدليل يعني أن P! = NP. وهي أصعب مشكلة مفتوحة في علم الحاسوب النظري.

أظهر Avi Wigderson أنه لا يوجد `` دليل طبيعي '' (بمعنى [RR]) على أن DLP يتطلب دوائر أكبر من نصف حجم أسي. الفكرة الأساسية هي أن الدليل الطبيعي على أن DLP صعب من شأنه أن يفضي إلى طريقة لكسر أنظمة التشفير المنفصلة القائمة على السجل ، وهذا تناقض. بالطبع ، لا يزال من الممكن إثبات أن DLP صعب ، ولكن من خلال إثبات ليس `` طبيعيًا ''.


كلية العلوم ، جامعة شمال الصين للتكنولوجيا ، بكين ، الصين

قسم الرياضيات ، جامعة هارفارد ، كامبريدج ، الولايات المتحدة الأمريكية

كلية العلوم ، جامعة شمال الصين للتكنولوجيا ، بكين ، الصين

قسم الرياضيات ، جامعة هارفارد ، كامبريدج ، الولايات المتحدة الأمريكية

الملخص

يشير الفصل إلى أن مشكلة اللوغاريتم المنفصل (DLP) ومسألة اللوغاريتم المنفصل للمنحنى الإهليلجي (ECDLP) ، جنبًا إلى جنب مع مشكلة التضمين الصحيح (IFP) ، هي أهم ثلاث مشاكل حسابية غير قابلة للتطبيق في نظرية الأعداد الحسابية والتشفير الحديث. يناقش الفصل العديد من الخوارزميات الحديثة الشائعة والمستخدمة على نطاق واسع لـ DLP / ECDLP ، بما في ذلك طريقة خطوة الطفل العملاقة لـ DLP ، خوارزمية Pohlig-Hellman لـ DLP / ECDLP حساب التفاضل والتكامل الخاص بمؤشر DLP. تعتمد طريقة ميستري على بعض الأفكار العميقة والتخمينات غير المثبتة في نظرية الأعداد التحليلية والهندسة الجبرية الحسابية ، ولا يمكننا في الوقت الحالي تقديم تقدير تقريبي لوقت تشغيل الخوارزمية. حساب التفاضل والتكامل هو خوارزمية احتمالية ذات زمن أسي فرعي قابلة للتطبيق على كل من مشكلة العامل الصحيح (IFP) ومسألة اللوغاريتم المنفصل في الميدان (DLP). تكمن مشكلة الخوارزميات الكمومية في أن الكمبيوتر الكمومي العملي بعيد المنال في تكنولوجيا اليوم.


شاهد الفيديو: اللوغاريتم 5 للمستجدين (شهر اكتوبر 2021).