خوارزمية اللعنة

في مجال كشف الأخطاء ، تُعد خوارزمية دام خوارزمية للتحقق من الأرقام ، حيث تكشف جميع أخطاء الرقم الواحد وجميع أخطاء التبديل المتجاورة . وقد قدمها إتش. مايكل دام في عام 2004، ^[¹^] كجزء من أطروحته للدكتوراه بعنوان " المجموعات شبه المتناظرة تمامًا".

نقاط القوة والضعف

نقاط القوة

تُشبه خوارزمية دام خوارزمية فيرهوف ، إذ تكشف هي الأخرى جميع حالات النوعين الأكثر شيوعًا من أخطاء النسخ ، وهما تغيير رقم واحد أو تبديل رقمين متجاورين (بما في ذلك تبديل رقم التحقق الأخير والرقم السابق). ^{[ 1 ]}^{[ 2 ]} تتميز خوارزمية دام بأنها لا تتطلب التباديل المُنشأة خصيصًا وقوى خاصة بالموقع كما في خوارزمية فيرهوف . كما يُمكن الاستغناء عن جدول المعكوسات عندما تكون جميع عناصر القطر الرئيسي في جدول العمليات أصفارًا.

تقوم خوارزمية Damm بتوليد 10 قيم محتملة فقط، مما يتجنب الحاجة إلى حرف غير رقمي (مثل X في مخطط رقم التحقق ISBN المكون من 10 أرقام ).

لا يؤثر إضافة الأصفار البادئة على رقم التحقق (وهي نقطة ضعف في الرموز ذات الطول المتغير). ^{[ 1 ]}

توجد مجموعات شبه متناظرة تمامًا تكشف جميع الأخطاء الصوتية المرتبطة باللغة الإنجليزية ( 13 ↔ 30 ، 14 ↔ 40 ، ...، 19 ↔ 90 ). الجدول المستخدم في المثال التوضيحي مبني على حالة من هذا النوع.

نقاط الضعف

بالنسبة لجميع خوارزميات التحقق من المجموع، بما في ذلك خوارزمية دام، فإن إضافة أصفار بادئة لا تؤثر على رقم التحقق، ^{[ 1 ]} لذا فإن 1، 01، 001، إلخ، تُنتج نفس رقم التحقق. وبالتالي، لا ينبغي التحقق من الرموز ذات الأطوال المتغيرة معًا.

تصميم

يتكون الجزء الأساسي منه من شبه زمرة من الرتبة 10 (أي أن جدول عملياتها يتكون من مربع لاتيني 10 × 10 ) تتميز بكونها مضادة للتناظر كليًا بشكل ضعيف . ^[³^]^[⁴^]^[ⁱ^]^[ⁱⁱ^]^[ⁱⁱⁱ^] كشف دام عن عدة طرق لإنشاء شبه زمر مضادة للتناظر كليًا من الرتبة 10، وقدم بعض الأمثلة في أطروحته للدكتوراه. ^[³^]^[ⁱ^] وبهذا، دحض دام أيضًا فرضية قديمة مفادها أن شبه الزمر المضادة للتناظر كليًا من الرتبة 10 غير موجودة. ^[⁵^]

تُسمى شبه المجموعة $(Q ، *)$ مضادة للتناظر تمامًا إذا كانت الاستدلالات التالية صحيحة لجميع $c ، x ، y \in Q :$ ^{[ 4 ]}

$(ج \times س) \times ص = (ج \times ص) \times س \Rightarrow س = ص$
$x * y = y * x \Rightarrow x = y$ ,

ويُطلق عليه اسم شبه زمرة مضادة للتناظر كليًا ضعيفة إذا تحقق الشرط الأول فقط. أثبت دام أن وجود شبه زمرة مضادة للتناظر كليًا من الرتبة $n$ يُكافئ وجود شبه زمرة مضادة للتناظر كليًا ضعيفة من الرتبة $n$ . بالنسبة لخوارزمية دام مع معادلة التحقق $(...((0 * x m) * x m -1) * ...) * x 0 = 0$ ، يلزم وجود شبه زمرة مضادة للتناظر كليًا ضعيفة ذات الخاصية $x * x = 0.$ يمكن إنشاء مثل هذه الشبه زمرة من أي شبه زمرة مضادة للتناظر كليًا عن طريق إعادة ترتيب الأعمدة بحيث تقع جميع الأصفار على القطر. ومن ناحية أخرى، يمكن إنشاء شبه زمرة مضادة للتناظر كليًا من أي شبه زمرة مضادة للتناظر كليًا ضعيفة عن طريق إعادة ترتيب الأعمدة بحيث يكون الصف الأول في ترتيبه الطبيعي. ^{[ 3 ]}

الخوارزمية

