خوارزميات F4 و F5 لفوغير

في الجبر الحاسوبي ، تُستخدم خوارزمية Faugère F4 ، التي وضعها جان-شارل فاوغير ، لحساب أساس غروبنر لمثالي في حلقة متعددة المتغيرات متعددة الحدود . تستخدم هذه الخوارزمية نفس المبادئ الرياضية لخوارزمية بوخبيرغر ، ولكنها تحسب العديد من الأشكال الطبيعية دفعة واحدة من خلال تكوين مصفوفة متفرقة بشكل عام ، واستخدام الجبر الخطي السريع لإجراء عمليات الاختزال بالتوازي.

تقوم خوارزمية Faugère F5 أولاً بحساب أساس Gröbner لزوج من كثيرات الحدود المولدة للمثالي. ثم تستخدم هذا الأساس لتقليل حجم المصفوفات الأولية للمولدات للأساس الأكبر التالي:

إذا كانت G _prev هي أساس Gröbner محسوب بالفعل ( f ₂ , …, f _m ) ونريد حساب أساس Gröbner لـ ( f ₁ )  + G _{prev ،} فسوف نقوم بإنشاء مصفوفات صفوفها هي m f ₁ بحيث يكون m أحادي الحد غير قابل للقسمة على الحد الرئيسي لعنصر من G _prev .  

تُمكّن هذه الاستراتيجية الخوارزمية من تطبيق معيارين جديدين بناءً على ما يُسميه فوجير " توقيعات كثيرات الحدود". وبفضل هذين المعيارين، تستطيع الخوارزمية حساب قواعد غروبنر لفئة واسعة من أنظمة كثيرات الحدود المهمة، والتي تُسمى المتتاليات المنتظمة ، دون الحاجة إلى تبسيط أي كثيرة حدود إلى الصفر - وهي العملية الأكثر استهلاكًا للوقت في الخوارزميات التي تحسب قواعد غروبنر. كما أنها فعّالة للغاية مع عدد كبير من المتتاليات غير المنتظمة.

تم تطبيق خوارزمية Faugère F4

• في FGb ، وهو تطبيق خاص بفوغير، والذي يتضمن واجهات لاستخدامه من C/C++ أو Maple ،
• في نظام الجبر الحاسوبي Maple ، كخيار method=fgb للدالة Groebner[gbasis]
• في نظام الجبر الحاسوبي ماجما ،
• في نظام الجبر الحاسوبي SageMath ،

تم تطبيق نسخ دراسية من خوارزمية Faugère F5 في

• نظام الجبر الحاسوبي SINGULAR ؛ ^{[ 1 ]}
• نظام SageMath للجبر الحاسوبي.
• في حزمة SymPy Python . ^{[ 2 ]}

تم حل مشكلة "الدورية 10" التي كانت مستعصية في السابق بواسطة F5، وكذلك عدد من الأنظمة المتعلقة بالتشفير؛ على سبيل المثال HFE و C ^* .

• فوغير، جيه.-سي. (يونيو 1999). "خوارزمية جديدة فعّالة لحساب قواعد غروبنر (F ₄ )" (ملف PDF) . مجلة الجبر البحت والتطبيقي . 139 (1): 61-88 . doi : 10.1016/S0022-4049(99)00005-5 . ISSN 0022-4049 . 
• فوغير، جيه.-سي. (يوليو 2002). "خوارزمية جديدة فعّالة لحساب قواعد غروبنر دون اختزال إلى الصفر ( _F5 ) ". وقائع الندوة الدولية لعام 2002 حول الحساب الرمزي والجبري (ملف PDF) . مطبعة ACM. الصفحات 75-83 . CiteSeerX 10.1.1.188.651 . doi : 10.1145/780506.780516 . ISBN   978-1-58113-484-1. S2CID 15833106 . 
• حتى إعادة النظر في خوارزمية F5 لـ Stegers Faugère ( رابط بديل ). أطروحة دبلوم الرياضيات، المستشار يوهانس بوخمان، جامعة دارمشتات التقنية، سبتمبر 2005 (تمت المراجعة في 27 أبريل 2007). العديد من المراجع، بما في ذلك وصلات للتطبيقات المتاحة.

• الصفحة الرئيسية لفوغير (تتضمن نسخًا بصيغة PDF لأوراق بحثية إضافية)
• مقدمة عن خوارزمية F4.