خوارزمية تونيللي-شانكس

تُستخدم خوارزمية تونيللي-شانكس (التي أشار إليها شانكس باسم خوارزمية RESSOL) في الحساب النمطي لحل r في تطابق من الشكل r ² ≡ n (mod p )، حيث p عدد أولي : أي لإيجاد الجذر التربيعي لـ n modulo p .

لا يمكن استخدام خوارزمية تونيللي-شانكس للأعداد المركبة: فإيجاد الجذور التربيعية للأعداد المركبة هو مشكلة حسابية مكافئة لتحليل الأعداد الصحيحة إلى عواملها الأولية . ^{[ 1 ]}

قام ألبرتو تونيللي ^{[ 2 ] [ 3 ]} بتطوير نسخة مكافئة، ولكنها أكثر تكرارًا بعض الشيء، من هذه الخوارزمية في عام 1891. أما النسخة التي نناقشها هنا فقد طورها دانيال شانكس بشكل مستقل في عام 1973، والذي أوضح ما يلي:

كان تأخري في معرفة هذه المراجع التاريخية بسبب إعارتي المجلد الأول من كتاب ديكسون التاريخي لصديق ولم يُعاد إليّ أبداً. ^{[ 4 ]}

وفقًا لديكسون، ^{[ 3 ]} يمكن لخوارزمية تونيللي أن تأخذ الجذور التربيعية لـ x modulo القوى الأولية p ^λ بصرف النظر عن الأعداد الأولية.

بافتراض قيمة غير صفرية${\displaystyle n}$ورئيس الوزراء${\displaystyle p>2}$(وهو ما سيكون دائمًا فرديًا)، يخبرنا معيار أويلر أن${\displaystyle n}$له جذر تربيعي (أي،${\displaystyle n}$(يكون الباقي من الدرجة الثانية ) إذا وفقط إذا :

${\displaystyle n^{\frac {p-1}{2}}\equiv 1{\pmod {p}}}$.

في المقابل، إذا كان الرقم${\displaystyle z}$ليس له جذر تربيعي (ليس باقياً)، ويخبرنا معيار أويلر بذلك:

${\displaystyle z^{\frac {p-1}{2}}\equiv -1{\pmod {p}}}$.

ليس من الصعب العثور على مثل هذا${\displaystyle z}$لأن نصف الأعداد الصحيحة بين 1 و${\displaystyle p-1}$يمتلك هذه الخاصية. لذلك نفترض أن لدينا إمكانية الوصول إلى مثل هذه البقايا غير المتبقية.

من خلال القسمة (عادةً) على 2 بشكل متكرر، يمكننا كتابة${\displaystyle p-1}$مثل${\displaystyle Q2^{S}}$، أين${\displaystyle Q}$هذا غريب. لاحظ أنه إذا حاولنا

${\displaystyle R\equiv n^{\frac {Q+1}{2}}{\pmod {p}}}$،

ثم${\displaystyle R^{2}\equiv n^{Q+1}=(n)(n^{Q}){\pmod {p}}}$. لو${\displaystyle t\equiv n^{Q}\equiv 1{\pmod {p}}}$، ثم${\displaystyle R}$هو الجذر التربيعي لـ${\displaystyle n}$وإلا، لـ${\displaystyle M=S}$لدينا${\displaystyle R}$و${\displaystyle t}$مُرضٍ:

• ${\displaystyle R^{2}\equiv nt{\pmod {p}}}$؛ و
• ${\displaystyle t}$هو${\displaystyle 2^{M-1}}$الجذر النوني للعدد 1 (لأن${\displaystyle t^{2^{M-1}}=t^{2^{S-1}}\equiv n^{Q2^{S-1}}=n^{\frac {p-1}{2}}}$).

إذا أُتيحت لنا خيارات${\displaystyle R}$و${\displaystyle t}$لشيء معين${\displaystyle M}$استيفاء ما سبق (حيث${\displaystyle R}$ليس الجذر التربيعي لـ${\displaystyle n}$)، يمكننا بسهولة حساب آخر${\displaystyle R}$و${\displaystyle t}$ل${\displaystyle M-1}$بحيث تتحقق العلاقات المذكورة أعلاه، يمكننا تكرار ذلك حتى${\displaystyle t}$يصبح${\displaystyle 2^{0}}$الجذر النوني للعدد 1، أي${\displaystyle t=1}$عند تلك النقطة${\displaystyle R}$هو الجذر التربيعي لـ${\displaystyle n}$.

يمكننا التحقق مما إذا${\displaystyle t}$هو${\displaystyle 2^{M-2}}$الجذر النوني للعدد 1 عن طريق تربيعه${\displaystyle M-2}$كرر العملية عدة مرات وتحقق مما إذا كانت النتيجة 1. إذا كانت كذلك، فلا داعي للقيام بأي شيء، لأن نفس الخيار${\displaystyle R}$و${\displaystyle t}$ينجح الأمر. ولكن إن لم ينجح،${\displaystyle t^{2^{M-2}}}$يجب أن يكون الناتج -1 (لأن تربيعه يعطي 1، ولا يمكن أن يكون هناك سوى جذرين تربيعيين للعدد 1، وهما 1 و-1 بتردد 1).${\displaystyle p}$).

