باستخدام وظائف التجزئة مع مرشحات بلوم

Question

يستخدم مرشح Bloom وظيفة تجزئة (أو كثيرة) لإنشاء قيمة بين 0 و M بالنظر إلى سلسلة الإدخال X. سؤالي يمثله طول 32 hex السلسلة ، كيف يمكنني استخدام خوارزمية التجزئة MD5 لإنشاء قيمة بين 0 و M حيث يمكنني تحديد M؟ أنا أستخدم Java في الوقت الحالي ، لذا فإن مثالًا على القيام بذلك من خلال وظائف MessagedIgest التي يقدمها سيكون رائعًا ، على الرغم من أن الوصف العام لكيفية القيام به حيال ذلك سيكون جيدًا أيضًا.

شكرًا

Answer 1

يجب عليك أولاً تحويل إخراج التجزئة إلى عدد صحيح غير موقّع ، ثم تقليله م. هذا يبدو هكذا:

MessageDigest md = MessageDigest.getInstance("MD5");
// hash data...
byte[] hashValue = md.digest();
BigInteger n = new BigInteger(1, hashValue);
n = n.mod(m);
// at that point, n has a value between 0 and m-1 (inclusive)

لقد افترضت ذلك م هو BigInteger نموذج. إذا لزم الأمر ، استخدم BigInteger.valueOf(). وبالمثل ، الاستخدام n.intValue() أو n.longValue() للحصول على قيمة ن كواحد من الأنواع البدائية من جافا.

التخفيض المعياري متحيز إلى حد ما ، لكن التحيز صغير جدًا إذا م أصغر بكثير من 2^128.

Answer 2

من المحتمل أن تكون أبسط طريقة هي تحويل إخراج التجزئة (كتسلسل بايت) إلى رقم ثنائي واحد واتخاذ هذا modulo m.