كيف يمكن للمرء أن تنفيذ الضرب في مجالات محدودة؟

Question

إذا F: = GF (ص ^ ن) هو مجال محدود مع ص ^ ن العناصر، حيث p عدد أولي وغ عدد طبيعي، هل هناك أي خوارزمية فعالة لعمل من نتاج عنصرين في F؟

وهنا أفكاري حتى الآن:

وأنا أعلم أن بناء القياسية من F هو أخذ و متعدد الحدود غير القابل للاختزال ن درجة في GF (ع) ومن ثم عرض عناصر F كما متعددو الحدود في GF القسمة (ع) [X] / (و)، و لدي شعور بأن هذا هو على الارجح بالفعل النهج الصحيح منذ الضرب متعدد الحدود وعلاوة على ذلك ينبغي أن تكون سهلة التنفيذ، لكنني بطريقة ما أن أرى كيف يمكن القيام بذلك في الواقع. على سبيل المثال، كيف يمكن للمرء أن يختار لو المناسبة، وكيف يمكنني الحصول على الدرجة تكافؤ متعدد الحدود التعسفي؟

Answer 1

أولا اختيار متعدد الحدود غير القابل للاختزال ن درجة على GF [ص]. فقط توليد منها بشكل عشوائي، متعدد الحدود العشوائي غير القابل للاختزال مع احتمال ~ 1 / ن .

لاختبار متعددو الحدود عشوائية الخاص بك، فإنك سوف تحتاج إلى بعض الرمز إلى متعددو عامل على GF [ص]، انظر> وأ href = "http://en.wikipedia.org/wiki/Polynomial_factorization" يختلط = "noreferrer نوفولو" > الصفحة يكيبيديا للحصول على بعض الخوارزميات.

وبعد ذلك العناصر الخاصة بك في GF [ص ^ ن] ليست سوى متعددو الحدود ن درجة على GF [ص]. مجرد القيام بعملية حسابية متعدد الحدود طبيعي وتأكد لحساب ما تبقى MODULO متعدد الحدود غير القابل للاختزال الخاص بك.

وانها جميلة سهلة إلى رمز تصل إصدارات بسيطة من هذا المخطط. يمكنك الحصول على معقد بشكل تعسفي في كيفية تطبيق، ويقول، ومعامل باقي القسمة. انظر حدات الأسي و <لأ href = "http://en.wikipedia.org/wiki / Montgomery_reduction "يختلط =" noreferrer نوفولو "> مونتغمري الضرب ، والضرب باستخدام الاتحاد الفرنسي للتنس.

Answer 2

وإذا كان هناك خوارزمية فعالة لعناصر تتضاعف في GF (ص ^ ن) يعتمد على كيفية كنت تمثل عناصر GF (ص ^ ن).

كما قلت، اتجاه واحد هو في الواقع للعمل في GF (ع) (X) / (و). الجمع والضرب هي نسبيا واضحة هنا. ومع ذلك، وتحديد مناسبة غير القابل للاختزال و متعدد الحدود ليست سهلة - كما بقدر ما أعرف ليس هناك خوارزمية فعالة لاحتساب و مناسبة.

وهناك طريقة أخرى لاستخدام ما يسمى زكريا في . الصهارة الاستخدامات الجداول منهم قبل احتساب مقابل العمل مع الحقول المنتهية الصغيرة. فمن الممكن أن GAP لا أيضا، على الرغم من وثائقها أقل وضوحا.

والحوسبة مع الهياكل الرياضية غالبا ما تكون صعبة جدا. أنت بالتأكيد لا تغفل أي شيء واضح هنا.

Answer 3

وذلك يعتمد على احتياجاتك وفي مجال عملك.

عند تتضاعف لديك لاختيار مولد F <سوب> س . عند إضافة لديك لاستخدام حقيقة أن F هو الفضاء ناقلات على بعض أصغر F <الفرعية> ص <سوب> م . في ممارسة ما تفعله الكثير من الوقت وبعض نهج مختلط. مثلا إذا كنت تعمل على F <الفرعية> 256 ، واتخاذ مولد X من F <الفرعية> 256 <سوب> س ، والسماح G سواء كان ذلك من الحد الأدنى من متعدد الحدود على F <الفرعية> 16 . لديك الآن

و(مجموع <الفرعية> أنا أصغر ثم 16 على <الفرعية> أنا X <سوب> أنا ) (مجموع <الفرعية> ي أصغر ثم 16 ب < فرعية> ي X <سوب> ي ) = sum_k مبلغ <الفرعية> ط + ي = ك على <الفرعية> أنا ب <الفرعية> ي X <سوب> ط + ي

وكل ما عليك القيام به لجعل الضرب كفاءة، وتخزين الجدول multipication من F <الفرعية> 16 ، و(باستخدام G) بناء X ^ م من حيث القوى السفلية من X والعناصر في F < فرعية> 16

وFinanly، في حالة نادرة حيث ف <سوب> ن = 2 <سوب> 2 <سوب> ن ، وتحصل على الحقل كونواي من nimbers (نظرة في كونواي "الفوز طرق "، أو في قسم 4A حجم نث 7.1.3)، التي توجد خوارزميات فعالة للغاية.

Answer 4

جالويس الميدان الحساب مكتبة (C ++، وزارة الدفاع 2، لا تبدو وكأنها تدعم العناصر الرئيسية الأخرى)

LinBox (C ++)

MPFQ (C ++)

وليس لدي أي تجربة شخصية ث / هذه، ولكن (جعلت لي الطبقات الخاصة البدائي C ++ لحقول جالويس من درجة 31 أو أقل، لا شيء غريب جدا أو يستحق النسخ). مثل واحد من المعلقين المذكورة، قد تحقق mathoverflow.net - فقط أسأل لطيف وتأكد من أنك قد فعلت المنزلية الخاصة بك أولا. هناك شخص ما يجب أن نعرف ما هي أنواع البرامج الرياضية مناسبة للتلاعب من الحقول المنتهية، وأنه يكفي قريبة من منطقة mathoverflow للاهتمام أن السؤال جاء جيدا لا يجب ان تحصل على إغلاقها.