الأسس بالتربيع

📅 آخر تحديث: ٢ أغسطس ٢٠٢٦
✍️ نُشر في: ٢ أغسطس ٢٠٢٦
📷 يحتوي على 56 صور
الموسوعة الحرة

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

الطريقة الأساسية

النسخة المتكررة

تعتمد هذه الطريقة على الملاحظة التي تفيد بأنه لأي عدد صحيحن>0{\displaystyle n>0}، لدى المرء xن={x(x2)(ن-1)/2لو ن غريب،(x2)ن/2لو ن بل إنه كذلك.{\displaystyle x^{n}={\begin{cases}x\,(x^{2})^{(n-1)/2}&{\text{إذا كان }}n{\text{ فرديًا}},\\(x^{2})^{n/2}&{\text{إذا كان }}n{\text{ زوجيًا}}.\end{cases}}}

إذا كان الأس n يساوي صفرًا، فإن الإجابة هي 1. أما إذا كان الأس سالبًا، فيمكننا إعادة استخدام الصيغة السابقة عن طريق إعادة كتابة القيمة باستخدام أس موجب. أي، xن=(1x)-ن.{\displaystyle x^{n}=\left({\frac {1}{x}}\right)^{-n}.}

ويمكن تنفيذ هذه الأمور معًا بشكل مباشر كخوارزمية تكرارية كما يلي :

المدخلات : عدد حقيقي x ؛ عدد صحيح n. المخرجات : x nالدالة exp_by_squaring( x , n ) هي : إذا كان n < 0 ، تُرجع exp_by_squaring(1 / x , −n ) ، وإذا كان n = 0 ، تُرجع 1 ، وإذا كان n زوجيًا، تُرجع exp_by_squaring( x × x , n / 2) ، وإذا كان n فرديًا ، تُرجع x × exp_by_squaring( x × x , ( n − 1) / 2) .

في كل استدعاء تكراري، يُحذف الرقم الأقل أهمية من التمثيل الثنائي لـ n . وبالتالي، فإن عدد الاستدعاءات التكرارية هو⌈سجل2⁡ن⌉،{\displaystyle \lceil \log _{2}n\rceil ,}عدد بتات التمثيل الثنائي للعدد n . لذا، تحسب هذه الخوارزمية هذا العدد من المربعات وعددًا أقل من عمليات الضرب، وهو ما يساوي عدد الآحاد في التمثيل الثنائي للعدد n . يُقارن هذا العدد اللوغاريتمي من العمليات بالخوارزمية البسيطة التي تتطلب n - 1 عملية ضرب.

هذه الخوارزمية ليست تكرارية ذيلية . وهذا يعني أنها تتطلب مقدارًا من الذاكرة المساعدة يتناسب تقريبًا مع عدد الاستدعاءات التكرارية، أو ربما يكون أكبر إذا كانت كمية البيانات لكل تكرار تتزايد.

تستخدم خوارزميات القسم التالي نهجًا مختلفًا، وتحتاج الخوارزميات الناتجة إلى نفس عدد العمليات، ولكنها تستخدم ذاكرة مساعدة مماثلة تقريبًا للذاكرة المطلوبة لتخزين النتيجة.

مع ذاكرة مساعدة ثابتة

تعتمد المتغيرات الموضحة في هذا القسم على الصيغة yxن={yx(x2)(ن-1)/2لو ن غريب،y(x2)ن/2لو ن بل إنه كذلك.{\displaystyle yx^{n}={\begin{cases}yx\,(x^{2})^{(n-1)/2}&{\text{إذا كان }}n{\text{ فرديًا}},\\y\,(x^{2})^{n/2}&{\text{إذا كان }}n{\text{ زوجيًا}}.\end{cases}}}

إذا قام المرء بتطبيق هذه الصيغة بشكل متكرر، بدءًا من y = 1 ، فسيحصل في النهاية على أس يساوي 0 ، والنتيجة المرجوة هي العامل الأيسر.

يمكن تنفيذ ذلك كدالة تكرارية ذيلية:

الدالة exp_by_squaring ( x , n ) تُرجع exp_by_squaring2 ( 1 , x , n )دالة exp_by_squaring2 ( y , x , n ) إذا كان n < 0 فإن إرجاع exp_by_squaring2 ( y , 1 / x , - n ) ؛ وإلا إذا كان n = 0 فإن إرجاع y ؛ وإلا إذا كان n زوجيًا فإن إرجاع exp_by_squaring2 ( y , x * x , n / 2 ) ؛ وإلا إذا كان n فرديًا فإن إرجاع exp_by_squaring2 ( x * y , x * x , ( n - 1 ) / 2 ) .

تستخدم النسخة التكرارية من الخوارزمية أيضًا مساحة مساعدة محدودة، ويتم إعطاؤها بواسطة

دالة exp_by_squaring_iterative ( x , n ) إذا كان n < 0 فإن x := 1 / x ; n := - n ; إذا كان n = 0 فإن return 1 y := 1 ; بينما n > 1 do إذا كان n فرديًا فإن y := x * y ; n := n - 1 ; x := x * x ; n := n / 2 ; return x * y

تنبع صحة الخوارزمية من حقيقة أنyxن{\displaystyle yx^{n}}يظل ثابتًا أثناء الحساب؛ إنه1⋅xن=xن{\displaystyle 1\cdot x^{n}=x^{n}}في البداية؛ وهوyx1=xy{\displaystyle yx^{1}=xy}في نهايةالمطاف.

تستخدم هذه الخوارزميات نفس عدد العمليات تمامًا مثل خوارزمية القسم السابق، ولكن عمليات الضرب تتم بترتيب مختلف.

التعقيد الحسابي

يُظهر تحليل موجز أن مثل هذه الخوارزمية تستخدم⌊سجل2⁡ن⌋{\displaystyle \lfloor \log _{2}n\rfloor }التربيعات وعلى الأكثر⌊سجل2⁡ن⌋{\displaystyle \lfloor \log _{2}n\rfloor }عمليات الضرب، حيث⌊⌋{\displaystyle \lfloor \;\rfloor }يرمز إلى دالة الجزء الصحيح . وبشكل أدق، يكون عدد عمليات الضرب أقل بواحد من عدد الآحاد الموجودة في التمثيل الثنائي للعدد n . بالنسبة لقيم n الأكبر من 4 تقريبًا، يكون هذا أكثر كفاءة حسابيًا من ضرب الأساس بنفسه بشكل متكرر.

ينتج عن كل تربيع ضعف عدد أرقام العدد السابق تقريبًا، وبالتالي، إذا تم تنفيذ ضرب عددين مكونين من d رقمًا في O( dk ) عملية لبعض قيم k الثابتة ، فإن تعقيد حساب xn يُعطى بالصيغة التالية :

∑أنا=0يا(سجل⁡ن)(2أنايا(سجل⁡x))ك=يا((نسجل⁡x)ك).{\displaystyle \sum \limits _{i=0}^{O(\log n)}{\big (}2^{i}O(\log x){\big )}^{k}=O{\big (}(n\log x)^{k}{\big )}.}

طريقة 2k - ary

تحسب هذه الخوارزمية قيمة xⁿ بعد توسيع الأس في الأساس 2k . وقد اقترحها براور لأول مرة عام 1939. في الخوارزمية أدناه ، نستخدم الدالة التالية f (0) = ( k , 0) و f ( m ) = ( s , u )، حيث m = u · 2s مع u عدد فردي.

الخوارزمية:

مدخل
عنصر x من G ، ومعامل k > 0، وعدد صحيح غير سالب n = ( n l −1 , n l −2 , ..., n 0 ) 2 k والقيم المحسوبة مسبقًاx3،x5،...،x2ك-1{\displaystyle x^{3},x^{5},...,x^{2^{k}-1}}.
الناتج
العنصر x n في G
y := 1; i := l - 1 while i ≥ 0 do (s, u) := f(n i ) for j := 1 to k - s do y := y 2 y := y * x u for j := 1 to s do y := y 2 i := i - 1 أعد y

لتحقيق الكفاءة المثلى، يجب أن يكون k أصغر عدد صحيح يحقق [ 1 ]

إل جي⁡ن<ك(ك+1)⋅22ك2ك+1-ك-2+1.{\displaystyle \lg n<{\frac {k(k+1)\cdot 2^{2k}}{2^{k+1}-k-2}}+1.}

طريقة النافذة المنزلقة

هذه الطريقة هي صيغة فعّالة من طريقة 2k - ary. على سبيل المثال، لحساب الأس 398، الذي يُكتب في التمثيل الثنائي (110001110) ² ، نستخدم نافذة طولها 3 باستخدام خوارزمية طريقة 2k - ary، ونحسب القيم التالية: 1، x³ ، x⁶ ، x¹² ، x²⁴ ، x⁴⁸ ، x⁴⁹، x⁹⁸ ، x⁹⁹ ، x³⁹⁸ . ولكن ، يمكننا أيضًا حساب القيم التالية: 1، x³ ، x⁶ ، x¹² ، x²⁴ ، x⁴⁸ ، x⁹⁶ ، x⁹⁹⁹ ، x³⁹⁸ ، مما يوفر عملية ضرب واحدة ويُعادل حساب ( 110001110 ) ²

إليكم الخوارزمية العامة:

الخوارزمية:

مدخل
عنصر x من G ، وعدد صحيح غير سالب n = ( n l −1 ، n l −2 ، ...، n 0 ) 2 ، ومعامل k > 0، والقيم المحسوبة مسبقًاx3،x5،...،x2ك-1{\displaystyle x^{3},x^{5},...,x^{2^{k}-1}}.
الناتج
العنصر x n ∈ G .

الخوارزمية:

y := 1; i := l - 1 while i > -1 do if n i = 0 then y := y 2 i := i - 1 آخر s := max{i - k + 1, 0} بينما n s = 0، نفّذ s := s + 1 [ ملاحظات 1 ]، من أجل h := 1 إلى i - s + 1، نفّذ y := y 2، u := (n i , n i-1 , ..., n s ) 2 ، y := y * x u i := s - 1 أعد y

أسلوب سلم مونتغمري

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

بالنظر إلى التمثيل الثنائي لعدد صحيح موجب وغير صفري n = ( n k −1 ... n 0 ) 2 حيث n k−1 = 1، يمكننا حساب x n على النحو التالي:

x₁ = x ؛ x₂ = x₂ لـ i = k - 2 إلى 0 إذا كان nᵢ = 0 فإن x₂ = x₁ * x₂ ؛ x₁ = x₁² وإلا فإن x₁ = x₁ * x₂ ؛ x₂ = x₂² أرجع x₁

تُنفّذ الخوارزمية سلسلة ثابتة من العمليات ( حتى لوغاريتم n ): حيث يتم الضرب والتربيع لكل بت في الأس، بغض النظر عن قيمة البت. وتوجد خوارزمية مماثلة للضرب بالمضاعفة.

لا يزال هذا التطبيق المحدد لخوارزمية سلم مونتغمري غير محمي ضد هجمات توقيت الذاكرة المخبئية : إذ قد يظل بإمكان المهاجم ملاحظة زمن استجابة الوصول إلى الذاكرة، حيث يتم الوصول إلى متغيرات مختلفة بناءً على قيمة بتات الأس السري. تستخدم تطبيقات التشفير الحديثة تقنية "التشتيت" لضمان عدم وصول المعالج إلى الذاكرة المخبئية الأسرع. [ 3 ]

الأس ذو القاعدة الثابتة

توجد عدة طرق يمكن استخدامها لحساب x n عندما يكون الأساس ثابتًا والأس متغيرًا. وكما هو واضح، تلعب الحسابات المسبقة دورًا رئيسيًا في هذه الخوارزميات.

أسلوب ياو

تُعتبر طريقة ياو متعامدة مع طريقة 2k - ary حيث يتم توسيع الأس في الأساس b = 2k ويتم الحساب كما هو موضح في الخوارزمية أعلاه. ليكن n و nᵢ و b و bᵢ أعدادًا صحيحة .

لنفترض أن الأس n يُكتب على النحو التالي:

ن=∑أنا=0w-1نأنابأنا،{\displaystyle n=\sum _{i=0}^{w-1}n_{i}b_{i},}

أين0⩽نأنا<ح{\displaystyle 0\leqslant n_{i}<h}للجميعأنا∈[0،w-1]{\displaystyle i\in [0,w-1]}.

ليكن x i = x b i .

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

xن=∏أنا=0w-1xأنانأنا=∏ج=1ح-1[∏نأنا=جxأنا]ج.{\displaystyle x^{n}=\prod _{i=0}^{w-1}x_{i}^{n_{i}}=\prod _{j=1}^{h-1}{\bigg [}\prod _{n_{i}=j}x_{i}{\bigg ]}^{j}.}

بفرض العنصر x من G ، والأس n المكتوب بالشكل أعلاه، بالإضافة إلى القيم المحسوبة مسبقًا x b 0 ... x b w −1 ، يتم حساب العنصر x n باستخدام الخوارزمية أدناه:

y = 1، u = 1، j = h - 1 طالما j > 0، نفّذ من أجل i = 0 إلى w - 1، إذا كان n i = j فإن u = u × x b i ص = ص × ع j = j - 1 أعد y

إذا وضعنا h = 2k و bᵢ = hᵢ ، فإن قيم nᵢ هي ببساطة أرقام n في النظام العددي ذي الأساس h . تجمع طريقة ياو في u أولًا قيم xᵢ التي تظهر عند أعلى قوة .ح-1{\displaystyle h-1}في الجولة التالية، أولئك الذين يملكون السلطةح-2{\displaystyle h-2}يتم تجميعها في u أيضًا، إلخ. يتم ضربالمتغير y .ح-1{\displaystyle h-1}مرات مع u الأولية،ح-2{\displaystyle h-2}مرات مع القوى الأعلى التالية، وهكذا. تستخدم الخوارزميةw+ح-2{\displaystyle w+h-2}الضرب ، وw+1{\displaystyle w+1}يجب تخزين العناصر لحساب x n . [ 1 ]

الطريقة الإقليدية

تم تقديم طريقة إقليدس لأول مرة في كتاب "الأس الفعال باستخدام الحساب المسبق وسلاسل جمع المتجهات" بواسطة PD Rooij.

هذه الطريقة لحسابxن{\displaystyle x^{n}}في المجموعة G ، حيث n عدد صحيح طبيعي، والتي ترد خوارزميتها أدناه، يتم استخدام المساواة التالية بشكل متكرر:

x0ن0⋅x1ن1=(x0⋅x1q)ن0⋅x1ن1مودن0،{\displaystyle x_{0}^{n_{0}}\cdot x_{1}^{n_{1}}=\left(x_{0}\cdot x_{1}^{q}\right)^{n_{0}}\cdot x_{1}^{n_{1}\mod n_{0}},}

أينq=⌊ن1ن0⌋{\displaystyle q=\left\lfloor {\frac {n_{1}}{n_{0}}}\right\rfloor }بمعنى آخر، يتم استخدام القسمة الإقليدية للأس n 1 على n 0 لإرجاع ناتج القسمة q وباقي القسمة n 1 mod n 0 .

بفرض العنصر الأساسي x في المجموعة G ، والأسن{\displaystyle n}مكتوبة كما في طريقة ياو، العنصرxن{\displaystyle x^{n}}يتم حسابها باستخدامل{\displaystyle l}القيم المحسوبة مسبقًاxب0،...،xبلأنا{\displaystyle x^{b_{0}},...,x^{b_{l_{i}}}}ثم الخوارزمية أدناه.

ابدأ البحث عن الحلقةم∈[0،ل-1]{\displaystyle M\in [0,l-1]}بحيث​∀أنا∈[0،ل-1]،نم≥نأنا{\displaystyle \forall i\in [0,l-1],n_{M}\geq n_{i}}. يجدشمال∈([0،ل-1]-م){\displaystyle N\in {\big (}[0,l-1]-M{\big )}}بحيث​∀أنا∈([0،ل-1]-م)،نشمال≥نأنا{\displaystyle \forall i\in {\big (}[0,l-1]-M{\big )},n_{N}\geq n_{i}}. اكسر الحلقة إذانشمال=0{\displaystyle n_{N}=0}. يتركq=⌊نم/نشمال⌋{\displaystyle q=\lfloor n_{M}/n_{N}\rfloor }ثم دع​نشمال=(نممودنشمال){\displaystyle n_{N}=(n_{M}{\bmod {n}}_{N})}. الحساب بشكل متكررxمq{\displaystyle x_{M}^{q}}ثم دع​xشمال=xشمال⋅xمq{\displaystyle x_{N}=x_{N}\cdot x_{M}^{q}} نهاية الحلقة ؛ إرجاعxن=xمنم{\displaystyle x^{n}=x_{M}^{n_{M}}}.

تبدأ الخوارزمية بإيجاد أكبر قيمة بين قيم nᵢ ، ثم القيمة العليا ضمن مجموعة { nᵢ \ i ≠ M } . بعد ذلك ، ترفع xᵢM إلى القوة q ، وتضرب هذه القيمة في xᵢN ، ثم تُسند إلى xᵢN نتيجة هذه العملية الحسابية ، وإلى nᵢM القيمة nᵢM modulo nᵢN .

تطبيقات أخرى

يُمكن تطبيق هذا النهج أيضًا على أنصاف الزمر التي لا تمتلك خاصية الصفر ، مما يسمح، على سبيل المثال، بحساب سريع للأسس الكبيرة بتردد عدد ما. ويُعدّ حساب القوى في حلقة من الأعداد الصحيحة بتردد q مفيدًا بشكل خاص في علم التشفير . على سبيل المثال، تقييم

13789 722341 (موديل 2345) = 2029

سيستغرق الأمر وقتًا طويلاً جدًا ومساحة تخزين كبيرة إذا تم استخدام الطريقة البسيطة لحساب 13789 722341 ثم حساب باقي القسمة على 2345. حتى استخدام طريقة أكثر فعالية سيستغرق وقتًا طويلاً: تربيع 13789، ثم حساب باقي القسمة على 2345، ثم ضرب الناتج في 13789، وهكذا.

بتطبيق خوارزمية الأس بالتربيع المذكورة أعلاه ، مع تفسير "*" على أنها x * y = xy mod 2345 (أي عملية ضرب متبوعة بقسمة مع باقٍ)، ينتج عن ذلك 27 عملية ضرب وقسمة للأعداد الصحيحة فقط، والتي يمكن تخزينها جميعًا في كلمة واحدة من ذاكرة الآلة. عمومًا، تتطلب أي من هذه الطرق أقل من 2log 2 (722340) ≤ 40 عملية ضرب نمطية.

يمكن أيضًا استخدام هذا الأسلوب لحساب قوى الأعداد الصحيحة في مجموعة ، باستخدام أي من القاعدتين التاليتين

Power( x , − n ) = Power( x −1 , n ) ,
Power( x , − n ) = (Power( x , n )) −1 .

يعمل هذا النهج أيضًا في أنصاف المجموعات غير التبادلية ويستخدم غالبًا لحساب قوى المصفوفات .

وبشكل عام، يعمل هذا النهج مع الأسس الصحيحة الموجبة في كل صهارة تكون فيها العملية الثنائية تجميعية للقوى .

إعادة ترميز الأرقام الموقعة

في بعض العمليات الحسابية ، قد يكون من الأنسب السماح بمعاملات سالبة، وبالتالي استخدام معكوس الأساس، شريطة أن يكون المعكوس في G سريعًا أو تم حسابه مسبقًا. على سبيل المثال، عند حساب x²k⁻¹ ، تتطلب الطريقة الثنائية k⁻¹ عملية ضرب و k⁻¹ عملية تربيع . مع ذلك، يمكن إجراء k عملية تربيع للحصول على x²k ، ثم ضرب الناتج في x⁻¹ للحصول على x²k⁻¹ .

ولهذا الغرض، نُعرّف تمثيل الأرقام المُوقّعة لعدد صحيح n في النظام ذي الأساس b على النحو التالي:

ن=∑أنا=0ل-1نأنابأنا مع |نأنا|<ب.{\displaystyle n=\sum _{i=0}^{l-1}n_{i}b^{i}{\text{ with }}|n_{i}|<b.}

يتوافق التمثيل الثنائي الموقّع مع الاختيار المحدد b = 2 ونأنا∈{-1،0،1}{\displaystyle n_{i}\in \{-1,0,1\}}ويرمز إليه بـ(نل-1...ن0)s{\displaystyle (n_{l-1}\dots n_{0})_{s}}توجد عدة طرق لحساب هذا التمثيل. هذا التمثيل ليس فريدًا. على سبيل المثال، إذا أخذنا n = 478 ، فسيتم إعطاء تمثيلين ثنائيين مختلفين مُوَقَّعين.(101¯11001¯10)s{\displaystyle (10{\bar {1}}1100{\bar {1}}10)_{s}}و(1001¯10001¯0)s{\displaystyle (100{\bar {1}}1000{\bar {1}}0)_{s}}، أين1¯{\displaystyle {\bar {1}}}يُستخدم الرمز −1 للدلالة على −1 . بما أن الطريقة الثنائية تحسب عملية ضرب لكل عنصر غير صفري في التمثيل الثنائي للعدد n ، فإننا مهتمون بإيجاد التمثيل الثنائي المُوَقَّع الذي يحتوي على أقل عدد من العناصر غير الصفرية، أي التمثيل ذو أقل وزن هامينغ . إحدى طرق القيام بذلك هي حساب التمثيل في صيغة غير متجاورة ، أو NAF اختصارًا، وهو التمثيل الذي يحقق الشرط التالي:نأنانأنا+1=0 للجميع أنا⩾0{\displaystyle n_{i}n_{i+1}=0{\text{ for all }}i\geqslant 0}ويرمز إليه بـ(نل-1...ن0)القوات الجوية الوطنية{\displaystyle (n_{l-1}\dots n_{0})_{\text{NAF}}}على سبيل المثال، تمثيل NAF للرقم 478 هو(10001¯٠٠٠1¯0)القوات الجوية الوطنية{\displaystyle (1000{\bar {1}}000{\bar {1}}0)_{\text{NAF}}}يتميز هذا التمثيل دائمًا بأقل وزن هامينغ. خوارزمية بسيطة لحساب تمثيل NAF لعدد صحيح مُعطىن=(نلنل-1...ن0)2{\displaystyle n=(n_{l}n_{l-1}\dots n_{0})_{2}}معنل=نل-1=0{\displaystyle n_{l}=n_{l-1}=0}وهو كالتالي:

ج0=0{\displaystyle c_{0}=0} لكل i = 0 إلى l − 1 قم جأنا+1=⌊12(جأنا+نأنا+نأنا+1)⌋{\displaystyle c_{i+1}=\left\lfloor {\frac {1}{2}}(c_{i}+n_{i}+n_{i+1})\right\rfloor }نأنا′=جأنا+نأنا-2جأنا+1{\displaystyle n_{i}'=c_{i}+n_{i}-2c_{i+1}}يعود(نل-1′...ن0′)القوات الجوية الوطنية{\displaystyle (n_{l-1}'\dots n_{0}')_{\text{NAF}}}

خوارزمية أخرى من ابتكار كوياما وتسوروكا لا تتطلب الشرط التالي:نأنا=نأنا+1=0{\displaystyle n_{i}=n_{i+1}=0}; لا يزال يقلل من وزن هامينغ.

البدائل والتعميمات

يمكن اعتبار عملية الرفع إلى الأس بالتربيع خوارزميةً غير مثالية للرفع إلى الأس باستخدام سلسلة الجمع : فهي تحسب الأس من خلال سلسلة جمع تتكون من مضاعفة الأس بشكل متكرر (التربيع) و/أو زيادة الأس بمقدار واحد فقط (الضرب في x ). وبشكل أعم، إذا سمحنا بجمع أي أسس محسوبة مسبقًا (بضرب قوى x هذه )، فيمكننا أحيانًا إجراء عملية الرفع إلى الأس باستخدام عدد أقل من عمليات الضرب (ولكن عادةً باستخدام ذاكرة أكبر). أصغر قوة يحدث عندها هذا هي n = 15.

x15=x×(x×[x×x2]2)2{\displaystyle x^{15}=x\times (x\times [x\times x^{2}]^{2})^{2}}(التربيع، 6 عمليات ضرب)،
x15=x3×([x3]2)2{\displaystyle x^{15}=x^{3}\times ([x^{3}]^{2})^{2}}(سلسلة جمع مثالية، 5 تتضاعف إذا تم إعادة استخدام x 3 ).

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

انظر أيضاً

ملحوظات

  1. ↑ في هذا السطر، تجد الحلقة أطول سلسلة نصية طولها أقل من أو يساوي k وتنتهي بقيمة غير صفرية. لا تشمل جميع القوى الفردية للعدد 2 حتىx2ك-1{\displaystyle x^{2^{k}-1}}يجب حسابها، ولا يلزم النظر إلا في أولئك المشاركين تحديدًا في الحساب.

مراجع

  1. 1 2 كوهين، هـ.؛ فراي، ج.، محرران. (2006). دليل تشفير المنحنيات الإهليلجية والزائدية الإهليلجية . الرياضيات المتقطعة وتطبيقاتها. تشابمان آند هول/سي آر سي. ISBN 9781584885184.
  2. ↑ مونتغمري، بيتر ل. (1987). "تسريع طريقتي بولارد والمنحنى الإهليلجي في التحليل إلى عوامل" (ملف PDF) . الرياضيات والحساب . 48 (177): 243-264 . doi : 10.1090/S0025-5718-1987-0866113-7 .
  3. ↑ جيرون، شاي (5 أبريل 2012). "تطبيقات برمجية فعّالة للأس المعياري" (ملف PDF) . مجلة هندسة التشفير . 2 (1): 31-43 . doi : 10.1007/s13389-012-0031-5 . S2CID 7629541 .