الأس المعياري

الأسس المعيارية هي عملية رفع الأس على معامل . وهي مفيدة في علوم الحاسوب ، وخاصة في مجال التشفير بالمفتاح العام ، حيث تُستخدم في كل من تبادل مفاتيح ديفي-هيلمان ومفاتيح RSA العامة/الخاصة .

الرفع الأسي المعياري هو الباقي $c$ عند رفع عدد صحيح $b$ (الأساس) إلى القوة $e$ (الأس)، ثم قسمته على عدد صحيح موجب $m$ (المعيار)؛ أي أن $c = b e mod m$ . ومن تعريف القسمة، يتبين أن $0 \leq c < m$ .

على سبيل المثال، إذا كانت $b = 5$ و $e = 3$ و $m = 13$ ، فإن قسمة $53 = 125$ على $13$ ينتج عنه باقي قسمة $c = 8$ .

عندما يكون العددان $b$ و $m$ أوليين فيما بينهما ، يمكن أيضًا السماح بأن يكون الأس $e$ سالبًا عن طريق إيجاد المعكوس الضربي $d$ للعدد $b$ بتردد $m$ (على سبيل المثال باستخدام خوارزمية إقليدس الموسعة ). بتعبير أدق:

c = b e mod m = d - e mod m

، حيث

e < 0

و

b \cdot d \equiv 1 (mod m)

.

يُعدّ حساب الأس المعياري فعالاً، حتى للأعداد الصحيحة الكبيرة جدًا. في المقابل، يُعتقد أن حساب اللوغاريتم المنفصل المعياري - أي إيجاد الأس $e$ عند معرفة $b$ و $c$ و $m$ - أمرٌ صعب. هذا السلوك أحادي الاتجاه للدالة يجعل حساب الأس المعياري مرشحًا للاستخدام في خوارزميات التشفير.

الطريقة المباشرة

أسهل طريقة لحساب الأس المعياري هي حساب $b e$ مباشرةً، ثم حساب باقي قسمة هذا العدد على $m$ . لنفترض أننا نحاول حساب $c$ ، علمًا بأن $b = 4$ و $e = 13$ و $m = 497$ :

ج \equiv 4 13 (mod 497)

يمكن استخدام الآلة الحاسبة لحساب 4 ¹³ ؛ والنتيجة هي 67,108,864. وبأخذ باقي قسمة هذه القيمة على 497، نجد أن الإجابة $ج$ هي 445.

لاحظ أن $b$ يتكون من رقم واحد فقط وأن $e$ يتكون من رقمين فقط، لكن القيمة $b e$ تتكون من ثمانية أرقام.

في التشفير القوي، غالبًا ما يكون طول $b$ 1024 بت على الأقل . ^{[ 1 ]} لنفترض أن $b = 5 \times 10⁷⁶$ و $e = 17$ ، وهما قيمتان معقولتان تمامًا. في هذا المثال، يبلغ طول $b 77 رقمًا، بينما يبلغ طول$ $e$ رقمين، لكن قيمة $b e$ تبلغ 1304 أرقام عشرية. يمكن إجراء مثل هذه العمليات الحسابية على الحواسيب الحديثة، لكن ضخامة هذه الأرقام تؤدي إلى انخفاض كبير في سرعة العمليات. ومع زيادة $b$ و $e$ أكثر لتحسين الأمان، تصبح قيمة $b e$ غير عملية.

يعتمد الوقت اللازم لإجراء عملية الرفع إلى الأس على بيئة التشغيل والمعالج. تتطلب الطريقة المذكورة أعلاه $Θ (e)$ عملية ضرب لإتمامها.

طريقة فعالة من حيث الذاكرة

إن الحفاظ على الأرقام أصغر يتطلب عمليات تقليل معيارية إضافية، لكن الحجم المصغر يجعل كل عملية أسرع، مما يوفر الوقت (وكذلك الذاكرة) بشكل عام.