للعثور على زوج جديد من${\displaystyle R}$و${\displaystyle t}$يمكننا أن نضرب${\displaystyle R}$بمعامل${\displaystyle b}$سيتم تحديده لاحقاً.${\displaystyle t}$يجب ضربها بعامل${\displaystyle b^{2}}$للحفاظ على${\displaystyle R^{2}\equiv nt{\pmod {p}}}$إذن، عندما${\displaystyle t^{2^{M-2}}}$إذا كانت القيمة -1، فنحن بحاجة إلى إيجاد عامل${\displaystyle b^{2}}$لهذا السبب.${\displaystyle tb^{2}}$هو${\displaystyle 2^{M-2}}$الجذر النوني للعدد 1، أو ما يعادله${\displaystyle b^{2}}$هو${\displaystyle 2^{M-2}}$الجذر النوني للعدد -1.

يكمن السر هنا في الاستفادة من${\displaystyle z}$، البقايا غير المعروفة. معيار أويلر المطبق على${\displaystyle z}$يوضح ما سبق أن${\displaystyle z^{Q}}$هو${\displaystyle 2^{S-1}}$الجذر النوني للعدد -1. لذا، بتربيع${\displaystyle z^{Q}}$بشكل متكرر، نتمكن من الوصول إلى سلسلة من${\displaystyle 2^{i}}$الجذور النونية للعدد -1. يمكننا اختيار الجذر المناسب ليكون بمثابة الجذر النوني للعدد -1.${\displaystyle b}$مع القليل من الصيانة المتغيرة وضغط الحالات البسيط، تظهر الخوارزمية أدناه بشكل طبيعي.

العمليات والمقارنات على عناصر المجموعة الضربية للأعداد الصحيحة بتردد p${\displaystyle \mathbb {Z} /p\mathbb {Z} }$هي ضمنيًا mod p .

المدخلات :

• p ، عدد أولي
• ن ، عنصر من${\displaystyle \mathbb {Z} /p\mathbb {Z} }$بحيث توجد حلول للتطابق r ² = n ؛ عندما يكون هذا صحيحًا نقول أن n هو باقي تربيعي modulo p .

المخرجات :

• r in${\displaystyle \mathbb {Z} /p\mathbb {Z} }$بحيث يكون r ² = n

الخوارزمية :

1. بتحليل قوى العدد 2، أوجد قيمتي Q و S بحيث${\displaystyle p-1=Q2^{S}}$مع Q فردي
2. ابحث عن حرف z في${\displaystyle \mathbb {Z} /p\mathbb {Z} }$وهو عبارة عن باقي تربيعي
   • نصف العناصر في المجموعة ستكون عناصر غير متبقية تربيعية
   • يمكن اختبار المرشحين باستخدام معيار أويلر أو عن طريق إيجاد رمز جاكوبي
3. يترك

   ${\displaystyle {\begin{aligned}M&\leftarrow S\\c&\leftarrow z^{Q}\\t&\leftarrow n^{Q}\\R&\leftarrow n^{\frac {Q+1}{2}}\end{aligned}}}$