تُعرَّف صحة تسلسل الأرقام الذي يحتوي على رقم التحقق على شبه زمرة. يمكن الحصول على جدول شبه زمرة جاهز للاستخدام من أطروحة دام (الصفحات 98، 106، 111). ^{[ 3 ]} من المفيد أن يكون كل عنصر من عناصر القطر الرئيسي $صفرًا$ ، ^{[ 1 ]} لأنه يُبسِّط حساب رقم التحقق.

التحقق من صحة الرقم مقابل رقم التحقق المرفق

قم بإعداد رقم مؤقت وقم بتهيئته إلى $0$ .
قم بمعالجة الرقم رقمًا برقم: استخدم رقم الرقم كمؤشر للعمود والرقم الوسيط كمؤشر للصف، خذ إدخال الجدول واستبدل الرقم الوسيط به.
يكون الرقم صالحًا إذا وفقط إذا ^كانت قيمة الرقم الوسيط الناتج تساوي $0.$ [ ^{1 ]}

حساب رقم التحقق

الشرط الأساسي: أن تكون قيم العناصر القطرية الرئيسية للجدول $صفرًا$ .

قم بإعداد رقم مؤقت وقم بتهيئته إلى $0$ .
قم بمعالجة الرقم رقمًا برقم: استخدم رقم الرقم كمؤشر للعمود والرقم الوسيط كمؤشر للصف، خذ إدخال الجدول واستبدل الرقم الوسيط به.
يُعطي الرقم الوسيط الناتج رقم التحقق، وسيتم إلحاقه كرقم لاحق بالرقم. ^{[ 1 ]}

مثال

سيتم استخدام جدول العمليات التالي. ^{[ 1 ]} يمكن الحصول عليه من شبه المجموعة المتناظرة تمامًا $x * y$ في أطروحة دام للدكتوراه صفحة 111 ^{[ 3 ]} عن طريق إعادة ترتيب الصفوف وتغيير المدخلات بالتبديل $φ = (1 2954867 3)$ وتعريف $x \cdot y = φ - 1 (φ (x) * y)$ .

$\cdot$	0	1	2	3	4	5	6	7	8	9
0	0	3	1	7	5	9	8	6	4	2
1	7	0	9	2	1	5	4	8	6	3
2	4	2	0	6	8	7	1	3	5	9
3	1	7	5	0	9	8	3	4	2	6
4	6	1	2	3	0	4	5	9	7	8
5	3	6	7	4	2	0	9	5	8	1
6	5	8	6	9	7	2	0	1	3	4
7	8	9	4	5	3	6	2	0	1	7
8	9	4	3	8	6	1	7	2	0	5
9	2	5	8	1	4	3	6	7	9	0

لنفترض أننا اخترنا الرقم (تسلسل الأرقام) 572 .

حساب رقم التحقق

الرقم المراد معالجته → فهرس العمود	5	7	2
الرقم المؤقت القديم → فهرس الصف	0	9	7
إدخال الجدول → رقم وسيط جديد	9	7	4

الرقم الوسيط الناتج هو 4. هذا هو رقم التحقق المحسوب. نضيفه إلى الرقم فنحصل على 5724 .

التحقق من صحة الرقم مقابل رقم التحقق المرفق

الرقم المراد معالجته → فهرس العمود	5	7	2	4
الرقم المؤقت القديم → فهرس الصف	0	9	7	4
إدخال الجدول → رقم وسيط جديد	9	7	4	0

الرقم الوسيط الناتج هو 0 ، وبالتالي فإن الرقم صحيح .

رسم توضيحي

هذا هو المثال أعلاه الذي يوضح تفاصيل الخوارزمية التي تولد رقم التحقق (السهم الأزرق المتقطع) والتحقق من الرقم 572 باستخدام رقم التحقق.

مراجع

1 2 3 4 5 6 7 8 فينويك، بيتر (2014). "مجموع التحقق والتحكم في الأخطاء". في فينويك، بيتر (محرر). مقدمة في تمثيل بيانات الحاسوب . دار بنثام للعلوم. الصفحات 191-218 . doi : 10.2174/9781608058822114010013 . ISBN 978-1-60805-883-9.
↑ للاطلاع على أنواع الأخطاء الشائعة وتكرارها، انظر: سالومون، ديفيد (2005). ترميز البيانات والاتصالات الحاسوبية . سبرينغر ساينس + بيزنس ميديا، ص 36. ISBN 978-0387-21245-6.
1 2 3 4 5 دام، إتش. مايكل (2004). مجموع مكافحة التماثل Quasigruppen (PDF) (Dr. rer. nat.) (في المانيا). جامعة فيليبس ماربورغ. جرة:nbn:de:hebis:04-z2004-05162 .
1 2 دام، هـ. مايكل (2007). "المجموعات شبه المتناظرة تمامًا لجميع الرتب n ≠ 2، 6" . الرياضيات المتقطعة . 307 (6): 715-729 . doi : 10.1016/j.disc.2006.05.033 . ISSN 0012-365X .
↑ دام، هـ. مايكل (2003). "حول وجود شبه زمر مضادة للتناظر كليًا من الرتبة 4k + 2 ". الحوسبة . 70 (4): 349-357 . doi : 10.1007/s00607-003-0017-3 . ISSN 0010-485X . S2CID 31659430 .