تستخدم هذه الخوارزمية الهوية

(أ \cdot ب) mod م = [(أ mod م) \cdot (ب mod م)] mod م

الخوارزمية المعدلة هي:

المدخلات: عدد صحيح $b$ (الأساس)، وعدد صحيح $e$ (الأس)، وعدد صحيح موجب $m$ (المقياس).

الناتج: الأس المعياري $c$ حيث

c = b e mod m

قم بتهيئة المتغير $c = 1$ ومتغير الحلقة $e' = 0$
بينما e′ < e do
1. قم بزيادة قيمة $e'$ بمقدار 1
2. احسب $c = (b \cdot c) mod m$
الناتج $ج$

لاحظ أنه في نهاية كل تكرار للحلقة، تتحقق المعادلة $c \equiv be' (mod m) . تنتهي الخوارزمية عندما يتم تنفيذ الحلقة$ $e$ مرة. عند هذه النقطة، تحتوي $c$ على نتيجة $be' (mod m )$ .

باختصار، تزيد هذه الخوارزمية $قيمة e'$ بمقدار واحد حتى تصبح مساوية لـ $e$ . في كل خطوة، يتم ضرب نتيجة التكرار السابق، $c$ ، في $b$ وإجراء عملية حساب باقي القسمة على الناتج، مما يحافظ على قيمة $c$ الناتجة عددًا صحيحًا صغيرًا.

يُعاد عرض المثال $b = 4$ و $e = 13$ و $m = 497. تُنفّذ الخوارزمية التكرار ثلاث عشرة مرة:$

