مرتبك على ميلر رابين
-
03-10-2019 - |
سؤال
كتمرين لنفسي ، أنا أقوم بتنفيذ اختبار Miller-Rabin. (العمل من خلال SICP). أنا أفهم نظرية فيرما الصغيرة وتمكنت من تنفيذ ذلك بنجاح. الجزء الذي أتعثر فيه في اختبار Miller-Rabin هو هذا العمل "1 mod n". أليس 1 mod n (n يجري عدد صحيح عشوائي) دائما 1؟ لذلك أنا في حيرة من أمري مع "الجذر التربيعي غير التافهة لـ 1 modulo n" لأنه في رأيي "1 mod n" هو دائمًا 1 عند التعامل مع قيم عدد صحيح. ماذا ينقصني؟
المحلول
1 متطابق مع 9 وزارة الدفاع 8 لذلك 3 هو الجذر التربيعي غير تافهة من 1 وزارة الدفاع 8.
ما تعمل معه ليس أرقامًا فردية ، ولكن مجموعات التكافؤ. [m]n
هل تعيين من جميع الأرقام x
مثل ذلك x
هو متطابق مع m
عصري n
. أي شيء يورزه أي عنصر من عناصر هذه المجموعة هو جذر تربيعي m
Modulo n
.
إعطاء أي n
, ، لدينا مجموعة من الأعداد الصحيحة Modulo N التي يمكننا أن نكتبها Zn
. هذه هي المجموعة (مجموعات) [1]n
, [2]n
, ... ,[n]n
. كل عدد صحيح يكمن في واحد وواحد فقط من هذه المجموعات. يمكننا تحديد الإضافة والضرب على هذه المجموعة بواسطة [a]n + [b]n = [a + b]n
وبالمثل للضرب. لذا جذر تربيعي [1]n
هو (عنصر n) [b]n
مثل ذلك [b*b]n = [1]n
.
في الممارسة العملية ، يمكننا الخلط m
مع [m]n
وعادة ما تختار العنصر الفريد ، m'
من [m]n
مثل ذلك 0 <= m' < n
كعنصر "ممثل" لدينا: هذا هو ما نعتقده عادة ك m mod n
. لكن من المهم أن نضع في اعتبارنا أننا "نستخدم التدوين" كما يقول علماء الرياضيات.
إليك بعض كود بيثون (غير الايديوماتيكي) حيث ليس لدي جهاز مترجم مترجم مخطط:
>>> def roots_of_unity(n):
... roots = []
... for i in range(n):
... if i**2 % n == 1:
... roots.append(i)
... return roots
...
>>> roots_of_unity(4)
[1, 3]
>>> roots_of_unity(8)
[1, 3, 5, 7]
>>> roots_of_unity(9)
[1, 8]
لذلك ، على وجه الخصوص (بالنظر إلى المثال الأخير) ، 17 هو جذر الوحدة Modulo 9. في الواقع ، 17^2 = 289 و 289 ٪ 9 = 1. العودة إلى تدويننا السابق [8]9 = [17]9
و ([17]9)^2 = [1]9
نصائح أخرى
هذا هو السبب في أن الصياغة كانت للجذر التربيعي غير التافهة 1. 1 هو جذر تربيعي تافهة من 1 ، لأي معامل n.
17 هو جذر تربيعي غير تافهة من 1 ، MOD 144. وهكذا 17^2 = 289 ، وهو متطابق مع 1 mod 144. إذا كان n prem هما الجذوران الوحيدتان. ومع ذلك ، بالنسبة للمركب n هناك عمومًا جذور مربعة متعددة. مع n = 144 ، تكون الجذور المربعة {1،17،55،71،73،89،127،143}.
أعتقد أن سوء الفهم يأتي من التعريف الذي يعطيه الكتاب عن الجذر غير التافهة:
"الجذر التربيعي غير التافهة لـ 1 modulo n" ، أي رقم لا يساوي 1 أو n - 1 الذي يساوي مربع 1 modulo n
حيث أعتقد أنه ينبغي أن يقول:
من هو المربع تتطابق إلى 1 modulo n