4. حلقة:
   • إذا كانت قيمة t تساوي صفرًا، فأرجع قيمة r تساوي صفرًا.
   • إذا كانت قيمة t تساوي 1، فأرجع r = R
   • وإلا، استخدم التربيع المتكرر لإيجاد أصغر قيمة لـ i ، حيث 0 < i < M ، بحيث${\displaystyle t^{2^{i}}=1}$
   • يترك${\displaystyle b\leftarrow c^{2^{M-i-1}}}$، وضبط

     ${\displaystyle {\begin{aligned}M&\leftarrow i\\c&\leftarrow b^{2}\\t&\leftarrow tb^{2}\\R&\leftarrow Rb\end{aligned}}}$

بعد حل مسألة التطابق مع r، يكون الحل الثاني هو${\displaystyle -r{\pmod {p}}}$إذا كان أصغر i بحيث${\displaystyle t^{2^{i}}=1}$إذا كان M ، فلا يوجد حل للتطابق، أي أن n ليس باقي تربيعي.

يكون هذا مفيدًا للغاية عندما يكون p ≡ 1 (mod 4).

بالنسبة للأعداد الأولية التي تحقق الشرط p ≡ 3 (mod 4)، فإن هذه المسألة لها حلول ممكنة${\displaystyle r=\pm n^{\frac {p+1}{4}}{\pmod {p}}}$إذا كانت هذه الشروط مستوفية${\displaystyle r^{2}\equiv n{\pmod {p}}}$فهي الحلول الوحيدة. وإلا،${\displaystyle r^{2}\equiv -n{\pmod {p}}}$، n هو باقي تربيعي، ولا توجد حلول.

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

• ${\displaystyle c^{2^{M-1}}=-1}$
• ${\displaystyle t^{2^{M-1}}=1}$
• ${\displaystyle R^{2}=tn}$

بدءًا:

• ${\displaystyle c^{2^{M-1}}=z^{Q2^{S-1}}=z^{\frac {p-1}{2}}=-1}$(بما أن z عبارة عن باقي تربيعي، وفقًا لمعيار أويلر)
• ${\displaystyle t^{2^{M-1}}=n^{Q2^{S-1}}=n^{\frac {p-1}{2}}=1}$(بما أن n هو باقي تربيعي)
• ${\displaystyle R^{2}=n^{Q+1}=tn}$

في كل تكرار ، مع استبدال القيم M و c و t و R بالقيم الجديدة :

• ${\displaystyle c'^{2^{M'-1}}=(b^{2})^{2^{i-1}}=c^{2^{M-i}2^{i-1}}=c^{2^{M-1}}=-1}$
• ${\displaystyle t'^{2^{M'-1}}=(tb^{2})^{2^{i-1}}=t^{2^{i-1}}b^{2^{i}}=-1\cdot -1=1}$
  • ${\displaystyle t^{2^{i-1}}=-1}$بما أننا نمتلك ذلك${\displaystyle t^{2^{i}}=1}$لكن${\displaystyle t^{2^{i-1}}\neq 1}$( i هي أصغر قيمة بحيث${\displaystyle t^{2^{i}}=1}$)
  • ${\displaystyle b^{2^{i}}=c^{2^{M-i-1}2^{i}}=c^{2^{M-1}}=-1}$
• ${\displaystyle R'^{2}=R^{2}b^{2}=tnb^{2}=t'n}$

من${\displaystyle t^{2^{M-1}}=1}$وبالاختبار مقابل t = 1 في بداية الحلقة، نرى أننا سنجد دائمًا قيمة i في 0 < i < M بحيث${\displaystyle t^{2^{i}}=1}$^{تكون قيمة} M أصغر تمامًا في كل تكرار ، وبالتالي يُضمن توقف الخوارزمية. عندما نصل إلى الشرط t = 1 ونتوقف، فإن الثابت الأخير للحلقة يعني أن R² = n .