(e' = 1) c = (4 \cdot 1) mod 497 = 4 mod 497 = 4

(e' = 2) c = (4 \cdot 4) mod 497 = 16 mod 497 = 16

(e' = 3) c = (4 \cdot 16) mod 497 = 64 mod 497 = 64

(e' = 4) c = (4 \cdot 64) mod 497 = 256 mod 497 = 256

(e' = 5) c = (4 \cdot 256) mod 497 = 1024 mod 497 = 30

(e' = 6) c = (4 \cdot 30) mod 497 = 120 mod 497 = 120

(e' = 7) c = (4 \cdot 120) mod 497 = 480 mod 497 = 480

(e' = 8) c = (4 \cdot 480) mod 497 = 1920 mod 497 = 429

(e' = 9) c = (4 \cdot 429) mod 497 = 1716 mod 497 = 225

(e' = 10) c = (4 \cdot 225) mod 497 = 900 mod 497 = 403

(e' = 11) c = (4 \cdot 403) mod 497 = 1612 mod 497 = 121

(e' = 12) c = (4 \cdot 121) mod 497 = 484 mod 497 = 484

(e' = 13) c = (4 \cdot 484) mod 497 = 1936 mod 497 = 445

وبالتالي فإن الإجابة النهائية لـ $c$ هي 445، كما هو الحال في الطريقة المباشرة .

كما هو الحال في الطريقة الأولى، تتطلب هذه الطريقة $O(e)$ عملية ضرب لإتمامها. ومع ذلك، ولأن الأعداد المستخدمة في هذه الحسابات أصغر بكثير من الأعداد المستخدمة في حسابات الخوارزمية الأولى، فإن وقت الحساب ينخفض بمعامل $O(e)$ على الأقل في هذه الطريقة.

في الشفرة الزائفة، يمكن تنفيذ هذه الطريقة بالطريقة التالية:

الدالة modular_pow(base, exponent, modulus) هي: إذا كان modulus = 1، فإن الدالة تُرجع 0. ج := 1 لكل عدد أولي من 0 إلى الأس - 1، قم بما يلي : c := (c * base) mod modulus، ثم أرجع c

طريقة العد الثنائي من اليمين إلى اليسار

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

أولاً، يجب تحويل الأس e $إلى$ الصيغة الثنائية . أي أن $e$ يمكن كتابته على النحو التالي:

e=\sum _{i=0}^{n-1}a_{i}2^{i}

في هذا الترميز، يبلغ طول $e$ عدد $n$ بت. يمكن أن تأخذ $aᵢ$ القيمة 0 أو 1 لأي قيمة لـ $i$ $بحيث$ يكون $0 \leq i < n$ . بحسب التعريف، $aᵢⱼ$ $- 1 = 1$ .

ويمكن كتابة القيمة $b e على النحو التالي:$

b^{e}=b^{\left(\sum _{i=0}^{n-1}a_{i}2^{i}\right)}=\prod _{i=0}^{n-1}b^{a_{i}2^{i}}

وبالتالي فإن الحل $ج$ هو:

c\equiv \prod _{i=0}^{n-1}b^{a_{i}2^{i}}{\pmod {m}}

الشفرة الزائفة

فيما يلي مثال مكتوب بلغة شبه رمزية بناءً على كتاب التشفير التطبيقي لبروس شناير . ^{[ 2 ]} تتوافق المدخلات base و exponent و modulus مع $b$ و $e$ و $m$ في المعادلات المذكورة أعلاه.

الدالة modular_pow(base, exponent, modulus) هي: إذا كان modulus = 1 ، تُرجع 0. تأكد من أن حاصل ضرب (modulus - 1) * (modulus - 1) لا يتجاوز قيمة base. النتيجة := 1 الأساس := الأساس باقي قسمة المعامل طالما أن الأس > 0 نفّذ إذا كان (الأس باقي قسمة 2 == 1) فإن النتيجة := (النتيجة * الأساس) باقي قسمة المعامل الأس := الأس >> 1 base := (base * base) mod modulus return result

لاحظ أنه عند دخول الحلقة لأول مرة، يكون متغير الكود base مكافئًا لـ $b$ . ومع ذلك، فإن التربيع المتكرر في السطر الثالث من الكود يضمن أنه عند اكتمال كل حلقة، يكون متغير base مكافئًا لـ $b 2 i mod m$ ، حيث $i$ هو عدد مرات تكرار الحلقة. (هذا يجعل $i$ البت العامل التالي للأس الثنائي exponent ، حيث يكون البت الأقل أهمية هو الأس ₀ ).

يقوم السطر الأول من التعليمات البرمجية ببساطة بتنفيذ عملية الضرب في $\prod _{i=0}^{n-1}b^{a_{i}2^{i}}{\pmod {m}}$ إذا كانت $قيمة a$ تساوي صفرًا، فلن يتم تنفيذ أي كود، لأن هذا سيؤدي فعليًا إلى ضرب المجموع التراكمي في واحد. أما إذا كانت $قيمة a$ تساوي واحدًا، فسيتم ببساطة ضرب المتغير base (الذي يحتوي على قيمة $b 2 i mod m$ للأساس الأصلي) في المتغير base.

في هذا المثال، يُرفع الأساس $b إلى الأس$ $e = 13.$ الأس هو 1101 في النظام الثنائي. يوجد أربعة أرقام ثنائية، لذا تُنفذ الحلقة أربع مرات، بقيم $a0 = 1، و a1 = 0، و a2 = 1$ ، و $a3 = 1$ .

أولاً، قم بتهيئة النتيجة $R$ إلى 1 مع الحفاظ على قيمة $b$ في المتغير $x$ :

R\leftarrow 1\,(=b^{0}){\text{ and }}x\leftarrow b

.

الخطوة 1) البت 1 هو 1، لذا قم بتعيينه

R\leftarrow R\cdot x{\text{ }}(=b^{1})

؛

تعيين

x\leftarrow x^{2}{\text{ }}(=b^{2})

.

الخطوة 2) البت 2 هو 0، لذا لا تقم بإعادة ضبط

R

؛

تعيين

x\leftarrow x^{2}{\text{ }}(=b^{4})

.

الخطوة 3) البت 3 هو 1، لذا قم بتعيينه

R\leftarrow R\cdot x{\text{ }}(=b^{5})

؛

تعيين

x\leftarrow x^{2}{\text{ }}(=b^{8})

.

الخطوة 4) البت 4 هو 1، لذا قم بتعيينه

R\leftarrow R\cdot x{\text{ }}(=b^{13})

؛

هذه هي الخطوة الأخيرة، لذلك لسنا بحاجة إلى تربيع

x

.

انتهينا: $R$ هو الآن $b^{13}$ .

إليكم الحساب أعلاه، حيث نحسب $b = 4$ مرفوعة للأس $e = 13$ ، ويتم إجراؤها بتردد 497.

التهيئة:

R\leftarrow 1\,(=b^{0})

و

x\leftarrow b=4

.

الخطوة 1) البت 1 هو 1، لذا قم بتعيينه

R\leftarrow R\cdot 4\equiv 4{\pmod {497}}

؛

تعيين

x\leftarrow x^{2}{\text{ }}(=b^{2})\equiv 4^{2}\equiv 16{\pmod {497}}

.

الخطوة 2) البت 2 هو 0، لذا لا تقم بإعادة ضبط

R

؛

تعيين

x\leftarrow x^{2}{\text{ }}(=b^{4})\equiv 16^{2}\equiv 256{\pmod {497}}

.

الخطوة 3) البت 3 هو 1، لذا قم بتعيينه

R\leftarrow R\cdot x{\text{ }}(=b^{5})\equiv 4\cdot 256\equiv 30{\pmod {497}}

؛

تعيين

x\leftarrow x^{2}{\text{ }}(=b^{8})\equiv 256^{2}\equiv 429{\pmod {497}}

.

الخطوة 4) البت 4 هو 1، لذا قم بتعيينه

R\leftarrow R\cdot x{\text{ }}(=b^{13})\equiv 30\cdot 429\equiv 445{\pmod {497}}

؛

انتهينا: $R$ هو الآن $4^{13}\equiv 445{\pmod {497}}$ ، وهي نفس النتيجة التي تم الحصول عليها في الخوارزميات السابقة.

زمن تشغيل هذه الخوارزمية هو $O(log$ exponent $)$ . عند التعامل مع قيم كبيرة للأس ، توفر هذه الخوارزمية سرعة فائقة مقارنةً بالخوارزميتين السابقتين، اللتين يبلغ زمن تشغيلهما $O($ exponent $)$ . على سبيل المثال، إذا كان الأس 2 ^{^20} = 1048576، فإن هذه الخوارزمية ستتطلب 20 خطوة بدلاً من 1048576 خطوة.

التنفيذ بلغة لوا

دالة modPow(b, e, m) إذا كانت m تساوي 1 ، فأرجع 0 نهاية المتغير المحلي r = 1 ب = ب % م بينما e > 0 ، إذا كان e % 2 == 1، فـ r = (r*b) % m نهاية ب = (ب*ب) % م e = e >> 1 -- استخدم 'e = math.floor(e / 2)' في Lua 5.2 أو أقدم نهاية الإرجاع r نهاية

طريقة العد الثنائي من اليسار إلى اليمين

يمكننا أيضًا استخدام بتات الأس من اليسار إلى اليمين. عمليًا، نرغب عادةً في الحصول على الناتج بتردد معين (mod $m$ ). في هذه الحالة، نقوم باختزال كل ناتج ضرب $(mod m)$ قبل المتابعة. ولتبسيط الأمر، تم حذف حساب التردد هنا. يوضح هذا المثال كيفية حساب $b^{13}$ باستخدام عملية الأسس الثنائية من اليسار إلى اليمين. الأس هو 1101 بالنظام الثنائي؛ هناك أربعة بتات، لذا هناك أربع دورات.

قم بتهيئة النتيجة إلى 1: $r\leftarrow 1\,(=b^{0})$ .

الخطوة 1)

r\leftarrow r^{2}\,(=b^{0})

البت 1 = 1، لذا احسب

r\leftarrow r\cdot b\,(=b^{1})

؛

الخطوة الثانية)

r\leftarrow r^{2}\,(=b^{2})

البت 2 = 1، لذا احسب

r\leftarrow r\cdot b\,(=b^{3})

؛

الخطوة 3)

r\leftarrow r^{2}\,(=b^{6})

; البت 3 = 0، لذلك انتهينا من هذه الخطوة؛

الخطوة الرابعة)

r\leftarrow r^{2}\,(=b^{12})

البت 4 = 1، لذا احسب

r\leftarrow r\cdot b\,(=b^{13})

.

الحد الأدنى من عمليات الضرب

في كتاب "فن برمجة الحاسوب" ، المجلد الثاني، "الخوارزميات شبه العددية" ، صفحة 463، يُشير دونالد كنوث إلى أنه خلافًا لبعض الادعاءات، لا تُعطي هذه الطريقة دائمًا أقل عدد ممكن من عمليات الضرب. وأصغر مثال مضاد هو قوة العدد 15، حيث تتطلب الطريقة الثنائية ست عمليات ضرب. بدلًا من ذلك، يُمكن تكوين ^x³^{بعمليتي}^{ضرب، ثم x⁶}بتربيع x³ ^{، ثم x¹²}بتربيع x⁶ ، ^{وأخيرًا} x¹⁵ بضرب x¹² في ^x³ ، وبالتالي تحقيق النتيجة ^{المرجوة} بخمس عمليات ضرب فقط. مع ^ذلك ، تلي ذلك صفحات عديدة تُشرح كيفية ابتكار مثل هذه المتتاليات بشكل عام.

التعميمات

المصفوفات

يمكن حساب الحد m لأي متتالية ثابتة متكررة (مثل أعداد فيبوناتشي أو أعداد بيرين) حيث يكون كل حد دالة خطية لـ k من الحدود السابقة، بكفاءة عالية باستخدام modulo n $،$ وذلك بحساب A m mod n ، $حيث$ $A$ هي $المصفوفة المرافقة k \times$ k $المناظرة$ . $تتكيف الطرق المذكورة$ أعلاه بسهولة مع هذا التطبيق. ويمكن استخدام ذلك لاختبار أولية الأعداد الكبيرة $n$ ، على سبيل المثال.

الشفرة الزائفة

خوارزمية تكرارية لـ ModExp(A, b, c)= $A b mod c$ ، حيث $A$ هي مصفوفة مربعة.

دالة Matrix_ModExp(Matrix A, int b, int c) هي: إذا كان b يساوي صفرًا، فأرجع I (مصفوفة الوحدة). إذا كان باقي قسمة b على 2 يساوي 1، فأرجع ( A * Matrix_ModExp ( A , b - 1, c)) mod c المصفوفة D := Matrix_ModExp(A, b / 2, c) أعد (D * D) mod c

المجموعات الدورية المنتهية

يستخدم تبادل مفاتيح ديفي-هيلمان عملية الأسس في الزمر الدورية المنتهية. ومن الواضح أن الطرق المذكورة أعلاه للأسس المعيارية للمصفوفات قابلة للتطبيق في هذا السياق. يتم استبدال ضرب المصفوفات المعيارية $C \equiv AB (mod n)$ ببساطة في كل مكان بضرب الزمر $c = ab$ .

الأسية المعيارية العكسية والكمية

في الحوسبة الكمومية ، يُمثل حساب الأس المعياري عنق الزجاجة في خوارزمية شور ، حيث يجب حسابه بواسطة دائرة تتكون من بوابات عكسية ، والتي يمكن تقسيمها بدورها إلى بوابات كمومية مناسبة لجهاز فيزيائي محدد. علاوة على ذلك، في خوارزمية شور، من الممكن معرفة أساس ومعامل الأس في كل استدعاء، مما يُتيح تحسينات متنوعة للدائرة. ^{[ 3 ]}

تطبيقات البرمجيات

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

pow()دالة الأس المدمجة في بايثون يأخذ وسيطًا ثالثًا اختياريًا، وهو المعامل
BigIntegerتحتوي فئة إطار عمل .NETModPow() على طريقة لإجراء عملية الأس المعياري
java.math.BigIntegerتحتوي فئة Java علىmodPow() طريقة لإجراء عملية الأسس المعيارية
دالة MATLABpowermod من Symbolic Math Toolbox
تحتوي لغة Wolfram على وظيفة PowerMod
تحتوي Math::BigIntوحدة بيرلbmodpow() على طريقةلإجراء عملية الأس المعياري
يحتوي برنامج راكو على روتين مدمج expmod.
big.Intيحتوي نوع Go علىExp() طريقة (الأس)المعامل الثالث، إذا لم يكن صفراً، هو المعامل المطلق
تحتوي مكتبة BC Math الخاصة بلغة PHPbcpowmod() على دالةلإجراء عملية الأس المعياري
تحتوي مكتبة GNU Multiple Precision Arithmetic Library (GMP) على mpz_powm()دالةلإجراء عملية الأس المعياري
دالة مخصصة @PowerMod()لبرنامج FileMaker Pro (مع مثال على تشفير RSA 1024 بت )
opensslتحتوي حزمة Ruby علىOpenSSL::BN#mod_exp الطريقةلإجراء عملية الأس المعياري.

انظر أيضاً

اختزال مونتغمري ، لحساب الباقي عندما يكون المعامل كبيرًا جدًا.
ضرب كوتشانسكي ، طريقة قابلة للتسلسل لحساب الباقي عندما يكون المعامل كبيرًا جدًا
اختزال باريت ، خوارزمية لحساب الباقي عندما يكون المعامل كبيرًا جدًا.

مراجع

↑ "بروتوكول ديفي-هيلمان الضعيف وهجوم الاختناق" . weakdh.org . تم الاطلاع عليه بتاريخ 3 مايو 2019 .
↑ شناير 1996 ، ص 244.
↑ ماركوف، إ. ل.، وسعيدي، م. (2012). "دوائر كمومية مُحسَّنة للثوابت للضرب والرفع الأسي المعياري". معلومات الكم والحوسبة . 12 ( 5-6 ): 361-394 . arXiv : 1202.6614 . Bibcode : 2012arXiv1202.6614M . doi : 10.26421/QIC12.5-6-1 . S2CID 16595181 .

روابط خارجية

شناير، بروس (1996). التشفير التطبيقي: البروتوكولات والخوارزميات وشفرة المصدر بلغة سي، الطبعة الثانية . وايلي. ISBN 978-0-471-11709-4.
بول غاريت، تطبيق جافا سريع للأسس المعيارية
غوردون، دانيال م. (1998). "دراسة استقصائية لطرق الأسس السريعة" (ملف PDF) . مجلة الخوارزميات . 27 (1). دار النشر إلسيفير: 129-146 . doi : 10.1006/jagm.1997.0913 . ISSN 0196-6774 .

[1] "بروتوكول ديفي-هيلمان الضعيف وهجوم الاختناق" . weakdh.org . تم الاطلاع عليه بتاريخ 3 مايو 2019 .

[schneier96p244-2] شناير 1996 ، ص 244.

[3] ماركوف، إ. ل.، وسعيدي، م. (2012). "دوائر كمومية مُحسَّنة للثوابت للضرب والرفع الأسي المعياري". معلومات الكم والحوسبة . 12 ( 5-6 ): 361-394 . arXiv : 1202.6614 . Bibcode : 2012arXiv1202.6614M . doi : 10.26421/QIC12.5-6-1 . S2CID 16595181 .

[ 1 ]

[ 2 ]

[ 3 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