ابحث عن جذر modulo متعدد الحدود 2^r [مغلق

Question

لدي تعدد الحدود p وأود أن أجد y بحيث p (y) = 0 modulo 2^r.

لقد جربت شيئًا على غرار رفع Hensel ، لكنني لا أعرف ما إذا كان هذا يمكن أن ينجح ، بسبب الحالة المعتادة F '(y mod 2)! = 0 mod 2 وهذا غير صحيح عادة.

هل هناك خوارزمية مختلفة متاحة؟ أو هل يمكن للاختلاف في رفع هينسيل العمل؟

شكرا مقدما

Answer 1

افترض أن لديك حل a مثل ذلك f(a) = 0 mod 2^p. للقيام برفع Hensel للحصول على حل mod 2^(p+1), ، ينتهي بك الأمر إلى حلها

f'(a)*t = -f(a)/2^(p+1) mod 2

إلى عن على t.

إذا f'(a) = 0 mod 2, ، هناك احتمالان:

إذا كان 2 لا يقسم f(a)/2^(p+1), ، ثم لا توجد حلول mod 2^(p+1) (أو أي قوة أعلى من 2) الناتجة عن هذه القيمة a.

إذا كان 2 يقسم f(a)/2^(p+1), ، يعمل كل من 0 و 1 كقيم مقبولة لـ T ، وستحتاج إلى القيام بمصعد منفصل لكل منهما إذا كنت ترغب في العثور على جميع الحلول mod 2^r.

لاحظ أن a في النطاق [0,2^p) في كل خطوة ، لذلك عند حلها t, ، أنت تقيم f(x) و f'(x) في x=a, ، ليس x=a mod 2.