هذه المقالة يتيمة. ساعد بإضافة وصلة إليها في مقالة متعلقة بها

نظرية التطابق الخطية

من أرابيكا، الموسوعة الحرة

هذه هي النسخة الحالية من هذه الصفحة، وقام بتعديلها عبود السكاف (نقاش | مساهمات) في 19:33، 12 ديسمبر 2022 (بوت: إصلاح التحويلات). العنوان الحالي (URL) هو وصلة دائمة لهذه النسخة.

(فرق) → نسخة أقدم | نسخة حالية (فرق) | نسخة أحدث ← (فرق)
اذهب إلى التنقل اذهب إلى البحث

في الرياضيات ونظرية الاعداد، نظرية التطابق الخطية تجيب عن السؤال: هل يمكن حل تطابق خطي؟ , ومعادلة التطابق الخطي هي من الصورة التالية:

فليكن a,b,n ثلاث اعداد طبيعية مُعروفة المعادلة هي: axb(modn) والمسألة هي ايجاد كل x يحقق المعادلة.[1]

تعريفات

نرمز ب- a مولد الزمرة الجزئية ل- Zn التي تتولد بواسطة a . بما انه يتحقق a={ax(modn):x>0} للمعادلة اعلاه يوجد حل فقط إذا ba . من مبرهنة لاجرانج ينص على |a| يُقسم n . سوف نستخدم المبرهنة التالية لتحديد عدد الحلول للمعادلة وايضا لتحديد إذا ما يمكن حلها اصلا.

مبرهنة

فليكن d=GCD(a,n) حينها a=d={0,d,2d,,(nd1)d} ولذا |a|=nd

برهان

نبدأ البرهان بأن نبين أنَّ da وبما أنَّ d=GCD(a,n) لذا فانه حسب نظرية اقليدس الموسعة يوجد x,y عددان صحيحان حيث يتحقق ax+ny=d لذا axd(modn) لذا da حسب التعريف.

بما أنَّ da أيضا كل مضاعفاتها كذلك تابعة ل-a وبما ان مضاعفات مضاعفات a هي أيضا مضاعفات a لذا فان a يحوي المجموعة {0,d,2d,,(nd1)d} وبالتي يتحقق da .

يتبقى ان نبرهن أنَّ ad . إذا ma حينها يوجد x بحيث يتحقق m=ax(modn) لذا فانه يوجد عدد صحيح y حيث يتحقق m=ax+ny . بما أنَّ d|a وكذلك d|n لذا فانه يتحقق d|m لذا فانه يتحقق dd .

لذا فانه يتحقق أنَّ d=a . ننتبه إلى انه بين 0 و- n-1 يوجد nd مضاغفات الرقم d لذا فانه يتحقق: |a|=nd

تحديد إذا ما يوجد حلول وعددها

  1. المعادلة axb(modn) يوجد لها حل فقط إذا GCD(a,n)|b .
  2. المعادلة axb(modn) يوجد لها d حلول عندما d=GCD(a,n) أو لا يوجد حلول البتة

المقولتان 1+2 بالواقع هما استنتاج من المبرهنة اعلاه.

إنتاج الحلول

على الاقل حل واحد

فليكن d=GCD(a,n) ولنفرض أنَّ d=ax+ny حيث أنَّ x,y عددان صحيحان، إذا d|b حينها أحد الحلول للمعادلة axb(modn) هو x0=xbd(modn) .

برهان:

بما أنَّ axd(modn) لذا:

ax0ax(bd)(modn)

d(bd)(modn)
b(modn)

من هذا ينبع أنَّ x0 هو حل كذلك.

إنتاج كل الحلول

لنفرض أن axb(modn) ولنفرض أنَّ x0 هو حل للمسألة، حينها للمعادلة هذه يوجد d حلول التي هي: i{1,2,,d1}xi=x0+ind في حين أنَّ d=GCD(a,n) .

خوارزمية حل المعادلات

الآن بما انه يمكن إنتاج كل الحلول وقد برهنا على ذلك لذا فاننا الآن صار بيدينا كل المقومات لخوارزمية تنتج هذه الحلول وهي كالتالي: (الخوارزمية بلغة MATLAB).

% ax=b mod n نريد ان نحل المعادلة 
function x=MLES(a,b,n)
% نحسب اولا القاسم المشترك الاكبر حسب الخوارزمية اقليدس الموسعة
[d,x1,y1]=egcd(a,n);
% هذه المصفوفة فيها نحفظ كل الحلول
x=zeros(1,d);
%حينها يوجد حلول b|d  اذا تحقق  
if mod(b,d)==0
    % الحل الاول حسب المبرهنة
    x0=mod(x1*b/d,n);
    % انتاج باقي الحلول
    for k=1:d
        x(1,k)=mod(x0+k*(n/d),n);
    end
else
    % لا يوجد حلول
    x=[];
end
end

تعقيد وقت الخوارزمية هو O(logn+gcd(a,n)) وذلك لاننا استخدمنا خوارزمية اقليدس مرة ثم الحلقة (loop) استخدمناها d مرات.

حالات خاصة

عندما GCD(a,n)=1 حينها يوجد حل واحد للمعادلة، كما انه يوجد حالة أخرى هي عندما b=1 حينها الحل المطلوب هو مقلوب العدد a ويمكن حسابه بواسطة خوارزمية اقليدس الموسعة فقط وهذا يجعل إنتاجه اسرع.

امثلة

معطاه المعادلة 35x10(mod50) علينا ايجاد كل الحلول:

  1. نريد ان نحسب GCD(35,50) والذي هو 5 , كما نحسب x و- y حيث أنَّ 35x+50y=5 , لذا فان قيمتهما هي x=3,y=-2 .
  2. نفحص هل b|d ? حسب المعادلة b=10 و- d=5 . لذا فان الجواب نعم ولذا يوجد 5 حلول (حسب المبرهنات)
  3. أول حل هو: x0=xbd(modn)=3105(mod50)=6(mod50)
  4. اما باقي الحلول فهي:
    • 6+110(mod50)=16(mod50)
    • 6+210(mod50)=26(mod50)
    • 6+310(mod50)=36(mod50)
    • 6+410(mod50)=46(mod50)

انظر أيضا

مصادر

  1. ^ "معلومات عن نظرية التطابق الخطية على موقع mathworld.wolfram.com". mathworld.wolfram.com. مؤرشف من الأصل في 2020-03-19.
  • introduction to algorithms , CE Leiserson, RL Rivest, C Stein, TH Cormen - 2001