خوارزمية شونهيج-ستراسن

الموسوعة الحرة
تعتمد خوارزمية شونهاج-ستراسن على طريقة تحويل فورييه السريع (FFT) لضرب الأعداد الصحيحة . يوضح هذا الشكل ضرب 1234 × 5678 = 7006652 باستخدام طريقة FFT البسيطة. تم استخدام النظام العشري (الأساس 10) بدلاً من النظام الثنائي (الأساس 2 ) لأغراض التوضيح.
شونهاج (على اليمين) وشتراسن (على اليسار) يلعبان الشطرنج في أوبرولفاخ ، 1979

خوارزمية شونهاج-ستراسن هي خوارزمية ضرب سريعة تقاربياً للأعداد الصحيحة الكبيرة ، نشرها أرنولد شونهاج وفولكر ستراسن عام 1971. [ 1 ] تعمل هذه الخوارزمية عن طريق تطبيق تحويل فورييه السريع (FFT) بشكل متكرر على الأعداد الصحيحة بتردد 0.2ن+1{\displaystyle 2^{n}+1}. التعقيد الزمني للبتات لضرب عددين مكونين من n خانة باستخدام الخوارزمية هويا(ن⋅سجل⁡ن⋅سجل⁡سجل⁡ن){\displaystyle O(n\cdot \log n\cdot \log \log n)}باستخدام ترميز Big O.​

كانت خوارزمية شونهاج-ستراسن أسرع طريقة ضرب معروفة من الناحية التقاربية من عام 1971 حتى عام 2007. وهي أسرع تقاربياً من الطرق الأقدم مثل كاراتسوبا وتوم -كوك ، وتبدأ في التفوق عليها عملياً للأعداد التي تتجاوز 10000 إلى 100000 رقم عشري. [ 2 ] في عام 2007، نشر مارتن فورر خوارزمية ذات تعقيد تقاربي أسرع. [ 3 ] في عام 2019، أثبت ديفيد هارفي وجوريس فان دير هوفن أن ضرب الأعداد متعددة الأرقام له تعقيد نظري أقل من الخوارزمية السابقة.يا(نسجل⁡ن){\displaystyle O(n\log n)}التعقيد؛ ومع ذلك، فإن خوارزميتهم تحتوي على عوامل ثابتة تجعلها بطيئة بشكل لا يمكن تصوره لأي مشكلة عملية (انظر الخوارزمية المجرة ). [ 4 ]

تشمل تطبيقات خوارزمية شونهاج-ستراسن عمليات حسابية ضخمة تُجرى لذاتها، مثل البحث الكبير عن أعداد ميرسين الأولية على الإنترنت وتقريب قيمة π ، بالإضافة إلى تطبيقات عملية مثل تحليل منحنى لينسترا الإهليلجي باستخدام استبدال كرونكر ، الذي يُختزل ضرب كثيرات الحدود إلى ضرب الأعداد الصحيحة. [ 5 ] [ 6 ]

وصف

يحتوي هذا القسم على نسخة مبسطة من الخوارزمية، توضح كيفية حساب الناتجأب{\displaystyle ab}عددان طبيعيانأ،ب{\displaystyle a,b}، modulo عدد من الشكل2ن+1{\displaystyle 2^{n}+1}، أينن=2كم{\displaystyle n=2^{k}M}هو عدد ثابت. الأعداد الصحيحةأ،ب{\displaystyle a,b}سيتم تقسيمها إلىد=2ك{\displaystyle D=2^{k}}كتل منم{\displaystyle M}لذا، في التطبيقات العملية، من المهم تحقيق التوازن الصحيح بين المعايير.م،ك{\displaystyle M,k}على أي حال، ستوفر هذه الخوارزمية طريقة لضرب عددين صحيحين موجبين، بشرطن{\displaystyle n}يتم اختيارها بحيثأب<2ن+1{\displaystyle ab<2^{n}+1}.

يتركن=دم{\displaystyle n=DM}ليكن عدد البتات في الإشاراتأ{\displaystyle a}وب{\displaystyle b}، أيند=2ك{\displaystyle D=2^{k}}هو قوة للعدد اثنين. قسّم الإشاراتأ{\displaystyle a}وب{\displaystyle b}داخلد{\displaystyle D}كتل منم{\displaystyle M}بتات لكل منها، وتخزين الكتل الناتجة كمصفوفاتأ،ب{\displaystyle A,B}(والتي سنعتبر مدخلاتها، تبسيطاً للأمر، أعداداً صحيحة ذات دقة عشوائية).