1 2 بيليافسكايا، غالينا؛ إزباش، فلاديمير؛ شيرباكوف، فيكتور (2003). "أنظمة التحقق من الأحرف على شبه الزمر والحلقات" (ملف PDF) . شبه الزمر والأنظمة ذات الصلة . 10 (1): 1-28 . ISSN 1561-2848 . انظر الصفحة 23.
↑ تشين جيانان (2009). "اكتمال NP لإكمال المربعات اللاتينية الجزئية المضادة للتناظر" (ملف PDF) . وقائع ورشة العمل الدولية لعام 2009 حول أمن المعلومات وتطبيقاتها (IWISA 2009) . دار النشر الأكاديمية. الصفحات 322-324 . ISBN 978-952-5726-06-0.انظر الصفحة 324.
↑Mileva, A.; Dimitrova, V. (2009). "Quasigroups constructed from complete mappings of a group (Z₂ⁿ,⊕)"(PDF). Contributions, Sec. Math. Tech. Sci., MANU/MASA. XXX (1–2): 75–93. ISSN 0351-3246. See page 78.

External links

Damm validation & generation code in several programming languages
Practical application in Singapore
Quasigroups for the Damm algorithm up to order 64
At RosettaCode.org, Implementations of the Damm algorithm in many programming languages

[fenwick2014-1] 1 2 3 4 5 6 7 8 فينويك، بيتر (2014). "مجموع التحقق والتحكم في الأخطاء". في فينويك، بيتر (محرر). مقدمة في تمثيل بيانات الحاسوب . دار بنثام للعلوم. الصفحات 191-218 . doi : 10.2174/9781608058822114010013 . ISBN 978-1-60805-883-9.

[Salomon2005-2] للاطلاع على أنواع الأخطاء الشائعة وتكرارها، انظر: سالومون، ديفيد (2005). ترميز البيانات والاتصالات الحاسوبية . سبرينغر ساينس + بيزنس ميديا، ص 36. ISBN 978-0387-21245-6.

[dhmd-3] 1 2 3 4 5 دام، إتش. مايكل (2004). مجموع مكافحة التماثل Quasigruppen (PDF) (Dr. rer. nat.) (في المانيا). جامعة فيليبس ماربورغ. جرة:nbn:de:hebis:04-z2004-05162 .

[damm2007-4] 1 2 دام، هـ. مايكل (2007). "المجموعات شبه المتناظرة تمامًا لجميع الرتب n ≠ 2، 6" . الرياضيات المتقطعة . 307 (6): 715-729 . doi : 10.1016/j.disc.2006.05.033 . ISSN 0012-365X .

[damm2003-8] دام، هـ. مايكل (2003). "حول وجود شبه زمر مضادة للتناظر كليًا من الرتبة 4k + 2 ". الحوسبة . 70 (4): 349-357 . doi : 10.1007/s00607-003-0017-3 . ISSN 0010-485X . S2CID 31659430 .

[BIS2003-5] 1 2 بيليافسكايا، غالينا؛ إزباش، فلاديمير؛ شيرباكوف، فيكتور (2003). "أنظمة التحقق من الأحرف على شبه الزمر والحلقات" (ملف PDF) . شبه الزمر والأنظمة ذات الصلة . 10 (1): 1-28 . ISSN 1561-2848 . انظر الصفحة 23.

[Chen2009-6] تشين جيانان (2009). "اكتمال NP لإكمال المربعات اللاتينية الجزئية المضادة للتناظر" (ملف PDF) . وقائع ورشة العمل الدولية لعام 2009 حول أمن المعلومات وتطبيقاتها (IWISA 2009) . دار النشر الأكاديمية. الصفحات 322-324 . ISBN 978-952-5726-06-0.انظر الصفحة 324.

[Mileva2009-7] Mileva, A.; Dimitrova, V. (2009). "Quasigroups constructed from complete mappings of a group (Z₂ⁿ,⊕)"(PDF). Contributions, Sec. Math. Tech. Sci., MANU/MASA. XXX (1–2): 75–93. ISSN 0351-3246. See page 78.

[

[ 2 ]

[

[

[

[

[

[