بولارد رو العامل الصحيح

Question

أحاول تنفيذ عامل عدد صحيح في Pollard Rho في C/C ++. تعطيني Google تنفيذ Java للمشكلة هنا.

لا أعرف جافا جيدًا ، لذا ما توصلت إليه هذه. ينفذني في C ++ يعمل في معظم الحالات ولكن ليس في عدد قليل مثل "9999" ، اعتدت هناك.

أدرك أن C ++ لم يكن لديه فئة BigInteger ، لذا لا يمكنني الحصول على الوظائف الكاملة كما تعطي في Java ولكني أريد وضع 15 رقمًا في الأرقام الكافية unsigned long long

يرجى الإشارة إلى الخطأ في تنفيذي.

Answer 1

المشكلة هنا:

#define abs(x) (x>0)?(x):(-x)

أنت تفتقد بعض الأقواس في abs دقيق. محاولة:

#define abs(x) ((x)>0 ? (x) : -(x))

في حين أن. (فكر في ما يحدث عندما abs(x-xx) تم توسيعه في القضية x-xx <= 0.)

أيضا ، لماذا تعيد وظيفة GCD الخاصة بك int بدلاً من biginteger؟

يجب أن تدرك أيضًا أن (على افتراض أن الطويل غير الموقّع هو نوع عدد صحيح 64 بت) لن يعمل هذا الرمز بشكل صحيح من أجله N أكبر من 2**32: لو x (أو xx) أكبر من أو يساوي 2**32 من ثم x*x سوف لف modulo 2**64, ، يعطيك القيمة الخاطئة ل x*x % N.

Answer 2

لقد رصدت اختلافًا واحدًا: يعين رمز Java c و x ان نكون new BigInteger(N.bitLength(), random), ، في حين يستخدم رمز C ++ rand() % N, ، وهو نطاق عشوائي أصغر. بالنسبة للقيمة 9999 ، الثنائي هو 10011100001111 ، وبالتالي فإن رمز Java سوف يعطي c و x القيمة القصوى من 16383.