سؤال

إعطاء وظيفة y = f (a، x):

unsigned long F(unsigned long A, unsigned long x) {
    return  ((unsigned long long)A*X)%4294967295;
}

كيف يمكنني العثور على وظيفة معكوس x = g (a، y) مثل x = g (a، f (a، x)) لجميع قيم 'x'؟

إذا كانت F () غير قابلة للتحول لجميع قيم "X"، ما هو الأقرب إلى معكوس؟

(F هو PRNG عفا عليه الزمن، وأنا أحاول فهم كيفية تعكس أحد الوظائف).

  • محدث
    إذا كان الأمر الرئيسي نسبيا إلى (2 ^ n) -1، فإن g (a، y) هو فقط f (a-1، y).
    إذا لم يكن الأمر الرئيسي نسبيا، فستظل مجموعة y () موجودة إذا تقتصر على هذا النطاق؟
هل كانت مفيدة؟

المحلول

تحتاج إلى حساب معكوس A mod ((2^N) - 1), ، ولكن قد لا يكون لديك دائما عكس أعطيت معضلك. يرى هذا على Wolfram Alpha.

لاحظ أن

A = 12343 لديه معكوس (A ^ -1 = 876879007 وزارة الدفاع 4294967295)

لكن 12345 لا يملك معكوس.

وبالتالي، إذا كان رئيس نسبيا مع (2 ^ n) -1، ثم يمكنك بسهولة إنشاء وظيفة معكوس باستخدام خوارزمية Euclidean طويلة أين

g(A,y) = F(A^-1, y),

خلاف ذلك أنت بعيد.

تحديث: استجابة لسؤالك المحدث، لا يزال بإمكانك الحصول على عكس فريد في النطاق المقيد. حتى إذا كنت تستخدم حل القوة الغاشمة في CookieFfortune، فسوف تواجه مشاكل مثل

G(12345, F(12345, 4294967294)) == 286331152 != 4294967294.

نصائح أخرى

تحتاج إلى خوارزمية Euclidean طويلة. وبعد هذا يمنحك ص آن بذلك

gcd(A,2^N-1) = R * A + S * (2^N-1).

إذا كان GCD هو 1 ثم ص العكس المضاعف من A. ثم الوظيفة العكسية

g(A,y) = R*y mod (2^N-1).

حسنا، ها هو تحديث بالنسبة للقضية حيث G = GCD (A، 2 ^ n-1) ليست 1. في هذه الحالة

R*y mod (2^N-1) = R*A*x mod (2^N-1) = G*x mod (2^N-1).

إذا تم حساب y بواسطة الدالة F، ثم Y قابلة للقسمة بواسطة G. وبالتالي يمكننا تقسيم المعادلة أعلاه بواسطة G والحصول على معادلة Modulo (2 ^ n-1) / g. وبالتالي مجموعة الحلول هي

  x = R*y/G + k*(2^N-1)/G, where k is an arbitrary integer.

يتم إعطاء الحل هنا (http://en.wikipedia.org/wiki/linear_congruence_theorem.)، ويشمل دليلا على كيفية استخدام خوارزمية Euclidean الموسعة للعثور على الحلول.

وظيفة المعامل بشكل عام لا تملك معكوس وظيفة, ، ولكن يمكنك في بعض الأحيان العثور على مجموعة من X من خريطة X إلى ذ.

لدى Accipitridae، Glenn، وجيف مومر الإجابة بينهما، لكن الأمر يستحق شرح أكثر قليلا لماذا ليس لكل رقم معكوس تحت وزارة الدفاع 4294967295. السبب هو أن 4294967295 ليس عددا رئيسيا؛ هذا هو نتاج خمس عوامل: 3 × 5 × 17 × 257 × 65537. رقم عاشر لديه معاكس متضار تحت وزارة الدفاع م إذا وفقط إذا عاشر و م نكون coprime., ، لذلك لا يمكن لأي عدد من هذه العوامل أن يكون لديك عكس في وظيفتك.

هذا هو السبب في أن المعامل الذي تم اختياره لمثل هذه PRNGS هو عادة ما يكون رئيسا.

إيه ... هنا واحد الذي سيعمل:

unsigned long G(unsigned long A, unsigned long y)
{
    for(unsigned int i = 0; i < 4294967295; i++)
    {
        if(y == F(A, i)) return i);
    }
}
مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى StackOverflow
scroll top