نختار الآن معيارًا لتحويل فورييه، كما يلي. ليكنم′{\displaystyle M'}أن يكون على هذا النحودم′≥2م+ك{\displaystyle DM'\geq 2M+k}ضع أيضًان′=دم′{\displaystyle n'=DM'}، وانظر إلى عناصر المصفوفاتأ،ب{\displaystyle A,B}كأعداد صحيحة (بدقة اختيارية) بتردد2ن′+1{\displaystyle 2^{n'}+1}لاحظ أنه بما أن2ن′+1≥22م+ك+1=د22م+1{\displaystyle 2^{n'}+1\geq 2^{2M+k}+1=D2^{2M}+1}، المعامل كبير بما يكفي لاستيعاب أي عمليات حمل قد تنتج عن الضرب.أ{\displaystyle a}وب{\displaystyle b}وبالتالي، فإن المنتجأب{\displaystyle ab}(modolo)2ن+1{\displaystyle 2^{n}+1}يمكن حساب ) عن طريق تقييم التفافأ،ب{\displaystyle A,B}أيضًا، معز=22م′{\displaystyle g=2^{2M'}}لدينازد/2≡-1(تعديل2ن′+1){\displaystyle g^{D/2}\equiv -1{\pmod {2^{n'}+1}}}وهكذاز{\displaystyle g}هو بدائيد{\displaystyle D}الجذر النوني للوحدة modulo2ن′+1{\displaystyle 2^{n'}+1}.

نقوم الآن بإجراء تحويل فورييه المنفصل للمصفوفاتأ،ب{\displaystyle A,B}في الحلبةZ/(2ن′+1)Z{\displaystyle \mathbb {Z} /(2^{n'}+1)\mathbb {Z} }باستخدام جذر الوحدةز{\displaystyle g}بالنسبة لأساس فورييه، مما يعطي المصفوفات المحولةأ^،ب^{\displaystyle {\widehat {A}},{\widehat {B}}}. لأند=2ك{\displaystyle D=2^{k}}إذا كان قوة للعدد اثنين، فيمكن تحقيق ذلك في وقت لوغاريتمي باستخدام تحويل فورييه السريع .

يتركج^أنا=أ^أناب^أنا{\displaystyle {\widehat {C}}_{i}={\widehat {A}}_{i}{\widehat {B}}_{i}}(الضرب النقطي)، وحساب التحويل العكسيج{\displaystyle C}من المصفوفةج^{\displaystyle {\widehat {C}}}، باستخدام جذر الوحدة مرة أخرىز{\displaystyle g}المصفوفةج{\displaystyle C}وهي الآن عملية التفاف المصفوفاتأ،ب{\displaystyle A,B}وأخيرًا، المنتجأب(تعديل2ن+1){\displaystyle ab{\pmod {2^{n}+1}}}يتم الحصول على ذلك من خلال تقييم أب≡∑ججج2مجتعديل2ن+1.{\displaystyle ab\equiv \sum _{j}C_{j}2^{Mj}\mod {2^{n}+1}.}

يمكن تحسين هذه الخوارزمية الأساسية بعدة طرق. أولاً، ليس من الضروري تخزين أرقامأ،ب{\displaystyle a,b}بدقة تعسفية، ولكن فقط حتىن′+1{\displaystyle n'+1}البتات، مما يوفر تمثيلاً آلياً أكثر كفاءة للمصفوفاتأ،ب{\displaystyle A,B}ثانيًا، من الواضح أن عمليات الضرب في التحويلات الأمامية هي مجرد إزاحات بتية بسيطة. مع بعض الحذر، يمكن أيضًا حساب التحويل العكسي باستخدام الإزاحات فقط. وبالتالي، مع توخي الحذر، يمكن حذف أي عمليات ضرب حقيقية من الخوارزمية باستثناء حالة الضرب النقطي.ج^أنا=أ^أناب^أنا{\displaystyle {\widehat {C}}_{i}={\widehat {A}}_{i}{\widehat {B}}_{i}}يتم تقييمها. لذلك من المفيد اختيار المعاييرد،م{\displaystyle D,M}بحيث يمكن إجراء هذا الضرب النقطي بكفاءة، إما لأنه كلمة آلة واحدة أو باستخدام خوارزمية مُحسَّنة لضرب الأعداد الصحيحة لعدد (صغير مثاليًا) من الكلمات. اختيار المعلماتد،م{\displaystyle D,M}وبالتالي، يُعد هذا مجالاً مهماً لمزيد من تحسين الطريقة.

تفاصيل

يمكن كتابة كل عدد في النظام العددي (الأساس B) على شكل متعدد الحدود:

X=∑أنا=0شمالxأنابأنا{\displaystyle X=\sum _{i=0}^{N}{x_{i}B^{i}}}

علاوة على ذلك، يمكن اعتبار عملية ضرب عددين بمثابة حاصل ضرب كثيرتي حدود:

XY=(∑أنا=0شمالxأنابأنا)(∑ج=0شمالyأنابج){\displaystyle XY=\left(\sum _{i=0}^{N}{x_{i}B^{i}}\right)\left(\sum _{j=0}^{N}{y_{i}B^{j}}\right)}

لأن، من أجلبك{\displaystyle B^{k}}:جك=∑(أنا،ج):أنا+ج=كأأنابج=∑أنا=0كأأنابك-أنا{\displaystyle c_{k}=\sum _{(i,j):i+j=k}{a_{i}b_{j}}=\sum _{i=0}^{k}{a_{i}b_{ki}}}لدينا تعقيد.

باستخدام تحويل فورييه السريع (FFT )، المستخدم في النسخة الأصلية بدلاً من تحويل نظرية الأعداد (NTT )، [ 7 ] مع قاعدة الالتفاف؛ نحصل على

و^(أ*ب)=و^(∑أنا=0كأأنابك-أنا)=و^(أ)∙و^(ب).{\displaystyle {\hat {f}}(a*b)={\hat {f}}\left(\sum _{i=0}^{k}a_{i}b_{ki}\right)={\hat {f}}(a)\bullet {\hat {f}}(b).}

إنه؛جك=أك∙بك{\displaystyle C_{k}=a_{k}\bullet b_{k}}، أينجك{\displaystyle C_{k}} وهو المعامل المقابل في فضاء فورييه. ويمكن كتابة ذلك أيضاً على النحو التالي:تحويل فورييه السريع(أ*ب)=تحويل فورييه السريع(أ)∙تحويل فورييه السريع(ب){\displaystyle {\text{fft}}(a*b)={\text{fft}}(a)\bullet {\text{fft}}(b)}.

لدينا نفس المعاملات بسبب الخطية تحت تحويل فورييه، ولأن هذه كثيرات الحدود تتكون فقط من حد فريد واحد لكل معامل:

و^(xن)=(أنا2π)ندلتا(ن){\displaystyle {\hat {f}}(x^{n})=\left({\frac {i}{2\pi }}\right)^{n}\delta ^{(n)}} و
و^(أX(ξ)+بY(ξ))=أX^(ξ)+بY^(ξ){\displaystyle {\hat {f}}(a\,X(\xi )+b\,Y(\xi ))=a\,{\hat {X}}(\xi )+b\,{\hat {Y}}(\xi )}

قاعدة الالتفاف:و^(X*Y)= و^(X)∙و^(Y){\displaystyle {\hat {f}}(X*Y)=\ {\hat {f}}(X)\bullet {\hat {f}}(Y)}

لقد قمنا بتحويل مشكلة الالتفاف إلى مشكلة ضرب، من خلال تحويل فورييه السريع (FFT).

عن طريق إيجاد تحويل فورييه السريع للاستيفاء متعدد الحدود لكلجك{\displaystyle C_{k}}، يمكن للمرء تحديد المعاملات المطلوبة.

تستخدم هذه الخوارزمية أسلوب فرق تسد لتقسيم المشكلة إلى مشاكل فرعية.

الالتفاف تحت mod N

جك=∑(أنا،ج):أنا+ج≡ك(تعديلشمال(ن))أأنابج{\displaystyle c_{k}=\sum _{(i,j):i+j\equiv k{\pmod {N(n)}}}a_{i}b_{j}}، أينشمال(ن)=2ن+1{\displaystyle N(n)=2^{n}+1}.

عن طريق السماح بما يلي:

أأنا′=θأناأأنا{\displaystyle a_{i}'=\theta ^{i}a_{i}}وبج′=θجبج،{\displaystyle b_{j}'=\theta ^{j}b_{j},}

أينθشمال=-1{\displaystyle \theta ^{N}=-1}إذا كان الجذر النوني ، فسيتضح ما يلي: [ 8 ]

جك=∑(أنا،ج):أنا+ج≡ك(تعديلشمال(ن))أأنابج=θ-ك∑(أنا،ج):أنا+ج≡ك(تعديلشمال(ن))أأنا′بج′=θ-ك(∑(أنا،ج):أنا+ج=كأأنا′بج′+∑(أنا،ج):أنا+ج=ك+نأأنا′بج′)=θ-ك(∑(أنا،ج):أنا+ج=كأأنابجθك+∑(أنا،ج):أنا+ج=ك+نأأنابجθن+ك)=∑(أنا،ج):أنا+ج=كأأنابج+θن∑(أنا،ج):أنا+ج=ك+نأأنابج.{\displaystyle {\begin{aligned}C_{k}&=\sum _{(i,j):i+j\equiv k{\pmod {N(n)}}}a_{i}b_{j}=\theta ^{-k}\sum _{(i,j):i+j\equiv k{\pmod {N(n)}}}a_{i}'b_{j}'\\[6pt]&=\theta ^{-k}\left(\sum _{(i,j):i+j=k}a_{i}'b_{j}'+\sum _{(i,j):i+j=k+n}a_{i}'b_{j}'\right)\\[6pt]&=\theta ^{-k}\left(\sum _{(i,j):i+j=k}a_{i}b_{j}\theta ^{k}+\sum _{(i,j):i+j=k+n}a_{i}b_{j}\theta ^{n+k}\right)\\[6pt]&=\sum _{(i,j):i+j=k}a_{i}b_{j}+\theta ^{n}\sum _{(i,j):i+j=k+n}a_{i}b_{j}.\end{aligned}}}

وهذا يعني أنه يمكن للمرء استخدام الوزنθأنا{\displaystyle \theta ^{i}}ثم اضرب فيθ-ك{\displaystyle \theta ^{-k}}بعد.

بدلاً من استخدام الوزن، كماθشمال=-1{\displaystyle \theta ^{N}=-1}، في الخطوة الأولى من الاستدعاء الذاتي (عندمان=شمال{\displaystyle n=N}، ويمكن حساب ما يلي:

جك=∑(أنا،ج):أنا+ج≡ك(تعديلشمال(شمال))=∑(أنا،ج):أنا+ج=كأأنابج-∑(أنا،ج):أنا+ج=ك+نأأنابج{\displaystyle C_{k}=\sum _{(i,j):i+j\equiv k{\pmod {N(N)}}}=\sum _{(i,j):i+j=k}a_{i}b_{j}-\sum _{(i,j):i+j=k+n}a_{i}b_{j}}

في خوارزمية تحويل فورييه السريع العادية التي تعمل على الأعداد المركبة، يمكن استخدام ما يلي:

خبرة⁡(2كπأنان)=كوس⁡2كπن+أناالخطيئة⁡2كπن،ك=0،1،...،ن-1.{\displaystyle \exp \left({\frac {2k\pi i}{n}}\right)=\cos {\frac {2k\pi }{n}}+i\sin {\frac {2k\pi }{n}},\qquad k=0,1,\dots ,n-1.}
جك=θ-ك(∑(أنا،ج):أنا+ج=كأأنابجθك+∑(أنا،ج):أنا+ج=ك+نأأنابجθن+ك)=هـ-أنا2πك/ن(∑(أنا،ج):أنا+ج=كأأنابجهـأنا2πك/ن+∑(أنا،ج):أنا+ج=ك+نأأنابجهـأنا2π(ن+ك)/ن){\displaystyle {\begin{aligned}C_{k}&=\theta ^{-k}\left(\sum _{(i,j):i+j=k}a_{i}b_{j}\theta ^{k}+\sum _{(i,j):i+j=k+n}a_{i}b_{j}\theta ^{n+k}\right)\\[6pt]&=e^{-i2\pi k/n}\left(\sum _{(i,j):i+j=k}a_{i}b_{j}e^{i2\pi k/n}+\sum _{(i,j):i+j=k+n}a_{i}b_{j}e^{i2\pi (n+k)/n}\right)\end{aligned}}}

مع ذلك، يمكن استخدام تحويل فورييه السريع (FFT) أيضًا كتحويل نظري للأعداد (NTT ) في نظرية شونهاج-ستراسن. هذا يعني أنه يتعين علينا استخدام θ لتوليد الأعداد في حقل منتهٍ (على سبيل المثال،جيF(2ن+1){\displaystyle \mathrm {GF} (2^{n}+1)}).

جذر الوحدة تحت حقل منتهٍ GF( r ) هو عنصر a بحيثθر-1≡1{\displaystyle \theta ^{r-1}\equiv 1}أوθر≡θ{\displaystyle \theta ^{r}\equiv \theta }على سبيل المثال، تعطي GF( p ) ، حيث p عدد أولي ،{1،2،...،ص-1}{\displaystyle \{1,2,\ldots ,p-1\}}.

لاحظ أن2ن≡-1{\displaystyle 2^{n}\equiv -1}فيجي إف⁡(2ن+1){\displaystyle \operatorname {GF} (2^{n}+1)} و2≡-1{\displaystyle {\sqrt {2}}\equiv -1}فيجي إف⁡(2ن+2+1){\displaystyle \operatorname {GF} (2^{n+2}+1)}بالنسبة لهؤلاء المرشحين،θشمال≡-1{\displaystyle \theta ^{N}\equiv -1}في ظل مجالها المحدود، وبالتالي نتصرف بالطريقة التي نريدها.

ومع ذلك، لا يزال من الممكن استخدام نفس خوارزميات FFT، طالما أن θ هو جذر الوحدة لحقل منتهٍ.

لإيجاد تحويل FFT/NTT، نقوم بما يلي:

جك′=و^(ك)=و^(θ-ك(∑(أنا،ج):أنا+ج=كأأنابجθك+∑(أنا،ج):أنا+ج=ك+نأأنابجθن+ك))جك+ك′=و^(ك+ك)=و^(∑(أنا،ج):أنا+ج=2كأأنابجθك+∑(أنا،ج):أنا+ج=ن+2كأأنابجθن+ك)=و^(∑(أنا،ج):أنا+ج=2كأأنابجθك+∑(أنا،ج):أنا+ج=2ك+نأأنابجθن+ك)=و^(أك←ك)∙و^(بك←ك)+و^(أك←ك+ن)∙و^(بك←ك+ن){\displaystyle {\begin{aligned}C_{k}'&={\hat {f}}(k)={\hat {f}}\left(\theta ^{-k}\left(\sum _{(i,j):i+j=k}a_{i}b_{j}\theta ^{k}+\sum _{(i,j):i+j=k+n}a_{i}b_{j}\theta ^{n+k}\right)\right)\\[6pt]C_{k+k}'&={\hat {f}}(k+k)={\hat {f}}\left(\sum _{(i,j):i+j=2k}a_{i}b_{j}\theta ^{k}+\sum _{(i,j):i+j=n+2k}a_{i}b_{j}\theta ^{n+k}\right)\\[6pt]&={\hat {f}}\left(\sum _{(i,j):i+j=2k}a_{i}b_{j}\theta ^{k}+\sum _{(i,j):i+j=2k+n}a_{i}b_{j}\theta ^{n+k}\right)\\[6pt]&={\hat {f}}\left(A_{k\leftarrow k}\right)\bullet {\hat {f}}(B_{k\leftarrow k})+{\hat {f}}(A_{k\leftarrow k+n})\bullet {\hat {f}}(B_{k\leftarrow k+n})\end{aligned}}}

المنتج الأول يساهم فيجك{\displaystyle c_{k}}لكل قيمة k . ثانياً، يُساهم فيجك{\displaystyle c_{k}}، بسبب(أنا+ج){\displaystyle (i+j)}تعديلشمال(ن){\displaystyle N(n)}.

للقيام بالعكس:

جك=2-مو-1^(θ-كجك+ك′){\displaystyle C_{k}=2^{-m}{\hat {f^{-1}}}(\theta ^{-k}C_{k+k}')}أوجك=و-1^(θ-كجك+ك′){\displaystyle C_{k}={\hat {f^{-1}}}(\theta ^{-k}C_{k+k}')}

وذلك بحسب ما إذا كانت البيانات بحاجة إلى تطبيع.

واحد يضرب في2-م{\displaystyle 2^{-m}}لتطبيع بيانات تحويل فورييه السريع (FFT) ضمن نطاق محدد، حيث1ن≡2-متعديلشمال(ن){\displaystyle {\frac {1}{n}}\equiv 2^{-m}{\bmod {N}}(n)}، حيث يتم إيجاد m باستخدام المعكوس الضربي المعياري .

تفاصيل التنفيذ

لماذا N = 2M + 1 mod N

في خوارزمية Schönhage-Strassen،شمال=2م+1{\displaystyle N=2^{M}+1}ينبغي اعتبار هذا بمثابة شجرة ثنائية ، حيث توجد القيم في0≤فِهرِس≤2م=2أنا+ج{\displaystyle 0\leq {\text{index}}\leq 2^{M}=2^{i+j}}عن طريق السماحك∈[0،م]{\displaystyle K\in [0,M]}، لكل قيمة K يمكن إيجاد جميعأنا+ج=ك{\displaystyle i+j=K}، وجمع كل(أنا،ج){\displaystyle (i,j)}قم بتقسيم الأزواج إلى M مجموعات مختلفة. باستخدامأنا+ج=ك{\displaystyle i+j=k}إلى مجموعة(أنا،ج){\displaystyle (i,j)}يُعدّ تحويل الأزواج عبر الالتفاف مشكلة كلاسيكية في الخوارزميات. [ 9 ]

مع أخذ هذا في الاعتبار،شمال=2م+1{\displaystyle N=2^{M}+1}ساعدنا في التجميع(أنا،ج){\displaystyle (i,j)}داخلم2ك{\displaystyle {\frac {M}{2^{k}}}}مجموعات لكل مجموعة من المهام الفرعية في العمق k في شجرة معشمال=2م2ك+1{\displaystyle N=2^{\frac {M}{2^{k}}}+1}

لاحظ أنشمال=2م+1=22ل+1{\displaystyle N=2^{M}+1=2^{2^{L}}+1}بالنسبة لبعض قيم L، فإن هذا يجعل N عددًا فيرما . عند إجراء عملية حسابية modشمال=2م+1=22ل+1{\displaystyle N=2^{M}+1=2^{2^{L}}+1}لدينا حلقة فيرما.

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

هناك قيم أخرى لـ N كان من الممكن استخدامها، بالطبع، مع نفس مزايا الأعداد الأولية. وذلك بتركشمال=2ك-1{\displaystyle N=2^{k}-1}، يمكن للمرء أن يمتلك أكبر عدد في نظام العد الثنائي معك+1{\displaystyle k+1}أجزاء. شمال=2ك-1{\displaystyle N=2^{k}-1}هو عدد ميرسين، وفي بعض الحالات يكون عددًا أوليًا من أعداد ميرسين. وهو مرشح طبيعي لمنافسة عدد فيرما.شمال=22ل+1{\displaystyle N=2^{2^{L}}+1}

بحثاً عن حرف N آخر

إجراء عدة عمليات حسابية باستخدام باقي القسمة على قيم N مختلفة قد يكون مفيدًا عند حل مسألة الضرب الصحيح. باستخدام نظرية الباقي الصينية ، وبعد تقسيم M إلى أنواع أصغر مختلفة من N ، يمكن إيجاد ناتج عملية الضرب xy [ 10 ].

أعداد فيرما وأعداد ميرسين هي مجرد نوعين من الأعداد، في شيء يسمى عدد فيرما ميرسين المعمم (GSM)؛ مع الصيغة: [ 11 ]

جيq،ص،ن=∑أنا=1صq(ص-أنا)ن=qصن-1qن-1{\displaystyle G_{q,p,n}=\sum _{i=1}^{p}q^{(p-i)n}={\frac {q^{pn}-1}{q^{n}-1}}}
مص،ن=جي2،ص،ن{\displaystyle M_{p,n}=G_{2,p,n}}

في هذه الصيغة،م2،2ك{\displaystyle M_{2,2^{k}}}هو عدد فيرما، ومص،1{\displaystyle M_{p,1}}هو عدد ميرسين.

يمكن استخدام هذه الصيغة لتوليد مجموعات من المعادلات، والتي يمكن استخدامها في نظرية الباقي الصينية (CRT): [ 12 ]

ز(مص،ن-1)2≡-1(تعديلمص،ن){\displaystyle g^{\frac {(M_{p,n}-1)}{2}}\equiv -1{\pmod {M_{p,n}}}}حيث g عدد بحيث يوجد x حيث x2≡ز(تعديلمص،ن){\displaystyle x^{2}\equiv g{\pmod {M_{p,n}}}}، بافتراضشمال=2ن{\displaystyle N=2^{n}}

بالإضافة إلى؛ز2(ص-1)ن-1≡أ2ن-1(تعديلمص،ن){\displaystyle g^{2^{(p-1)n}-1}\equiv a^{2^{n}-1}{\pmod {M_{p,n}}}}، حيث يمثل a عنصرًا يُولّد عناصر في{1،2،4،..0.2ن-1،2ن}{\displaystyle \{1,2,4,...2^{n-1},2^{n}\}}بطريقة دورية.

لوشمال=2ت{\displaystyle N=2^{t}}، أين1≤ت≤ن{\displaystyle 1\leq t\leq n}، ثمزت=أ(2ن-1)2ن-ت{\displaystyle g_{t}=a^{(2^{n}-1)2^{n-t}}}.

كيفية اختيار قيمة K لقيمة N محددة

الصيغة التالية مفيدة لإيجاد قيمة K المناسبة (عدد المجموعات التي يتم تقسيم N بت إليها) مع حجم البت N عن طريق حساب الكفاءة  : [ 13 ]

هـ=2شمالك+كن{\displaystyle E={\frac {{\frac {2N}{K}}+k}{n}}}N هو حجم البت (المستخدم في2شمال+1{\displaystyle 2^{N}+1}) في المستوى الخارجي. K يعطيشمالك{\displaystyle {\frac {N}{K}}}مجموعات من البتات، حيثك=2ك{\displaystyle K=2^{k}}.

يتم إيجاد قيمة n من خلال N و K و k عن طريق إيجاد أصغر قيمة لـ x ، بحيث 2شمال/ك+ك≤ن=ك2x{\displaystyle 2N/K+k\leq n=K2^{x}}

إذا افترضنا كفاءة تزيد عن 50%،ن2≤2شمالك،ك≤ن{\displaystyle {\frac {n}{2}}\leq {\frac {2N}{K}},K\leq n}و k صغيرة جدًا مقارنة ببقية الصيغة؛ يحصل المرء على

ك≤2شمال{\displaystyle K\leq 2{\sqrt {N}}}

هذا يعني: عندما يكون شيء ما فعالاً للغاية، فإن قيمة K تكون محدودة من الأعلى بواسطة2شمال{\displaystyle 2{\sqrt {N}}}أو مقيدة تقاربياً من الأعلى بواسطةشمال{\displaystyle {\sqrt {N}}}

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

يمكن الاطلاع على خوارزمية الضرب المعيارية لـ Schönhage-Strassen (مع بعض التحسينات) في نظرة عامة من خلال [ 14 ].

  1. قسّم كلا العددين المدخلين a و b إلى n معاملًا، كل منها مكون من s بت. استخدم على الأقلك+1{\displaystyle K+1}بتات لتخزينها، للسماح بتشفير القيمة2ك.{\displaystyle 2^{K}.}⁠
  2. قم بترجيح متجهي المعاملات وفقًا لـ (2.24) بقوى θ عن طريق إجراء تحولات دورية عليهما.
  3. قم بتبديل المعاملاتأأنا{\displaystyle a_{i}}و​​بج{\displaystyle b_{j}}⁠ .
  4. التقييم​أأنا{\displaystyle a_{i}}و​​بج{\displaystyle b_{j}}. عمليات الضرب بقوى ω هي إزاحات دورية.
  5. قم بإجراء عمليات الضرب النقطيجك:=أكبك{\displaystyle c_{k}:=a_{k}b_{k}}في​​Z/(2ك+1)Z{\displaystyle Z/(2^{K}+1)Z}إذا تم استخدام SMUL بشكل متكرر، فقم بتوفير K كمعامل. وإلا، فاستخدم دالة ضرب أخرى مثل T3MUL وقم بالاختزال باستخدام باقي القسمة .2ك+1{\displaystyle 2^{K}+1}بعد ذلك.
  6. قم بخلط معاملات الضربجك{\displaystyle c_{k}}⁠ .
  7. احسب معاملات الضرب ⁠جك{\displaystyle c_{k}}⁠ .
  8. قم بتطبيق الأثقال الموازنة علىجك{\displaystyle c_{k}}وفقًا لـ (2.25). بما أنθ2ن≡1{\displaystyle \theta ^{2n}\equiv 1}ويترتب على ذلك θ-ك≡θن-ك{\displaystyle \theta ^{-k}\equiv \theta ^{n-k}}⁠
  9. قم بتطبيع ⁠جك{\displaystyle c_{k}}مع​​1/ن≡2-م{\displaystyle 1/n\equiv 2^{-m}}( مرة أخرى تحول دوري).
  10. اجمع​جك{\displaystyle c_{k}}ثم قم بنشر عمليات الحمل. تأكد من التعامل مع المعاملات السالبة بشكل صحيح.
  11. قم بإجراء عملية اختزال modulo2شمال+1{\displaystyle 2^{N}+1}⁠ .
  • T3MUL = ضرب توم-كوك
  • SMUL = ضرب شونهاج-ستراسين
  • التقييم = FFT/IFFT

دراسة إضافية

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

التحسينات

يشرح هذا القسم عددًا من التحسينات العملية المهمة عند تطبيق Schönhage–Strassen.

استخدام خوارزمية ضرب أخرى، داخل الخوارزمية

عند تجاوز نقطة قطع معينة، يكون من الأفضل استخدام خوارزميات ضرب أخرى، مثل ضرب توم-كوك . [ 17 ]

خدعة الجذر التربيعي للعدد 2

الفكرة هي استخدام2{\displaystyle {\sqrt {2}}}كجذر لوحدة النظام2ن+2{\displaystyle 2^{n+2}}في حقل منتهٍجيF(2ن+2+1){\displaystyle \mathrm {GF} (2^{n+2}+1)}(إنه حل للمعادلة)θ2ن+2≡1(تعديل2ن+2+1){\displaystyle \theta ^{2^{n+2}}\equiv 1{\pmod {2^{n+2}+1}}}عند ترجيح القيم في نهج التحويل النظري للأعداد (NTT)، فقد ثبت أنه يوفر 10% من وقت ضرب الأعداد الصحيحة. [ 18 ]

خدعة غرانلوند

عن طريق السماحم=شمال+ح{\displaystyle m=N+h}يمكن للمرء أن يحسب uvتعديل2شمال+1{\displaystyle uv{\bmod {2^{N}+1}}}و(uتعديل2ح)(vتعديل2ح){\displaystyle (u{\bmod {2^{h}}})(v{\bmod {2}}^{h})}بالاشتراك مع نظرية الباقي الصينية (CRT) لإيجاد القيم الدقيقة لعملية الضرب uv . [ 19 ]

مراجع

  1. ^ شونهاج، أرنولد ؛ ستراسن ، فولكر (1971). "Schnelle Multiplikation großer Zahlen" [ الضرب السريع للأعداد الكبيرة ] . الحوسبة (باللغة الألمانية). 7 ( 3– 4): 281– 292. دوى : 10.1007/BF02242355 . S2CID 9738629 . 
  2. ↑ يبلغ التعقيد التقاربي لعملية الضرب في كاراتسوبا حوالييا(ن1.58){\displaystyle O(n^{1.58})}وتبلغ التعقيدية التقاربية لعملية الضرب وفقًا لـ Toom-Cook حوالييا(ن1.46).{\displaystyle O(n^{1.46}).}
    فان ميتر، رودني؛ إيتوه، كوهي م. (2005). "الأسية المعيارية الكمومية السريعة". مجلة Physical Review . 71 (5) 052320. arXiv : quant-ph/0408006 . Bibcode : 2005PhRvA..71e2320V . doi : 10.1103/PhysRevA.71.052320 . S2CID 14983569 . 
    يمكن الاطلاع على مناقشة نقاط التقاطع العملية بين مختلف الخوارزميات في: نظرة عامة على ميزات Magma V2.9، قسم العمليات الحسابية. مؤرشف بتاريخ 20 أغسطس 2006 على موقع Wayback Machine.
    لويس كارلوس كورونادو غارسيا، " هل يمكن لعملية الضرب في نظام شونهاج تسريع تشفير أو فك تشفير RSA؟ مؤرشف "، جامعة دارمشتات للتكنولوجيا (2005)
    تستخدم مكتبة GNU Multi-Precision هذه الطريقة لقيم تتراوح بين 1728 و7808 كلمة 64 بت (33000 إلى 150000 رقم عشري)، وذلك حسب بنية النظام. انظر:
    "ضرب تحويل فورييه السريع (GNU MP 6.2.1)" . gmplib.org . تم الاطلاع عليه بتاريخ 20 يوليو 2021 .
    "MUL_FFT_THRESHOLD" . ركن مطوري GMP . مؤرشف من الأصل بتاريخ 24 نوفمبر 2010. تم الاطلاع عليه بتاريخ 3 نوفمبر 2011 .
    "MUL_FFT_THRESHOLD" . gmplib.org . تم الاطلاع عليه بتاريخ 20 يوليو 2021 .
  3. ↑ خوارزمية فورر لها تعقيد تقاربييا(ن⋅سجل⁡ن⋅2Θ(سجل*⁡ن)).{\textstyle O{\bigl (}n\cdot \log n\cdot 2^{\Theta (\log ^{*}n)}{\bigr )}.}
    فورر، مارتن (2007). "ضرب الأعداد الصحيحة بشكل أسرع" (ملف PDF) . وقائع مؤتمر STOC '07 . ندوة نظرية الحوسبة، سان دييغو، يونيو 2007. الصفحات 57-66 . مؤرشف (ملف PDF) من النسخة الأصلية بتاريخ 5 مارس 2007. تاريخ الاسترجاع: 2 أكتوبر 2007 . 
    فورر، مارتن (2009). "ضرب الأعداد الصحيحة بشكل أسرع". مجلة SIAM للحوسبة . 39 (3): 979-1005 . doi : 10.1137/070711761 . ISSN 0097-5397 . 
    تُستخدم خوارزمية فورر في مكتبة البرامج الفرعية للجبر متعدد الحدود الأساسية (BPAS) مفتوحة المصدر. انظر: كوفانوف، سفياتوسلاف؛ مهاجراني، داوود؛ مورينو مازا، مارك؛ وانغ، لينشياو (8 يوليو 2019). "تحويل فورييه السريع لحقل الأعداد الأولية الكبيرة على المعالجات متعددة النوى" . وقائع الندوة الدولية لعام 2019 حول الحساب الرمزي والجبري (ملف PDF) . بكين، الصين: ACM. الصفحات 106-113 . doi : 10.1145/3326229.3326273 . ISBN  978-1-4503-6084-5. S2CID 195848601 . 
  4. ^ هارفي ، ديفيد. فان دير هوفن، يوريس (2021). "ضرب الأعداد الصحيحة في الوقت المناسبيا(نسجل⁡ن){\displaystyle O(n\log n)}( ملف PDF) . حوليات الرياضيات . السلسلة الثانية. 193 (2): 563-617 . doi : 10.4007/annals.2021.193.2.4 . MR 4224716. S2CID 109934776 .  
  5. ↑ تُستخدم هذه الطريقة في مكتبة إدارة المحتوى الإلكتروني (ECM) التابعة لمعهد INRIA .
  6. ↑ "ECMNET" . members.loria.fr . تم الاطلاع عليه بتاريخ 2023-04-09 .
  7. ↑ بيكر، هانو؛ هوانغ، فينسنت؛ ج. كانويشر، ماتياس؛ باني، لورنز (2022). "الضرب الفعال للأعداد الصحيحة الصغيرة نوعًا ما باستخدام التحويلات النظرية للأعداد" (PDF) .
  8. ↑ لودرز، كريستوف (2014). "الضرب السريع للأعداد الصحيحة الكبيرة: تطبيق وتحليل خوارزمية DKSS" . ص 26. 
  9. ^ كلاينبرج ، جون. تاردوس، إيفا (2005). تصميم الخوارزمية (1 ed.). بيرسون. ص. 237. ردمك   0-321-29535-8.
  10. ^ جودري ، بيريك. ألكسندر، كروبا؛ بول زيمرمان (2007). “تطبيق قائم على GMP لخوارزمية مضاعفة الأعداد الصحيحة الكبيرة لـ Schönhage-Strassen” (PDF) . ص. 6. 
  11. ↑ إس. ديميتروف، فاسيل؛ في. كوكليف، تودور؛ دي. دونيفسكي، بوريسلاف (1994). "تحويل فيرما-ميرسين المعمم لنظرية الأعداد" . ص 2. 
  12. ↑ إس. ديميتروف، فاسيل؛ في. كوكليف، تودور؛ دي. دونيفسكي، بوريسلاف (1994). "تحويل فيرما-ميرسين المعمم لنظرية الأعداد" . ص 3. 
  13. ^ جودري ، بيريك. كروبا، الكسندر؛ زيمرمان، بول (2007). “التنفيذ القائم على GMP لخوارزمية مضاعفة الأعداد الصحيحة الكبيرة لـ Schönhage-Strassen” (PDF) . ص. 2. 
  14. ↑ لودرز، كريستوف (2014). "الضرب السريع للأعداد الصحيحة الكبيرة: تطبيق وتحليل خوارزمية DKSS" . ص 28. 
  15. ↑ ر. كراندال و س. بوميرانس. الأعداد الأولية - منظور حسابي . الطبعة الثانية، سبرينغر، 2005. القسم 9.5.6: طريقة شونهاج، ص 502. ISBN 0-387-94777-9
  16. ↑ كنوت، دونالد إي. (1997). "القسم 4.3.3.ج: تحويلات فورييه المنفصلة" . فن برمجة الحاسوب . المجلد 2: الخوارزميات شبه العددية ( الطبعة الثالثة). أديسون-ويسلي. الصفحات 305-311 . ISBN    0-201-89684-2.
  17. ^ جودري ، بيريك. كروبا، الكسندر؛ زيمرمان، بول (2007). “تطبيق قائم على GMP لخوارزمية مضاعفة الأعداد الصحيحة الكبيرة لـ Schönhage-Strassen” (PDF) . ص. 7. 
  18. ^ جودري ، بيريك. كروبا، الكسندر؛ زيمرمان، بول (2007). “تطبيق قائم على GMP لخوارزمية مضاعفة الأعداد الصحيحة الكبيرة لـ Schönhage-Strassen” (PDF) . ص. 6. 
  19. ^ جودري ، بيريك. كروبا، الكسندر؛ زيمرمان، بول (2007). “تطبيق قائم على GMP لخوارزمية مضاعفة الأعداد الصحيحة الكبيرة لـ Schönhage-Strassen” (PDF) . ص. 6.