العثور على معكوس عملية Modulo

Question

لقد قمت بإنشاء خوارزمية لتحويل رقم سداسي عشري إلى سلسلة أبجدية رقمية، ولكن الآن أريد إنشاء معكوس هذه الخوارزمية.الخوارزمية باختصار هي كما يلي:

الرقم السداسي العشري % طول مصفوفة الأحرف الأبجدية الرقمية = الفهرس في مصفوفة الأحرف الأبجدية الرقمية

على سبيل المثال، تأخذ الخوارزمية رقمًا سداسيًا عشريًا 4e (78 بالنظام العشري)، يقوم بتعديله بحجم مصفوفة أحرف أبجدية رقمية (الحجم: 62)، وإرجاع رقم عشري 16, ، وهو أ G.يتم تنظيم مصفوفة الأحرف الأبجدية الرقمية في هذا المثال على النحو التالي:(0-9، من الألف إلى الياء، من الألف إلى الياء).

باختصار هذا المثال مكتوب على النحو التالي: (4e)78 % 62 = 16(G)

عكس هذه الخوارزمية هو ما آمل تحقيقه ومن خلال اختبارات مختلفة، يبدو أنه يمكن أن تحدث نتائج متعددة، لكن هدفي النهائي هو أن ينتهي بي الأمر بخوارزمية قابلة للعكس، حيث، على سبيل المثال، رقم سداسي عشري 4e يتم تحويله إلى حرف G ثم العودة مرة أخرى إلى 4e عند وضعها من خلال الخوارزمية العكسية.من المثال، قمت بتطوير وصف محتمل للخوارزمية العكسية:

لنفترض أن لدينا معادلة معيارية.يترك x تكون الأرباح، y يكون المقسوم عليه، و r يكون الباقي. r و y يتم إعطاء أين r=16 و y=62.العثور على x مثل ذلك x % y = r أو x % 62 = 16.

الحل الذي قمت بتجربته :Bruteforce الأرباح

لن تكون الأرباح أبدًا خارج الفترة المغلقة [0, 255] نظرًا لأن زوجًا من الأرقام السداسية العشرية يمكن أن يكون له قيمة قصوى ff, ، الذي 255 في العشري.وبالتالي، إذا قمنا باختبار x مقابل المعادلة المعيارية حتى نحصل على باقي متساو، فيمكننا استخلاص المقسوم.

ومع ذلك، فإن هذا الحل سوف يؤدي إلى احتمالات متعددة x القيم بسبب عملية modulo التي تسبب تأثيرًا التفافيًا في المصفوفة الأبجدية الرقمية، مما يعني أن القيم المتعددة يمكن أن تتسبب في جعل المعادلة صحيحة.في حالة المثال المقدم، يؤدي الحل المقترح إلى الأرباح التالية: 16, 78, 140, ، و 202.العائد الثاني هو الصحيح والذي يؤدي إلى عكس الخوارزميات.ومع ذلك، تكمن المشكلة في العثور عليه، نظرًا لعدم معرفة الخيار الصحيح مباشرةً في وقت تشغيل الخوارزمية العكسية.

أي مساعدة في ابتكار حل لطريقتي المقترحة أو حل مختلف سيكون موضع تقدير كبير.شكرًا.

Answer 1

وانتهى بي الأمر بحل مشكلتي، ولكن ليس بالطريقة التي كنت أتوقعها.يتضمن الحل النصف المتأصل لسلسلة الإخراج.باستخدام هذا، يمكن للمرء ببساطة حساب حاصل القسمة x بواسطة y واستخدام ذلك باعتباره الحرف الأبجدي الرقمي الثاني، لتكوين زوج.في المثال المعطى، النتيجة G قد يصبح G1 لأن الحساب المعياري يتضمن التكرار على مصفوفة الأحرف الأبجدية الرقمية مرة واحدة.

الخوارزمية الآن هي كما يلي: x % y = r + (x / y), ، والذي يمكن عكسه بسهولة عن طريق تحطيم الأرباح المحتملة واختيار التوزيع الصحيح ببساطة باستخدام الحرف الثاني في الزوج الأبجدي الرقمي.وبالتالي، أصبحت هذه الخوارزمية المعدلة الآن قابلة للعكس وقد ثبت أنها تعمل مع المثال الوارد في السؤال الأصلي.