مرتبك على ميلر رابين

Question

كتمرين لنفسي ، أنا أقوم بتنفيذ اختبار Miller-Rabin. (العمل من خلال SICP). أنا أفهم نظرية فيرما الصغيرة وتمكنت من تنفيذ ذلك بنجاح. الجزء الذي أتعثر فيه في اختبار Miller-Rabin هو هذا العمل "1 mod n". أليس 1 mod n (n يجري عدد صحيح عشوائي) دائما 1؟ لذلك أنا في حيرة من أمري مع "الجذر التربيعي غير التافهة لـ 1 modulo n" لأنه في رأيي "1 mod n" هو دائمًا 1 عند التعامل مع قيم عدد صحيح. ماذا ينقصني؟

Answer 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

Answer 2

هذا هو السبب في أن الصياغة كانت للجذر التربيعي غير التافهة 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}.

Answer 3

أعتقد أن سوء الفهم يأتي من التعريف الذي يعطيه الكتاب عن الجذر غير التافهة:

"الجذر التربيعي غير التافهة لـ 1 modulo n" ، أي رقم لا يساوي 1 أو n - 1 الذي يساوي مربع 1 modulo n

حيث أعتقد أنه ينبغي أن يقول:

من هو المربع تتطابق إلى 1 modulo n