بحل التطابق r² ≡ 5 (mod 41) ^، نجد أن 41 عدد أولي كما هو مطلوب، و 41 ≡ 1 (mod 4). إذن، 5 هو باقي تربيعي وفقًا لمعيار أويلر.${\displaystyle 5^{\frac {41-1}{2}}=5^{20}=1}$(كما كان من قبل، العمليات في${\displaystyle (\mathbb {Z} /41\mathbb {Z} )^{\times }}$(يتم تطبيق التعديل 41 ضمنيًا).

1. ${\displaystyle p-1=40=5\cdot 2^{3}}$لذا${\displaystyle Q\leftarrow 5}$،${\displaystyle S\leftarrow 3}$
2. أوجد قيمة لـ z:
   • ${\displaystyle 2^{\frac {41-1}{2}}=1}$إذن، 2 هو باقي تربيعي وفقًا لمعيار أويلر.
   • ${\displaystyle 3^{\frac {41-1}{2}}=40=-1}$إذن، 3 هو باقي تربيعي: ضع${\displaystyle z\leftarrow 3}$
3. تعيين
   • ${\displaystyle M\leftarrow S=3}$
   • ${\displaystyle c\leftarrow z^{Q}=3^{5}=38}$
   • ${\displaystyle t\leftarrow n^{Q}=5^{5}=9}$
   • ${\displaystyle R\leftarrow n^{\frac {Q+1}{2}}=5^{\frac {5+1}{2}}=2}$
4. حلقة:
   • التكرار الأول:
     • ${\displaystyle t\neq 1}$إذن لم ننتهِ بعد
     • ${\displaystyle t^{2^{1}}=40}$،${\displaystyle t^{2^{2}}=1}$لذا${\displaystyle i\leftarrow 2}$
     • ${\displaystyle b\leftarrow c^{2^{M-i-1}}=38^{2^{3-2-1}}=38}$
     • ${\displaystyle M\leftarrow i=2}$
     • ${\displaystyle c\leftarrow b^{2}=38^{2}=9}$
     • ${\displaystyle t\leftarrow tb^{2}=9\cdot 9=40}$
     • ${\displaystyle R\leftarrow Rb=2\cdot 38=35}$
   • التكرار الثاني:
     • ${\displaystyle t\neq 1}$إذن، لم ننتهِ بعد.
     • ${\displaystyle t^{2^{1}}=1}$لذا${\displaystyle i\leftarrow 1}$
     • ${\displaystyle b\leftarrow c^{2^{M-i-1}}=9^{2^{2-1-1}}=9}$
     • ${\displaystyle M\leftarrow i=1}$
     • ${\displaystyle c\leftarrow b^{2}=9^{2}=40}$
     • ${\displaystyle t\leftarrow tb^{2}=40\cdot 40=1}$
     • ${\displaystyle R\leftarrow Rb=35\cdot 9=28}$
   • النسخة الثالثة:
     • ${\displaystyle t=1}$وهكذا انتهينا؛ فلنعد.${\displaystyle r=R=28}$

في الواقع، 28 ² ≡ 5 (mod 41) و (−28) ² ≡ 13 ² ≡ 5 (mod 41). لذا، تُعطي الخوارزمية الحلين للتطابق المطلوب.

تتطلب خوارزمية تونيللي-شانكس (في المتوسط ​​على جميع المدخلات الممكنة (البقايا التربيعية والبقايا غير التربيعية))

${\displaystyle 2m+2k+{\frac {S(S-1)}{4}}+{\frac {1}{2^{S-1}}}-9}$

الضرب المعياري، حيث${\displaystyle m}$يمثل عدد الأرقام في التمثيل الثنائي لـ${\displaystyle p}$و${\displaystyle k}$يمثل عدد الآحاد في التمثيل الثنائي لـ${\displaystyle p}$إذا كان الباقي التربيعي المطلوب${\displaystyle z}$يتم العثور عليه عن طريق التحقق مما إذا كان رقمًا تم اختياره عشوائيًا${\displaystyle y}$هو متبقي غير تربيعي، ويتطلب (في المتوسط)${\displaystyle 2}$حسابات رمز ليجندر . ^{[ 5 ]} يُشرح متوسط ​​حسابين لرمز ليجندر على النحو التالي:${\displaystyle y}$هو باقي تربيعي مع احتمال${\displaystyle {\tfrac {\tfrac {p+1}{2}}{p}}={\tfrac {1+{\tfrac {1}{p}}}{2}}}$وهو أصغر من${\displaystyle 1}$لكن${\displaystyle \geq {\tfrac {1}{2}}}$لذلك سنحتاج في المتوسط ​​إلى التحقق مما إذا كان${\displaystyle y}$هو باقي تربيعي مرتين.

يُظهر هذا بشكل أساسي أن خوارزمية تونيللي-شانكس تعمل بشكل جيد للغاية إذا كان المعامل${\displaystyle p}$عشوائي، أي إذا${\displaystyle S}$لا يُعدّ حجمه كبيرًا بشكل خاص مقارنةً بعدد الأرقام في التمثيل الثنائي لـ${\displaystyle p}$كما هو مذكور أعلاه، فإن خوارزمية سيبولا تعمل بشكل أفضل من خوارزمية تونيللي-شانكس إذا (وفقط إذا)${\displaystyle S(S-1)>8m+20}$ومع ذلك، إذا استخدمنا بدلاً من ذلك خوارزمية ساذرلاند لإجراء حساب اللوغاريتم المنفصل في المجموعة الفرعية 2-سيلو من${\displaystyle \mathbb {F} _{p}^{\ast }}$، يمكن استبدال${\displaystyle S(S-1)}$بتعبير محدود تقاربياً بواسطة${\displaystyle O(S\log S/\log \log S)}$[ ^{6 ] بشكل صريح} ، يتم حساب${\displaystyle e}$بحيث${\displaystyle c^{e}\equiv n^{Q}}$وثم${\displaystyle R\equiv c^{-e/2}n^{(Q+1)/2}}$يرضي${\displaystyle R^{2}\equiv n}$(لاحظ أن${\displaystyle e}$هو من مضاعفات العدد 2 لأن${\displaystyle n}$(وهو باقي تربيعي).

تتطلب الخوارزمية منا إيجاد باقي تربيعي غير متبقٍ${\displaystyle z}$لا توجد خوارزمية حتمية معروفة تعمل في وقت متعدد الحدود لإيجاد مثل هذا${\displaystyle z}$ومع ذلك، إذا كانت فرضية ريمان المعممة صحيحة، فإنه يوجد باقي تربيعي غير متبقٍ${\displaystyle z<2\ln ^{2}{p}}$[ ^{7 ] مما يجعل} من الممكن التحقق من كل${\displaystyle z}$حتى ذلك الحد، وابحث عن خيار مناسب.${\displaystyle z}$في غضون وقت متعدد الحدود . مع ذلك، ضع في اعتبارك أن هذا أسوأ سيناريو ممكن؛ بشكل عام،${\displaystyle z}$يتم العثور عليها في المتوسط ​​في تجربتين كما هو مذكور أعلاه.

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

يمكن تعميم نظرية تونيللي-شانكس على أي مجموعة حلقية (بدلاً من${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{\times }}$) وإلى الجذور k لأي عدد صحيح k ، وعلى وجه الخصوص إلى أخذ الجذر k لعنصر من حقل منتهٍ . ^{[ 8 ]}

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

1. استخرج عوامل العدد 2 من p − 1، مع تعريف Q و S على النحو التالي:${\displaystyle p-1=Q2^{S}}$مع كون Q فرديًا.
2. يترك${\displaystyle R\leftarrow n^{\frac {Q+1}{2}},t\leftarrow n^{Q}\equiv R^{2}/n}$
3. يجد${\displaystyle b}$من الجدول بحيث${\displaystyle b^{2}\equiv t}$وضبط${\displaystyle R\equiv R/b}$
4. أعد R.​

• إيفان نيفن ؛ هربرت س. زوكرمان؛ هيو ل. مونتغمري (1991). مدخل إلى نظرية الأعداد (الطبعة الخامسة  ). وايلي. الصفحات 110-115 . ISBN  0-471-62546-9.
• دانيال شانكس. خمس خوارزميات نظرية الأعداد. وقائع المؤتمر الثاني لمانيتوبا حول الرياضيات العددية. الصفحات  51-70. 1973.
• ألبرتو تونيلي، Bemerkung über die Auflösung Quadratischer Congruenzen. Nachrichten von der Königlichen Gesellschaft der Wissenschaften und der Georg-August-Universität zu Göttingen . ص.  344-346. 1891.
• جاغان تارا ناندا - الرياضيات 115: خوارزمية ريسول
• غونزالو تورناريا