تويت
في نظرية الأعداد، تنص نظرية الباقي الصيني “Chinese remainder theorem” على أنه إذا عرف المرء بقايا القسمة الإقليدية لعدد صحيح n بواسطة عدة أعداد صحيحة، فيمكن عندئذٍ تحديد ما تبقى من قسمة n على حاصل ضرب هذه الأعداد الصحيحة، بشرط أن القواسم هي جريمة مشتركة.
الصورة: صيغة Sun-tzu الأصلية:
X ≡ 2 (mod 3) ≡ 3 (mod 5) ≡ 2 (mod 7)
مع الحل x = 23 + 105k ، مع k عدد صحيح.
أقدم بيان معروف للنظرية هو من قبل عالم الرياضيات الصيني سون-تزو في صن-تزو سوان-تشينج في القرن الثالث الميلادي.
تُستخدم نظرية الباقي الصينية على نطاق واسع للحوسبة ذات الأعداد الصحيحة الكبيرة، لأنها تسمح باستبدال الحساب الذي يعرف المرء حدودًا لحجم النتيجة بعدة حسابات مماثلة على أعداد صحيحة صغيرة. نظرية الباقي الصيني (المعبر عنها بمصطلحات التطابق) صحيحة على كل مجال مثالي رئيسي. لقد تم تعميمه على أي حلقة تبادلية، مع صياغة تتضمن مُثُل عليا.
تاريخ نظرية الباقي الصينية
يظهر أقرب بيان معروف للنظرية، كمشكلة مع أرقام محددة، في كتاب القرن الثالث Sun-tzu Suan-ching لعالم الرياضيات الصيني Sun-tzu:
“هناك أشياء معينة لا يعرف عددها. إذا عدناهم إلى ثلاثة، يتبقى لدينا اثنان؛ بخمسات، يتبقى لدينا ثلاثة؛ و بحلول السبعات، بقي اثنان. كم عدد الأشياء الموجودة؟ “
لا يحتوي عمل Sun-tzu على دليل ولا خوارزمية كاملة. ما يرقى إلى خوارزمية لحل هذه المشكلة وصفه أرياباتا (القرن السادس). كما عُرفت حالات خاصة من نظرية الباقي الصينية لدى Brahmagupta (القرن السابع)، و ظهرت في كتاب Liber Abaci (1202) لفيبوناتشي. تم تعميم النتيجة لاحقًا باستخدام حل كامل يسمى Da-yan-shu (大 衍 術) في رسالة Ch’in Chiu-shao 1247 الرياضية في تسعة أقسام (數 書 九章 ، Shu-shu Chiu-chang) و التي تُرجمت إلى الإنجليزية في أوائل القرن التاسع عشر من قبل المبشر البريطاني ألكسندر ويلي.
الصورة: تظهر نظرية الباقي الصيني في استفسارات حسابية، كتاب من تأليف كارل فريدريش غاوس.
تم تقديم مفهوم التطابق لأول مرة واستخدامه بواسطة غاوس في كتابه ستفسارات حسابية لعام 1801. يوضح جاوس نظرية الباقي الصينية حول مشكلة تتعلق بالتقويمات، أي “العثور على السنوات التي لها رقم فترة معين فيما يتعلق بالدورة الشمسية والقمرية والدليل الروماني”. يقدم غاوس إجراءً لحل المشكلة التي استخدمها أويلر بالفعل و لكنها كانت في الواقع طريقة قديمة ظهرت عدة مرات.
بيان تصريح نظرية الباقي الصينية
لنفترض أن n1، …، nk تكون أعدادًا صحيحة أكبر من 1، والتي غالبًا ما تسمى وحدات أو قواسم. دعونا نشير بواسطة N إلى حاصل ضرب ni.
تؤكد نظرية الباقي الصينية أنه إذا كانت ni عبارة عن جريمة مشتركة زوجية، و إذا كانت a1، …، ak أعدادًا صحيحة مثل 0 ≤ ai <ni لكل i، فإن هناك واحدًا واحدًا فقط عدد صحيح x، مثل 0 ≤ x <N والباقي من القسمة الإقليدية لـ x على ni هي ai لكل i.
يمكن إعادة بيان هذا على النحو التالي من حيث التطابق:
إذا كانت ni عبارة عن جريمة مشتركة زوجية، و إذا كانت a1، …، ak أي أعداد صحيحة، فإن النظام
له حل، وأي حلين، على سبيل المثال x1 و x2، هما مقياس متطابق N، أي x1 ≡ x2 (mod N).
في الجبر المجرد، غالبًا ما يتم إعادة صياغة النظرية على النحو التالي: إذا كانت ni هي جريمة مشتركة زوجية، فإن الخريطة:
يحدد تماثل الحلقة
بين حلقة الأعداد الصحيحة حسابيات معيارية و المنتج المباشر لحلقات الأعداد الصحيحة حسابيات ni. هذا يعني أنه لإجراء سلسلة من العمليات الحسابية في Z/NZ، يمكن للمرء أن يفعل الشيء نفسه الحساب بشكل مستقل في كل Z/niZ ثم الحصول على النتيجة من خلال تطبيق التماثل (من اليمين إلى اليسار). قد يكون هذا أسرع بكثير من الحساب المباشر إذا كانت N و عدد العمليات كبيرًا. يستخدم هذا على نطاق واسع، تحت اسم الحساب متعدد الوحدات، للجبر الخطي على الأعداد الصحيحة أو الأرقام المنطقية.
يمكن أيضًا إعادة صياغة النظرية في لغة التوافقية حيث أن التدرجات الحسابية اللانهائية للأعداد الصحيحة تشكل عائلة هيلي.
الدليل والاثبات
يمكن إثبات وجود الحل و تفرده بشكل مستقل. و مع ذلك، فإن أول دليل على الوجود، الوارد أدناه، يستخدم هذا التفرد.
التفرد
افترض أن x و y كلاهما حلين لكل التطابقات. بما أن x و y يعطيان الباقي نفسه، عند القسمة على ni، فإن الفرق بينهما x – y هو مضاعف كل ni. نظرًا لأن ni عبارة عن جريمة مشتركة زوجية، فإن ناتجها N يقسم أيضًا x – y، و بالتالي فإن x و y هما مقياسان متطابقان N. إذا كان من المفترض أن يكون x و y غير سالبين و أقل من N (كما في العبارة الأولى من النظرية)، فقد يكون الاختلاف بينهما من مضاعفات N فقط إذا كانت x = y.
وجود (أول دليل)
الخريطة:
تطابق فئات الخرائط حسابيات معيارية N إلى متواليات فئات التطابق حسابيات معيارية ni. يُظهر الدليل على التفرد أن هذه الخريطة هي حقنة. نظرًا لأن المجال السري لهذه الخريطة لهما نفس عدد العناصر، فإن الخريطة أيضًا تخمينية، مما يثبت وجود الحل.
هذا الدليل بسيط للغاية و لكنه لا يوفر أي طريقة مباشرة لحساب حل. علاوة على ذلك، لا يمكن تعميمها على مواقف أخرى حيث يمكن للأدلة التالية.
وجود (دليل بناء)
يمكن إثبات الوجود من خلال بناء صريح لـ x. يمكن تقسيم هذا البناء إلى خطوتين، أولاً عن طريق حل المشكلة في حالة وجود نمطين، و الثاني عن طريق توسيع هذا الحل للحالة العامة عن طريق الاستقراء على عدد الوحدات.
حالة اثنين من المعادلات
نريد حل النظام:
حيث n1 و n2 هي جريمة مشتركة.
تؤكد هوية بيزوت وجود عددين صحيحين m1 و m2 على هذا النحو: m1 n1 + m2n2 = 1
يمكن حساب الأعداد الصحيحة m1 و m2 بواسطة الخوارزمية الإقليدية الموسعة.
يتم إعطاء حل بواسطة: x = a1 m2 n2 + a2m1n1
في الواقع،
مما يعني أن x≡ a1 (الوضع n1). تم إثبات التطابق الثاني بالمثل، من خلال تبادل الحرفين 1 و 2.
الحالة العامة
ضع في اعتبارك سلسلة من معادلات التطابق:
X ≡ a1 (mod n1) …. x ≡ ak (mod nk)
حيث ni هي جريمة مشتركة. المعادلتان الأوليان لهما الحل a1،2 المقدم من طريقة القسم السابق. مجموعة حلول هاتين المعادلتين الأوليين هي مجموعة جميع حلول المعادلة
X ≡ a1،2 (mod n1،2)
نظرًا لأن ni الآخر عبارة عن n1n2، فإن هذا يقلل من حل المشكلة الأولية لمعادلات k إلى مشكلة مماثلة مع معادلات k-1. بتكرار العملية، يحصل المرء في النهاية على حلول المشكلة الأولية.
وجود (بناء مباشر)
لإنشاء حل، ليس من الضروري إجراء تحريض على عدد الوحدات. و مع ذلك، فإن مثل هذا البناء المباشر ينطوي على مزيد من الحسابات بأعداد كبيرة، مما يجعلها أقل كفاءة وأقل استخدامًا. و مع ذلك، فإن استيفاء لاغرانج هو حالة خاصة لهذا البناء، يتم تطبيقه على كثيرات الحدود بدلاً من الأعداد الصحيحة.
لنفترض أن Ni = N / ni هو نتاج جميع المقاييس باستثناء واحدة. نظرًا لأن ni عبارة عن جريمة مشتركة زوجية، فإن Ni و n هما جريمة مشتركة. و هكذا تنطبق هوية بزوت، و هناك أعداد صحيحة Mi و mi من القبيل MiNi + mini = 1. حل نظام التطابق هو
في الواقع، نظرًا لأن Nj هو مضاعف ni لـ I ≠ j، فلدينا
لكل i.
حساب
ضع في اعتبارك نظام التطابق:
X ≡ a1 (mod n1)
…
X ≡ ak (mod nk)
حيث ni هي أولية نسبية زوجية، و دع N = n1n2 … nk.
في هذا القسم، تم وصف عدة طرق لحساب الحل الفريد لـ x، بحيث يتم تطبيق 0 ≥ x < N و هذه الطرق على المثال:
X ≡ 0 (mod 3)
X ≡ 3 (mod 4)
X≡ 4 (mod 5)
البحث المنهجي
من السهل التحقق مما إذا كانت قيمة x حلاً: يكفي حساب باقي القسمة الإقليدية لـ x بواسطة كل ni. و بالتالي، لإيجاد الحل، يكفي التحقق من الأعداد الصحيحة من 0 إلى N على التوالي حتى إيجاد الحل.
على الرغم من بساطتها، إلا أن هذه الطريقة غير فعالة للغاية. بالنسبة للمثال البسيط المدروس هنا، يجب التحقق من 40 عددًا صحيحًا (بما في ذلك 0) لإيجاد الحل، و هو 39. هذه خوارزمية زمنية أسية، حيث أن حجم الإدخال يصل إلى عامل ثابت، و عدد أرقام N، و متوسط عدد العمليات بترتيب N.
لذلك، نادرًا ما يتم استخدام هذه الطريقة، لا للحسابات المكتوبة بخط اليد ولا على أجهزة الكمبيوتر.
البحث عن طريق الغربلة
الصورة: أصغر حلين، 23 و 128، من الصيغة الأصلية لمشكلة نظرية الباقي الصينية التي تم العثور عليها باستخدام منخل.
قد يكون البحث عن الحل أسرع بشكل كبير عن طريق الغربلة. بالنسبة لهذه الطريقة، نفترض، دون فقدان العمومية، أن ai < ni (إذا لم يكن الأمر كذلك، فسيكفي استبدال كل ai ببقية تقسيمه بواسطة ni). هذا يعني أن الحل ينتمي إلى التقدم الحسابي
a1 ، a1 + n1 ، a1 + 2n1 ، …
من خلال اختبار قيم هذه الأرقام، المقياس n2، يجد المرء في النهاية حلاً x2 من التطابقين الأولين. ثم الحل ينتمي إلى التقدم الحسابي
x2 ، x2 + n1n2 ، x2 + 2n1n2 ، …
اختبار قيم هذه الأعداد بمعامل n3 والاستمرار حتى يتم اختبار كل معامل يعطي الحل في النهاية.
تكون هذه الطريقة أسرع إذا تم ترتيب المعادلات عن طريق تقليل القيمة، أي إذا كانت n1 > n2 > ….> nk.
على سبيل المثال، هذا يعطي الحساب التالي.
نعتبر أولاً الأرقام المتطابقة مع 4 مقياس 5 (أكبر معامل)، وهي 4، 9 = 4 + 5، 14 = 9 + 5، … لكل منها، احسب الباقي بمقدار 4 (الثاني أكبر معامل) حتى الحصول على رقم مطابق لـ 3 مقياس 4. يمكن بعد ذلك المضي قدمًا بإضافة 20 = 5 × 4 في كل خطوة، و حساب الباقي فقط بمقدار 3.
هذا يعطي
4 mod 4 → 0.
استمر..
4 + 5 = 9 mod 4 →1.
استمر..
9 + 5 = 14 mod 4 → 2.
استمر..
14 + 5 = 19 mod 4 → 3.
حسنًا، استمر في النظر في الباقي بالمقياس 3 وإضافة 5 × 4 = 20 في كل مرة
19 mod 3 → 1.
استمر..
19 + 20 = 39 mod 3 → 0.
حسنًا، هذه هي النتيجة.
تعمل هذه الطريقة بشكل جيد مع الحساب المكتوب يدويًا باستخدام منتج من وحدات ليست كبيرة جدًا. و مع ذلك، فهي أبطأ بكثير من الطرق الأخرى، بالنسبة للمنتجات الكبيرة جدًا من الوحدات. على الرغم من أن هذه الطريقة أسرع بشكل كبير من البحث المنهجي، إلا أن هذه الطريقة لها أيضًا تعقيد زمني أسي و بالتالي لا يتم استخدامها على أجهزة الكمبيوتر.
استخدام بناء الوجود
يُظهر إثبات الوجود البناء أنه في حالة وجود نمطين، يمكن الحصول على الحل من خلال حساب معاملات بيزوت الخاصة بالمعايير، متبوعة ببعض عمليات الضرب والإضافات والتخفيضات n1n2 (للحصول على نتيجة في الفترة 0، n1n2 – 1). نظرًا لأن معاملات بيزوت يمكن حسابها باستخدام الخوارزمية الإقليدية الموسعة، فإن الحساب بأكمله، على الأكثر، له تعقيد زمني من الدرجة الثانية O(s1 + s2)2، حيث يشير si إلى عدد أرقام ni.
بالنسبة لأكثر من نمطين، تسمح طريقة المعاملين باستبدال أي تطابقين بوحدة تطابق واحدة لمنتج المعاملين. يوفر تكرار هذه العملية في النهاية للحل تعقيدًا، و هو تربيعي في عدد أرقام منتج جميع الوحدات. لا يعتمد هذا التعقيد الزمني التربيعي على الترتيب الذي يتم فيه إعادة تجميع الوحدات. يمكن للمرء إعادة تجميع المعاملين الأولين، ثم إعادة تجميع المعامل الناتج مع المعامل التالي، و هكذا. هذه الإستراتيجية هي الأسهل في التنفيذ، و لكنها تتطلب أيضًا مزيدًا من الحسابات التي تتضمن أعدادًا كبيرة.
تتمثل الإستراتيجية الأخرى في تقسيم المعادلات إلى أزواج يكون لمنتجها أحجام قابلة للمقارنة (قدر الإمكان)، و تطبيق، بالتوازي، طريقة اثنين من المعاملين لكل زوج، والتكرار مع عدد من الوحدات مقسومًا تقريبًا على اثنين. تسمح هذه الطريقة بموازنة الخوارزمية بسهولة. أيضًا، إذا تم استخدام خوارزميات سريعة (و هي خوارزميات تعمل في وقت شبه خطي) للعمليات الأساسية، فإن هذه الطريقة توفر خوارزمية للحساب الكامل الذي يعمل في وقت شبه خطي.
في المثال الحالي (الذي يحتوي على ثلاثة نماذج فقط)، كلا الاستراتيجيتين متطابقتان و تعملان على النحو التالي.
متطابقة بيزو (صيغة تربط عددين وقاسمهم المشترك الأكبر) لـ 3 و 4 هي 1 × 4 + (- 1) × 3 = 1.
وضع هذا في الصيغة المعطاة لإثبات الوجود يعطي 0 × 1 × 4 + 3 × (-1) × 3 = -9
لحل التطابقين الأولين، يتم الحصول على الحلول الأخرى عن طريق إضافة أي مضاعف لـ 3 × 4 = 12. إلى -9، يمكن للمرء أن يستمر مع أي من هذه الحلول، ولكن الحل 3 = -9 +12 أصغر (في القيمة المطلقة) و بالتالي ربما يؤدي إلى عملية حسابية أسهل. مطابقة بيزوت لـ 5 و 3 × 4 = 12 هي 5 × 5 + (- 2) × 12 = 1.
بتطبيق نفس الصيغة مرة أخرى، نحصل على حل للمشكلة : 25 × 3-24 × 4 = 21-.
يتم الحصول على الحلول الأخرى بإضافة أي من مضاعفات 3 × 4 × 5 = 60، وأصغر حل موجب هو 21− + 60 = 39.
نظام ديوفانتاين خطي
يمكن إعادة كتابة نظام التطابق الذي تم حله بواسطة نظرية الباقي الصينية كنظام من معادلات ديوفانتين الخطية المتزامنة:
x = a1 + xini
…
x = ak + xknk ،
حيث الأعداد الصحيحة المجهولة هي x و xi. لذلك، يمكن استخدام كل طريقة عامة لحل مثل هذه الأنظمة لإيجاد حل نظرية الباقي الصينية، مثل اختزال مصفوفة النظام إلى شكل سميث العادي أو النموذج العادي هيرمايت. و مع ذلك، كالمعتاد عند استخدام خوارزمية عامة لمشكلة أكثر تحديدًا، فإن هذا النهج أقل كفاءة من طريقة القسم السابق، بناءً على الاستخدام المباشر لهوية بيزوت.
المجالات المثالية الرئيسية
في قسم بيان – تصريح النظريه، تم ذكر نظرية الباقي الصيني بثلاث طرق مختلفة: من حيث الباقي، و التطابق، و تماثل الحلقة. لا ينطبق البيان من حيث الباقي، بشكل عام، على المجالات المثالية الرئيسية، حيث لم يتم تعريف الباقي في مثل هذه الحلقات. و مع ذلك، فإن النسختين الأخريين لهما معنى على المجال المثالي الرئيسي R: يكفي استبدال “عدد صحيح” بـ “عنصر المجال” و Z بواسطة R.
هاتان النسختان من النظرية صحيحة في هذا السياق، لأن البراهين (باستثناء إثبات الوجود الأول)، تستند إلى ليما إقليدس وهوية بيزوت، و هي صحيحة على كل مجال رئيسي. و مع ذلك، بشكل عام، فإن النظرية ليست سوى نظرية وجود ولا توفر أي طريقة لحساب الحل، ما لم يكن لدى المرء خوارزمية لحساب معاملات هوية بيزوت.
تعميم نظرية الباقي الصينية على تعديل وحدات وحدات غير مغطاة
يمكن تعميم نظرية الباقي الصينية على معاملات غير مغطاة. لنفترض أن m ، n ، a ، b أي أعداد صحيحة، دع g = gcd(m، n)، و اعتبر نظام التطابق:
X≡ a (mod m)
X≡ b (mod n)
إذا كان a ≡ b (mod g)، فإن نظام المعادلات هذا له معامل حل فريد lcm(m، n) = mn / g. خلاف ذلك، ليس لديها حلول.
إذا استخدمنا هوية بيزوت لكتابة g = um + vn، فالحل هو
هذا يحدد عددًا صحيحًا، حيث أن g تقسم كل من m و n. و بخلاف ذلك، يكون الدليل مشابهًا جدًا لإثبات معاملات المشاركة في الجريمة.
تعميم نظرية الباقي الصينية على الحلقات العشوائية
يمكن تعميم نظرية الباقي الصيني على أي حلقة، باستخدام مُثُل الجريمة الجماعية (و تسمى أيضًا المُثُل الكومكسيمالية). مثالان I و J هما جريمة مشتركة إذا كان هناك عنصران i ϵ I و j ϵ J مثل i + j = 1. تلعب هذه العلاقة دور هوية بيزوت في البراهين المتعلقة بهذا التعميم، والتي، بخلاف ذلك، متشابهة جدًا. يمكن ذكر التعميم على النحو التالي.
دع I1، … ، Ik تكون مُثلًا ذات وجهين للحلقة R و دع I تكون تقاطعهم. إذا كانت المثل العليا هي الجريمة الزوجية، فلدينا التماثل:
بين حلقة خارج القسمة R / I والمنتج المباشر لـ R / Ii حيث يشير “x mod I” إلى صورة العنصر x في حلقة خارج القسمة المحددة بواسطة المثالي I. علاوة على ذلك، إذا كانت R تبادلية، فإن التقاطع المثالي بين المثل العليا للجريمة المشتركة يساوي منتجهم؛ هذا هو
إذا كان Ii و Ij جريمة مشتركة لـ I ≠ j.
تطبيقات نظرية الباقي الصينية
ترقيم التسلسل
تم استخدام نظرية الباقي الصينية لبناء ترقيم Gödel للتسلسلات، والتي تشارك في إثبات نظريات عدم اكتمال Gödel.
تحويل فورييه السريع
تستخدم خوارزمية FFT الرئيسية (تسمى أيضًا خوارزمية Good-Thomas) نظرية الباقي الصينية لتقليل حساب تحويل فورييه السريع بالحجم n1n2 إلى حساب تحولي فورييه سريعين بأحجام أصغر n1 و n2.
التشفير
تستخدم معظم تطبيقات RSA نظرية الباقي الصينية أثناء توقيع شهادات HTTPS وأثناء فك التشفير.
يمكن أيضًا استخدام نظرية الباقي الصينية في المشاركة السرية، والتي تتكون من توزيع مجموعة من الأسهم بين مجموعة من الأشخاص الذين يمكنهم، معًا (ولكن لا أحد بمفرده)، استعادة سر معين من مجموعة الأسهم المحددة. يتم تمثيل كل سهم في تطابق، و حل نظام التطابق باستخدام نظرية الباقي الصينية هو السر الذي يجب استرداده. تستخدم المشاركة السرية باستخدام نظرية الباقي الصينية، جنبًا إلى جنب مع نظرية الباقي الصينية، تسلسلات خاصة من الأعداد الصحيحة التي تضمن استحالة استعادة السر من مجموعة من المشاركات التي تحتوي على عدد أقل من عدد أصلي معين.
الصورة: صيغة Sun-tzu الأصلية:
X ≡ 2 (mod 3) ≡ 3 (mod 5) ≡ 2 (mod 7)
مع الحل x = 23 + 105k ، مع k عدد صحيح.
أقدم بيان معروف للنظرية هو من قبل عالم الرياضيات الصيني سون-تزو في صن-تزو سوان-تشينج في القرن الثالث الميلادي.
تُستخدم نظرية الباقي الصينية على نطاق واسع للحوسبة ذات الأعداد الصحيحة الكبيرة، لأنها تسمح باستبدال الحساب الذي يعرف المرء حدودًا لحجم النتيجة بعدة حسابات مماثلة على أعداد صحيحة صغيرة. نظرية الباقي الصيني (المعبر عنها بمصطلحات التطابق) صحيحة على كل مجال مثالي رئيسي. لقد تم تعميمه على أي حلقة تبادلية، مع صياغة تتضمن مُثُل عليا.
تاريخ نظرية الباقي الصينية
يظهر أقرب بيان معروف للنظرية، كمشكلة مع أرقام محددة، في كتاب القرن الثالث Sun-tzu Suan-ching لعالم الرياضيات الصيني Sun-tzu:
“هناك أشياء معينة لا يعرف عددها. إذا عدناهم إلى ثلاثة، يتبقى لدينا اثنان؛ بخمسات، يتبقى لدينا ثلاثة؛ و بحلول السبعات، بقي اثنان. كم عدد الأشياء الموجودة؟ “
لا يحتوي عمل Sun-tzu على دليل ولا خوارزمية كاملة. ما يرقى إلى خوارزمية لحل هذه المشكلة وصفه أرياباتا (القرن السادس). كما عُرفت حالات خاصة من نظرية الباقي الصينية لدى Brahmagupta (القرن السابع)، و ظهرت في كتاب Liber Abaci (1202) لفيبوناتشي. تم تعميم النتيجة لاحقًا باستخدام حل كامل يسمى Da-yan-shu (大 衍 術) في رسالة Ch’in Chiu-shao 1247 الرياضية في تسعة أقسام (數 書 九章 ، Shu-shu Chiu-chang) و التي تُرجمت إلى الإنجليزية في أوائل القرن التاسع عشر من قبل المبشر البريطاني ألكسندر ويلي.
الصورة: تظهر نظرية الباقي الصيني في استفسارات حسابية، كتاب من تأليف كارل فريدريش غاوس.
تم تقديم مفهوم التطابق لأول مرة واستخدامه بواسطة غاوس في كتابه ستفسارات حسابية لعام 1801. يوضح جاوس نظرية الباقي الصينية حول مشكلة تتعلق بالتقويمات، أي “العثور على السنوات التي لها رقم فترة معين فيما يتعلق بالدورة الشمسية والقمرية والدليل الروماني”. يقدم غاوس إجراءً لحل المشكلة التي استخدمها أويلر بالفعل و لكنها كانت في الواقع طريقة قديمة ظهرت عدة مرات.
بيان تصريح نظرية الباقي الصينية
لنفترض أن n1، …، nk تكون أعدادًا صحيحة أكبر من 1، والتي غالبًا ما تسمى وحدات أو قواسم. دعونا نشير بواسطة N إلى حاصل ضرب ni.
تؤكد نظرية الباقي الصينية أنه إذا كانت ni عبارة عن جريمة مشتركة زوجية، و إذا كانت a1، …، ak أعدادًا صحيحة مثل 0 ≤ ai <ni لكل i، فإن هناك واحدًا واحدًا فقط عدد صحيح x، مثل 0 ≤ x <N والباقي من القسمة الإقليدية لـ x على ni هي ai لكل i.
يمكن إعادة بيان هذا على النحو التالي من حيث التطابق:
إذا كانت ni عبارة عن جريمة مشتركة زوجية، و إذا كانت a1، …، ak أي أعداد صحيحة، فإن النظام
له حل، وأي حلين، على سبيل المثال x1 و x2، هما مقياس متطابق N، أي x1 ≡ x2 (mod N).
في الجبر المجرد، غالبًا ما يتم إعادة صياغة النظرية على النحو التالي: إذا كانت ni هي جريمة مشتركة زوجية، فإن الخريطة:
يحدد تماثل الحلقة
بين حلقة الأعداد الصحيحة حسابيات معيارية و المنتج المباشر لحلقات الأعداد الصحيحة حسابيات ni. هذا يعني أنه لإجراء سلسلة من العمليات الحسابية في Z/NZ، يمكن للمرء أن يفعل الشيء نفسه الحساب بشكل مستقل في كل Z/niZ ثم الحصول على النتيجة من خلال تطبيق التماثل (من اليمين إلى اليسار). قد يكون هذا أسرع بكثير من الحساب المباشر إذا كانت N و عدد العمليات كبيرًا. يستخدم هذا على نطاق واسع، تحت اسم الحساب متعدد الوحدات، للجبر الخطي على الأعداد الصحيحة أو الأرقام المنطقية.
يمكن أيضًا إعادة صياغة النظرية في لغة التوافقية حيث أن التدرجات الحسابية اللانهائية للأعداد الصحيحة تشكل عائلة هيلي.
الدليل والاثبات
يمكن إثبات وجود الحل و تفرده بشكل مستقل. و مع ذلك، فإن أول دليل على الوجود، الوارد أدناه، يستخدم هذا التفرد.
التفرد
افترض أن x و y كلاهما حلين لكل التطابقات. بما أن x و y يعطيان الباقي نفسه، عند القسمة على ni، فإن الفرق بينهما x – y هو مضاعف كل ni. نظرًا لأن ni عبارة عن جريمة مشتركة زوجية، فإن ناتجها N يقسم أيضًا x – y، و بالتالي فإن x و y هما مقياسان متطابقان N. إذا كان من المفترض أن يكون x و y غير سالبين و أقل من N (كما في العبارة الأولى من النظرية)، فقد يكون الاختلاف بينهما من مضاعفات N فقط إذا كانت x = y.
وجود (أول دليل)
الخريطة:
تطابق فئات الخرائط حسابيات معيارية N إلى متواليات فئات التطابق حسابيات معيارية ni. يُظهر الدليل على التفرد أن هذه الخريطة هي حقنة. نظرًا لأن المجال السري لهذه الخريطة لهما نفس عدد العناصر، فإن الخريطة أيضًا تخمينية، مما يثبت وجود الحل.
هذا الدليل بسيط للغاية و لكنه لا يوفر أي طريقة مباشرة لحساب حل. علاوة على ذلك، لا يمكن تعميمها على مواقف أخرى حيث يمكن للأدلة التالية.
وجود (دليل بناء)
يمكن إثبات الوجود من خلال بناء صريح لـ x. يمكن تقسيم هذا البناء إلى خطوتين، أولاً عن طريق حل المشكلة في حالة وجود نمطين، و الثاني عن طريق توسيع هذا الحل للحالة العامة عن طريق الاستقراء على عدد الوحدات.
حالة اثنين من المعادلات
نريد حل النظام:
حيث n1 و n2 هي جريمة مشتركة.
تؤكد هوية بيزوت وجود عددين صحيحين m1 و m2 على هذا النحو: m1 n1 + m2n2 = 1
يمكن حساب الأعداد الصحيحة m1 و m2 بواسطة الخوارزمية الإقليدية الموسعة.
يتم إعطاء حل بواسطة: x = a1 m2 n2 + a2m1n1
في الواقع،
مما يعني أن x≡ a1 (الوضع n1). تم إثبات التطابق الثاني بالمثل، من خلال تبادل الحرفين 1 و 2.
الحالة العامة
ضع في اعتبارك سلسلة من معادلات التطابق:
X ≡ a1 (mod n1) …. x ≡ ak (mod nk)
حيث ni هي جريمة مشتركة. المعادلتان الأوليان لهما الحل a1،2 المقدم من طريقة القسم السابق. مجموعة حلول هاتين المعادلتين الأوليين هي مجموعة جميع حلول المعادلة
X ≡ a1،2 (mod n1،2)
نظرًا لأن ni الآخر عبارة عن n1n2، فإن هذا يقلل من حل المشكلة الأولية لمعادلات k إلى مشكلة مماثلة مع معادلات k-1. بتكرار العملية، يحصل المرء في النهاية على حلول المشكلة الأولية.
وجود (بناء مباشر)
لإنشاء حل، ليس من الضروري إجراء تحريض على عدد الوحدات. و مع ذلك، فإن مثل هذا البناء المباشر ينطوي على مزيد من الحسابات بأعداد كبيرة، مما يجعلها أقل كفاءة وأقل استخدامًا. و مع ذلك، فإن استيفاء لاغرانج هو حالة خاصة لهذا البناء، يتم تطبيقه على كثيرات الحدود بدلاً من الأعداد الصحيحة.
لنفترض أن Ni = N / ni هو نتاج جميع المقاييس باستثناء واحدة. نظرًا لأن ni عبارة عن جريمة مشتركة زوجية، فإن Ni و n هما جريمة مشتركة. و هكذا تنطبق هوية بزوت، و هناك أعداد صحيحة Mi و mi من القبيل MiNi + mini = 1. حل نظام التطابق هو
في الواقع، نظرًا لأن Nj هو مضاعف ni لـ I ≠ j، فلدينا
لكل i.
حساب
ضع في اعتبارك نظام التطابق:
X ≡ a1 (mod n1)
…
X ≡ ak (mod nk)
حيث ni هي أولية نسبية زوجية، و دع N = n1n2 … nk.
في هذا القسم، تم وصف عدة طرق لحساب الحل الفريد لـ x، بحيث يتم تطبيق 0 ≥ x < N و هذه الطرق على المثال:
X ≡ 0 (mod 3)
X ≡ 3 (mod 4)
X≡ 4 (mod 5)
البحث المنهجي
من السهل التحقق مما إذا كانت قيمة x حلاً: يكفي حساب باقي القسمة الإقليدية لـ x بواسطة كل ni. و بالتالي، لإيجاد الحل، يكفي التحقق من الأعداد الصحيحة من 0 إلى N على التوالي حتى إيجاد الحل.
على الرغم من بساطتها، إلا أن هذه الطريقة غير فعالة للغاية. بالنسبة للمثال البسيط المدروس هنا، يجب التحقق من 40 عددًا صحيحًا (بما في ذلك 0) لإيجاد الحل، و هو 39. هذه خوارزمية زمنية أسية، حيث أن حجم الإدخال يصل إلى عامل ثابت، و عدد أرقام N، و متوسط عدد العمليات بترتيب N.
لذلك، نادرًا ما يتم استخدام هذه الطريقة، لا للحسابات المكتوبة بخط اليد ولا على أجهزة الكمبيوتر.
البحث عن طريق الغربلة
الصورة: أصغر حلين، 23 و 128، من الصيغة الأصلية لمشكلة نظرية الباقي الصينية التي تم العثور عليها باستخدام منخل.
قد يكون البحث عن الحل أسرع بشكل كبير عن طريق الغربلة. بالنسبة لهذه الطريقة، نفترض، دون فقدان العمومية، أن ai < ni (إذا لم يكن الأمر كذلك، فسيكفي استبدال كل ai ببقية تقسيمه بواسطة ni). هذا يعني أن الحل ينتمي إلى التقدم الحسابي
a1 ، a1 + n1 ، a1 + 2n1 ، …
من خلال اختبار قيم هذه الأرقام، المقياس n2، يجد المرء في النهاية حلاً x2 من التطابقين الأولين. ثم الحل ينتمي إلى التقدم الحسابي
x2 ، x2 + n1n2 ، x2 + 2n1n2 ، …
اختبار قيم هذه الأعداد بمعامل n3 والاستمرار حتى يتم اختبار كل معامل يعطي الحل في النهاية.
تكون هذه الطريقة أسرع إذا تم ترتيب المعادلات عن طريق تقليل القيمة، أي إذا كانت n1 > n2 > ….> nk.
على سبيل المثال، هذا يعطي الحساب التالي.
نعتبر أولاً الأرقام المتطابقة مع 4 مقياس 5 (أكبر معامل)، وهي 4، 9 = 4 + 5، 14 = 9 + 5، … لكل منها، احسب الباقي بمقدار 4 (الثاني أكبر معامل) حتى الحصول على رقم مطابق لـ 3 مقياس 4. يمكن بعد ذلك المضي قدمًا بإضافة 20 = 5 × 4 في كل خطوة، و حساب الباقي فقط بمقدار 3.
هذا يعطي
4 mod 4 → 0.
استمر..
4 + 5 = 9 mod 4 →1.
استمر..
9 + 5 = 14 mod 4 → 2.
استمر..
14 + 5 = 19 mod 4 → 3.
حسنًا، استمر في النظر في الباقي بالمقياس 3 وإضافة 5 × 4 = 20 في كل مرة
19 mod 3 → 1.
استمر..
19 + 20 = 39 mod 3 → 0.
حسنًا، هذه هي النتيجة.
تعمل هذه الطريقة بشكل جيد مع الحساب المكتوب يدويًا باستخدام منتج من وحدات ليست كبيرة جدًا. و مع ذلك، فهي أبطأ بكثير من الطرق الأخرى، بالنسبة للمنتجات الكبيرة جدًا من الوحدات. على الرغم من أن هذه الطريقة أسرع بشكل كبير من البحث المنهجي، إلا أن هذه الطريقة لها أيضًا تعقيد زمني أسي و بالتالي لا يتم استخدامها على أجهزة الكمبيوتر.
استخدام بناء الوجود
يُظهر إثبات الوجود البناء أنه في حالة وجود نمطين، يمكن الحصول على الحل من خلال حساب معاملات بيزوت الخاصة بالمعايير، متبوعة ببعض عمليات الضرب والإضافات والتخفيضات n1n2 (للحصول على نتيجة في الفترة 0، n1n2 – 1). نظرًا لأن معاملات بيزوت يمكن حسابها باستخدام الخوارزمية الإقليدية الموسعة، فإن الحساب بأكمله، على الأكثر، له تعقيد زمني من الدرجة الثانية O(s1 + s2)2، حيث يشير si إلى عدد أرقام ni.
بالنسبة لأكثر من نمطين، تسمح طريقة المعاملين باستبدال أي تطابقين بوحدة تطابق واحدة لمنتج المعاملين. يوفر تكرار هذه العملية في النهاية للحل تعقيدًا، و هو تربيعي في عدد أرقام منتج جميع الوحدات. لا يعتمد هذا التعقيد الزمني التربيعي على الترتيب الذي يتم فيه إعادة تجميع الوحدات. يمكن للمرء إعادة تجميع المعاملين الأولين، ثم إعادة تجميع المعامل الناتج مع المعامل التالي، و هكذا. هذه الإستراتيجية هي الأسهل في التنفيذ، و لكنها تتطلب أيضًا مزيدًا من الحسابات التي تتضمن أعدادًا كبيرة.
تتمثل الإستراتيجية الأخرى في تقسيم المعادلات إلى أزواج يكون لمنتجها أحجام قابلة للمقارنة (قدر الإمكان)، و تطبيق، بالتوازي، طريقة اثنين من المعاملين لكل زوج، والتكرار مع عدد من الوحدات مقسومًا تقريبًا على اثنين. تسمح هذه الطريقة بموازنة الخوارزمية بسهولة. أيضًا، إذا تم استخدام خوارزميات سريعة (و هي خوارزميات تعمل في وقت شبه خطي) للعمليات الأساسية، فإن هذه الطريقة توفر خوارزمية للحساب الكامل الذي يعمل في وقت شبه خطي.
في المثال الحالي (الذي يحتوي على ثلاثة نماذج فقط)، كلا الاستراتيجيتين متطابقتان و تعملان على النحو التالي.
متطابقة بيزو (صيغة تربط عددين وقاسمهم المشترك الأكبر) لـ 3 و 4 هي 1 × 4 + (- 1) × 3 = 1.
وضع هذا في الصيغة المعطاة لإثبات الوجود يعطي 0 × 1 × 4 + 3 × (-1) × 3 = -9
لحل التطابقين الأولين، يتم الحصول على الحلول الأخرى عن طريق إضافة أي مضاعف لـ 3 × 4 = 12. إلى -9، يمكن للمرء أن يستمر مع أي من هذه الحلول، ولكن الحل 3 = -9 +12 أصغر (في القيمة المطلقة) و بالتالي ربما يؤدي إلى عملية حسابية أسهل. مطابقة بيزوت لـ 5 و 3 × 4 = 12 هي 5 × 5 + (- 2) × 12 = 1.
بتطبيق نفس الصيغة مرة أخرى، نحصل على حل للمشكلة : 25 × 3-24 × 4 = 21-.
يتم الحصول على الحلول الأخرى بإضافة أي من مضاعفات 3 × 4 × 5 = 60، وأصغر حل موجب هو 21− + 60 = 39.
نظام ديوفانتاين خطي
يمكن إعادة كتابة نظام التطابق الذي تم حله بواسطة نظرية الباقي الصينية كنظام من معادلات ديوفانتين الخطية المتزامنة:
x = a1 + xini
…
x = ak + xknk ،
حيث الأعداد الصحيحة المجهولة هي x و xi. لذلك، يمكن استخدام كل طريقة عامة لحل مثل هذه الأنظمة لإيجاد حل نظرية الباقي الصينية، مثل اختزال مصفوفة النظام إلى شكل سميث العادي أو النموذج العادي هيرمايت. و مع ذلك، كالمعتاد عند استخدام خوارزمية عامة لمشكلة أكثر تحديدًا، فإن هذا النهج أقل كفاءة من طريقة القسم السابق، بناءً على الاستخدام المباشر لهوية بيزوت.
المجالات المثالية الرئيسية
في قسم بيان – تصريح النظريه، تم ذكر نظرية الباقي الصيني بثلاث طرق مختلفة: من حيث الباقي، و التطابق، و تماثل الحلقة. لا ينطبق البيان من حيث الباقي، بشكل عام، على المجالات المثالية الرئيسية، حيث لم يتم تعريف الباقي في مثل هذه الحلقات. و مع ذلك، فإن النسختين الأخريين لهما معنى على المجال المثالي الرئيسي R: يكفي استبدال “عدد صحيح” بـ “عنصر المجال” و Z بواسطة R.
هاتان النسختان من النظرية صحيحة في هذا السياق، لأن البراهين (باستثناء إثبات الوجود الأول)، تستند إلى ليما إقليدس وهوية بيزوت، و هي صحيحة على كل مجال رئيسي. و مع ذلك، بشكل عام، فإن النظرية ليست سوى نظرية وجود ولا توفر أي طريقة لحساب الحل، ما لم يكن لدى المرء خوارزمية لحساب معاملات هوية بيزوت.
تعميم نظرية الباقي الصينية على تعديل وحدات وحدات غير مغطاة
يمكن تعميم نظرية الباقي الصينية على معاملات غير مغطاة. لنفترض أن m ، n ، a ، b أي أعداد صحيحة، دع g = gcd(m، n)، و اعتبر نظام التطابق:
X≡ a (mod m)
X≡ b (mod n)
إذا كان a ≡ b (mod g)، فإن نظام المعادلات هذا له معامل حل فريد lcm(m، n) = mn / g. خلاف ذلك، ليس لديها حلول.
إذا استخدمنا هوية بيزوت لكتابة g = um + vn، فالحل هو
هذا يحدد عددًا صحيحًا، حيث أن g تقسم كل من m و n. و بخلاف ذلك، يكون الدليل مشابهًا جدًا لإثبات معاملات المشاركة في الجريمة.
تعميم نظرية الباقي الصينية على الحلقات العشوائية
يمكن تعميم نظرية الباقي الصيني على أي حلقة، باستخدام مُثُل الجريمة الجماعية (و تسمى أيضًا المُثُل الكومكسيمالية). مثالان I و J هما جريمة مشتركة إذا كان هناك عنصران i ϵ I و j ϵ J مثل i + j = 1. تلعب هذه العلاقة دور هوية بيزوت في البراهين المتعلقة بهذا التعميم، والتي، بخلاف ذلك، متشابهة جدًا. يمكن ذكر التعميم على النحو التالي.
دع I1، … ، Ik تكون مُثلًا ذات وجهين للحلقة R و دع I تكون تقاطعهم. إذا كانت المثل العليا هي الجريمة الزوجية، فلدينا التماثل:
بين حلقة خارج القسمة R / I والمنتج المباشر لـ R / Ii حيث يشير “x mod I” إلى صورة العنصر x في حلقة خارج القسمة المحددة بواسطة المثالي I. علاوة على ذلك، إذا كانت R تبادلية، فإن التقاطع المثالي بين المثل العليا للجريمة المشتركة يساوي منتجهم؛ هذا هو
إذا كان Ii و Ij جريمة مشتركة لـ I ≠ j.
تطبيقات نظرية الباقي الصينية
ترقيم التسلسل
تم استخدام نظرية الباقي الصينية لبناء ترقيم Gödel للتسلسلات، والتي تشارك في إثبات نظريات عدم اكتمال Gödel.
تحويل فورييه السريع
تستخدم خوارزمية FFT الرئيسية (تسمى أيضًا خوارزمية Good-Thomas) نظرية الباقي الصينية لتقليل حساب تحويل فورييه السريع بالحجم n1n2 إلى حساب تحولي فورييه سريعين بأحجام أصغر n1 و n2.
التشفير
تستخدم معظم تطبيقات RSA نظرية الباقي الصينية أثناء توقيع شهادات HTTPS وأثناء فك التشفير.
يمكن أيضًا استخدام نظرية الباقي الصينية في المشاركة السرية، والتي تتكون من توزيع مجموعة من الأسهم بين مجموعة من الأشخاص الذين يمكنهم، معًا (ولكن لا أحد بمفرده)، استعادة سر معين من مجموعة الأسهم المحددة. يتم تمثيل كل سهم في تطابق، و حل نظام التطابق باستخدام نظرية الباقي الصينية هو السر الذي يجب استرداده. تستخدم المشاركة السرية باستخدام نظرية الباقي الصينية، جنبًا إلى جنب مع نظرية الباقي الصينية، تسلسلات خاصة من الأعداد الصحيحة التي تضمن استحالة استعادة السر من مجموعة من المشاركات التي تحتوي على عدد أقل من عدد أصلي معين.
الملفات المرفقة
