مشكلة البقايا التربيعية

تتمثل مشكلة الباقي التربيعي ( QRP ^{[ 1 ]} ) في نظرية الأعداد الحسابية في تحديد، بالنظر إلى الأعداد الصحيحة${\displaystyle a}$و${\displaystyle N}$، سواء${\displaystyle a}$هو الباقي التربيعي modulo${\displaystyle N}$أو لا. هنا${\displaystyle N=p_{1}p_{2}}$لعددين أوليين مجهولين${\displaystyle p_{1}}$و${\displaystyle p_{2}}$، و${\displaystyle a}$وهي من بين الأرقام التي لا تُعتبر بوضوح بواقي تربيعية غير متبقية (انظر أدناه).

وصف غاوس هذه المشكلة لأول مرة في كتابه "Disquisitiones Arithmeticae" عام 1801. ويُعتقد أن هذه المشكلة صعبة حسابيًا . وتعتمد العديد من طرق التشفير على صعوبتها ، انظر قسم  التطبيقات .

إن وجود خوارزمية فعالة لمسألة الباقي التربيعي يستلزم بالضرورة وجود خوارزميات فعالة لمسائل نظرية الأعداد الأخرى ، مثل تحديد ما إذا كان المركب${\displaystyle N}$إن تحليل العدد المجهول إلى عوامله الأولية هو حاصل ضرب عددين أو ثلاثة أعداد أولية. ^{[ 2 ]}

معطى أعداد صحيحة${\displaystyle a}$و${\displaystyle T}$،${\displaystyle a}$يقال إنها متبقية تربيعية modulo${\displaystyle T}$إذا كان هناك عدد صحيح${\displaystyle b}$بحيث

${\displaystyle a\equiv b^{2}{\pmod {T}}}$.

وإلا نقول إنها دالة غير متبقية من الدرجة الثانية. عندما${\displaystyle T=p}$إذا كان عددًا أوليًا، فمن المعتاد استخدام رمز ليجندر :

$\displaystyle \left(\frac{a}{p}\right)=\begin{cases}1&{\text{ إذا كان }}a{\text{ باقيًا تربيعيًا modulo }}p{\text{ و }}a\not \equiv 0{\pmod {p}},\\-1&{\text{ إذا كان }}a{\text{ ليس باقيًا تربيعيًا modulo }}p,\\0&{\text{ إذا كان }}a\equiv 0{\pmod {p}}.\end{cases}}}$

هذا رمز ضربي يعني${\displaystyle {\big (}{\tfrac {a}{p}}{\big )}=1}$لـ بالضبط${\displaystyle (p-1)/2}$من القيم${\displaystyle 1,\ldots ,p-1}$وهو${\displaystyle -1}$أما الباقي.

من السهل حساب ذلك باستخدام قانون التبادل التربيعي بطريقة مشابهة للخوارزمية الإقليدية ؛ انظر رمز ليجندر .

لنفترض الآن بعض المعطيات${\displaystyle N=p_{1}p_{2}}$أين${\displaystyle p_{1}}$و${\displaystyle p_{2}}$هما عددان أوليان مجهولان مختلفان. معطى${\displaystyle a}$هو الباقي التربيعي modulo${\displaystyle N}$إذا وفقط إذا${\displaystyle a}$هو الباقي التربيعي modulo كلاهما${\displaystyle p_{1}}$و${\displaystyle p_{2}}$و${\displaystyle \gcd(a,N)=1}$.

بما أننا لا نعرف${\displaystyle p_{1}}$أو${\displaystyle p_{2}}$لا يمكننا الحساب${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}}$و${\displaystyle {\big (}{\tfrac {a}{p_{2}}}{\big )}}$ومع ذلك، من السهل حساب حاصل ضربهما. وهذا ما يُعرف برمز جاكوبي .

${\displaystyle \left({\frac {a}{N}}\right)=\left({\frac {a}{p_{1}}}\right)\left({\frac {a}{p_{2}}}\right)}$

ويمكن أيضًا حساب ذلك بكفاءة باستخدام قانون التبادل التربيعي لرموز جاكوبي.

لكن،${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}}$لا يمكننا في جميع الحالات أن نخبرنا ما إذا كان${\displaystyle a}$هو الباقي التربيعي modulo${\displaystyle N}$أو لا! بتعبير أدق، إذا${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=-1}$ثم${\displaystyle a}$هو بالضرورة باقي تربيعي modulo إما${\displaystyle p_{1}}$أو${\displaystyle p_{2}}$وفي هذه الحالة نكون قد انتهينا. ولكن إذا${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1}$إذن، إما أن يكون الأمر كذلك${\displaystyle a}$هو الباقي التربيعي modulo كلاهما${\displaystyle p_{1}}$و${\displaystyle p_{2}}$أو دالة تربيعية غير متبقية بتردد كليهما${\displaystyle p_{1}}$و${\displaystyle p_{2}}$لا يمكننا التمييز بين هذه الحالات ومعرفة ذلك فحسب.${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1}$.

وهذا يؤدي إلى الصياغة الدقيقة لمسألة البقايا التربيعية:

المسألة: معطى أعداد صحيحة${\displaystyle a}$و${\displaystyle N=p_{1}p_{2}}$، أين${\displaystyle p_{1}}$و${\displaystyle p_{2}}$هي أعداد أولية مجهولة متميزة، وحيث${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1}$، تحديد ما إذا${\displaystyle a}$هو الباقي التربيعي modulo${\displaystyle N}$أو لا.

لو${\displaystyle a}$يتم سحبها عشوائياً وبشكل منتظم من الأعداد الصحيحة${\displaystyle 0,\ldots ,N-1}$بحيث${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1}$، يكون${\displaystyle a}$في أغلب الأحيان يكون باقيًا تربيعيًا أو باقيًا تربيعيًا modulo${\displaystyle N}$؟

كما ذكرنا سابقاً، بالنسبة لنصف الخيارات بالضبط${\displaystyle a\in \{1,\ldots ,p_{1}-1\}}$، ثم${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}=1}$أما بالنسبة للباقي فلدينا${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}=-1}$وبالتالي، ينطبق هذا أيضًا على نصف خيارات${\displaystyle a\in \{1,\ldots ,N-1\}\setminus p_{1}\mathbb {Z} }$وبالمثل بالنسبة لـ${\displaystyle p_{2}}$من الجبر الأساسي، يتبين أن هذا التقسيم${\displaystyle (\mathbb {Z} /N\mathbb {Z} )^{\times }}$إلى 4 أجزاء متساوية الحجم، حسب إشارة${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}}$و${\displaystyle {\big (}{\tfrac {a}{p_{2}}}{\big )}}$.

المسموح به${\displaystyle a}$في مسألة البقايا التربيعية المذكورة أعلاه، يشكل الجزآن المتوافقان مع الحالات المذكورة تحديدًا${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}={\big (}{\tfrac {a}{p_{2}}}{\big )}=1}$و${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}={\big (}{\tfrac {a}{p_{2}}}{\big )}=-1}$وبالتالي، فإن نصف الاحتمالات الممكنة بالضبط${\displaystyle a}$البقايا هي بقايا تربيعية، أما البقايا فليست كذلك.

تُشكّل صعوبة حلّ مسألة البقايا التربيعية أساس أمان مولد الأرقام العشوائية الزائفة من نوع بلوم بلوم شوب . كما أنها تُنتج نظام التشفير بالمفتاح العام غولدواسير-ميكالي ، ^{[ 3 ] [ 4 ]} بالإضافة إلى مخطط كوكس القائم على الهوية .

• مشكلة البقايا العالية