دوارة فروبينوس: أسس نظامية بلا تعداد ✛ ✎
بمجرد أن تبدأ الحركة، تدور دوارة فروبينوس: ينتقل كل عنصر من الحقل المحدود إلى خليفته من الدرجة q، وتنزاح الإحداثيات دورياً. هذه العملية — تحليل فورييه — قد وصفها Carl Friedrich Gauss في أبحاثه الحسابية، لكن زمناً طويلاً لم يكن تشغيل الدوارة بدون اختلالات ممكناً إلا بتعداد شامل أو التلاعب بالمصفوفات.
سر الدوران السلس يكمن في الترتيب الصحيح: يجب إيجاد المحاكاة العددية بحيث يقوم التشاكل الذاتي بتبديل عناصره دورياً ببساطة. يقترح مؤلفو الورقة ألا يجربوا التذاكر عشوائياً، بل أن يحسبوا مباشرة قائمة بكل الأماكن المعيبة. من أجل التمديد من الدرجة n، يبنون عائلة من المرشحين $β_t$ = (θ − t)⁻¹ — أشبه بمقاعد على المنصة، وتقريباً جميعها صالحة.
جوهر الطريقة هو الحساب فائق السرعة لـ التحليل الطيفي ذي المدخلات الحدودية. تُختزل المصفوفة إلى متعددة حدود مميزة في جبر مزود بقاعدة غروبنر (Groebner basis)، ويتفادى الرفع p-أدي خبيث (p-adic lifting) الأصفار في مقامات صيغ لفيرييه (Leverrier's formulas). بفضل تقنية المجموعات المثلثة والتركيب المودولي (modular composition)، يستغرق الحساب كله زمناً شبه خطي بالنسبة لحجم الدخل — O_ϵ((n² log q)^{1+ϵ}) عملية بت. بالنسبة للحقول الصغيرة، يُوسع الحقل مؤقتاً بضرب لوغاريتمي، يُبنى عنصر نظامي هناك، ثم يُعاد بعناية — وكل هذا التحسين.
الآن، تدور الدوارة لا بعينين مغمضتين، بل بمعرفة تامة بنقطة الانطلاق الآمنة. يمنح هذا نظرية المعلومات متانة مضمونة، ولأنظمة الجبر الحاسوبي قابلية إعادة إنتاج الحسابات. الخطوة التالية هي تسريع الغرافات (graphs) إلى زمن خطي حقاً، وعندئذ سينخفض التعقيد الكلي إلى O˜(n²). فيما مضى كان غاوس يدوّر الأعداد يدوياً؛ أما اليوم فالدوارة الخوارزمية تفعل ذلك في أجزاء من الثانية، تاركةً لنا الإعجاب بالرياضيات البحتة.
إذا كان n=1000 و q عدداً أولياً يزيد قليلاً عن 10⁶، فإن عدد قيم t 'السيئة' لا يتجاوز 10⁶، وسيكون تعداد مليون قيمة فقط كافياً — وهي مهمة ممكنة حتى باستخدام آلة حاسبة مكتبية. الفكرة كلها هي ألا نفعل ذلك بالتعداد الغبي، بل بحساب متعددة حدود واحدة وتقييمها في n(n−1)+1 نقطة.