👨🏿‍🤝‍👨🏽 👨🏻‍🎤 🈯️ شيشوا: أسرع مولد أرقام عشوائية زائف في العالم 🔀 🚧 📙

قبل ستة أشهر ، أردت إنشاء أفضل مولد أرقام عشوائي (PRNG) مع بعض العمارة غير العادية. اعتقدت أن البداية ستكون سهلة ، وأثناء عملك ، ستصبح المهمة أكثر تعقيدًا ببطء. وفكرت إذا كنت أستطيع أن أتعلم كل شيء بالسرعة الكافية للتعامل مع أصعب.

ولدهشتي ، لم يزد التعقيد خطياً. ثبت أن اختبار Chi-square byte صعب للغاية! في وقت لاحق كان من الصعب اجتياز اختبارات قاسية. لقد نشرت النتائج الحالية لفهم الصعوبات الأخرى التي تنتظرني. ومع ذلك ، فشل اختبار PractRand في ذلك الوقت .

ثم كان من الصعب للغاية اجتياز اختبار BigCrush .

ثم كان من الصعب للغاية نقل 32 تيرابايت من البيانات عند تمرير PractRand. أصبحت السرعة مشكلة. لم يكن كافياً إنشاء تصميم يولد عشرة ميغابايت في الثانية ، لأن اجتياز PractRand سيستغرق شهرًا. ولكن يجب أن أعترف أنه كان من الصعب للغاية اجتياز هذا الاختبار بسرعة غيغابايت في الثانية .

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

لقد نجحت.

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

هدف

لنبدأ بالواضح: تعتمد السرعة على النظام الأساسي . ركزت على تحسين بنية x86-64 الحديثة (معالجات Intel و AMD).

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

لتحسين cpb ، يمكنك:

توليد المزيد من البايتات بنفس القدر من العمل ،
أو قم بعمل أقل لتوليد نفس عدد البايتات ،
أو مواز العمل.

سنفعل كل ما سبق.

وفقًا للنقطة الأولى ، نحتاج إلى إنتاج المزيد من البتات عند كل تكرار.

كنت أخشى أن يخبروني: "إذا لم تعط أرقام 32 بت ، فهذا ليس PRSP" ، أو نفس الشيء مع أرقام 64 بت. أو: "يجب أن يكون PRNG مخصصًا فقط للهندسة المعمارية x86-64" ، كما لو كانت الإرشادات مثل POPCNT أو السجلات مثل٪ xmm7 محظورة.

ومع ذلك ، فإن PRNG هندسة: مولدات تحاول منذ عدة عقود الضغط على كل شيء ممكن خارج المعالجات! عندما ظهر ROL ، بدأوا في الاعتماد عليه. مع ظهور معالجات 64 بت ، بدأوا في الاعتماد على٪ rax. بالطبع ، يمكن لهذه الخوارزميات أن تعمل بشكل أبطأ على ARM (على الرغم من أنه لا يزال يتعين رؤيتها) ، ومع ذلك ، تم استخدام PRNs 64 بت بنشاط حتى قبل أن يبدأ Android في طلب دعم 64 بت في 2019!

أي أن هذه المنطقة تتطور جنبًا إلى جنب مع الأجهزة. واليوم ، تدعم معالجات Intel و AMD بسبب AVX2 بالفعل عمليات 256 بت. أنتجت RC4 1 بايت ، يمكن أن ينتج drand48 4 بايت في المرة الواحدة ، pcg64 - 8 بايت ، والآن يمكننا على الفور توليد 32 بايت.

يمكن أن تكون 8 بايت عدد 64 بت ، ومعظم لغات البرمجة لها أنواع مدمجة لذلك. لكن القليل من اللغات توفر أنواعًا لـ 16 بايت (الاستثناء الملحوظ هو __uint128_t في C). حتى عدد أقل من اللغات لها نوع لـ 32 بايت (باستثناء الداخلية).

لذلك يمكننا أن نقول وداعًا للنموذج الأولي المعتاد لوظيفة PRNG (مثال من معيار Vigny HWD ):

static uint64_t next(void);

بدلاً من ذلك ، يمكنك إنشاء مولد يملأ المخزن المؤقت (مثال من قياس الأداء الخاص بي ):

void prng_gen(prng_state *s, __uint64_t buf[], __uint64_t size);

ما هي عيوب هذا الحل؟

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

نقوم الآن بتوليد المزيد من وحدات البايت ، ونقوم بنفس مقدار العمل. كيف نوازيها؟

تماثل

تقدم المعالجات مجموعة رائعة من أدوات الموازاة على جميع المستويات.

أولاً ، هذه تعليمات SIMD (تعليمات فردية ، بيانات متعددة). على سبيل المثال ، يقوم AVX2 بتنفيذ أربعة إضافات 64 بت في نفس الوقت ، أو ثمانية إضافات 32 بت ، إلخ.

تم استخدامه في التشفير لمدة خمسة عشر عامًا تقريبًا. قدم التزامن الأداء المذهل لـ ChaCha20 . يتم استخدامه من قبل الأوليات الأكثر أهمية والتي لا تستخدم AESNI. على سبيل المثال ، تم تصميم NORX و Gimli مع مراعاة التوازي.

في الآونة الأخيرة ، ازداد الاهتمام بهذا الموضوع أيضًا في مجتمع PRNG غير المشفر. على وجه الخصوص ، يمكن أن تكون الأوليات الموجودة التي لم يتم تصميمها لـ SIMD هي الأساس لإنشاء PRNs سريعة جدًا.

عندما قام Sebastiano Vigna بترويج بنية xoshiro256 ++ الخاصة به في مكتبة جوليا القياسية ، اكتشف أن نتائج ثمانية حالات PRNG تنافسية ومختلفة بشكل مختلف يمكن أن تتسلسل بسرعة كبيرة إذا تم تنفيذ كل عملية في وقت واحد في جميع PRNRs.

SIMD ليست سوى واحدة من مستويات التوازي في المعالج. أوصي بقراءة المقالة السابقة حول هذا الموضوع من أجل الحصول على فكرة أفضل ، ولكن سأقدم بعض التفسيرات. تسمح

خطوط أنابيب المعالج بمعالجة عدة تعليمات في مراحل مختلفة. إذا قمت بتنظيم ترتيب التنفيذ بشكل جيد من أجل تقليل التبعيات بين المراحل ، فيمكنك تسريع معالجة التعليمات.

يسمح لك تنفيذ Superscalar بمعالجة أجزاء الحوسبة من التعليمات في وقت واحد. ولكن لهذا لا ينبغي أن يكون لديهم تبعيات القراءة والكتابة. يمكنك تعديل البنية لتقليل خطر التوقف عن طريق التسجيل قبل وقت طويل من القراءة. يسمح

التنفيذ الاستثنائي للمعالج بتنفيذ التعليمات ليس بترتيب التسلسل ، ولكن عندما تكون جاهزة ، حتى لو لم تكن التعليمات السابقة جاهزة بعد. ولكن لهذا يجب ألا يكون هناك تبعية للقراءة والكتابة.

والآن ننتقل إلى التنفيذ!

هندسة معمارية

خذ بعين الاعتبار مخطط يسمى شبه شيشوا. من أين يأتي هذا الاسم ، سيظهر تدريجيًا أثناء قراءتك.

يبدو المخطط كما يلي:

النظر في خطه سطرا.

typedef struct prng_state {
  __m256i state[2];
  __m256i output;
  __m256i counter;
} prng_state;

تنقسم الحالة إلى جزأين ، يتم وضعهما في سجل AVX2 (256 بت). لزيادة السرعة ، نبقي النتيجة قريبة من الدولة نفسها ، لكنها ليست جزءًا من الدولة.

لدينا أيضًا عداد 64 بت. لتبسيط الحساب ، فهو أيضًا سجل AVX2. الحقيقة هي أن AVX2 لديه ميزة صغيرة: لا يمكن نقل السجلات العادية (٪ rax وما شابه) مباشرة إلى SIMD عبر MOV ، يجب أن تمر عبر ذاكرة الوصول العشوائي (في الغالب من خلال المكدس) ، مما يزيد من التأخير ويكلف تعليمات معالجين (MOV على المكدس ، VMOV من المكدس).

الآن دعونا نلقي نظرة على الجيل. لنبدأ بالتحميل ، ثم نذهب عبر المخزن المؤقت ونملأه بـ 32 بايت عند كل تكرار.

inline void prng_gen(prng_state *s, __uint64_t buf[], __uint64_t size) {
  __m256i s0 = s->state[0], counter = s->counter,
          s1 = s->state[1],       o = s->output;
  for (__uint64_t i = 0; i < size; i += 4) {
    _mm256_storeu_si256((__m256i*)&buf[i], o);
    // …
  }
  s->state[0] = s0; s->counter = counter;
  s->state[1] = s1; s->output  = o;
}

نظرًا لأن الوظيفة مضمنة ، فإن ملء المخزن المؤقت عند بدء التشغيل يتيح للمعالج تنفيذ التعليمات على الفور بناءً على ذلك من خلال آلية تنفيذ استثنائية.

داخل الحلقة ، نقوم بسرعة بإجراء ثلاث عمليات حالة:

شي قدم
شو فلي
A ي

ومن هنا جاء اسم شيشوا!

الوردية الأولى

u0 = _mm256_srli_epi64(s0, 1);              u1 = _mm256_srli_epi64(s1, 3);

لسوء الحظ ، لا يدعم AVX2 عمليات المراجعة. لكني أريد المزج بين بتات موضع ما في رقم 64 بت مع بتات موضع آخر! والتحول هو أفضل طريقة لتحقيق ذلك. سوف ننتقل برقم فردي ، بحيث يقوم كل بت بزيارة جميع مواقع 64 بت ، وليس نصفها.

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

سننتقل إلى اليمين ، لأن البتات الموجودة في أقصى اليمين لها أدنى انتشار أثناء الإضافة: على سبيل المثال ، أقل بت معتبر في A + B هو فقط XOR للبتات الأقل أهمية A و B.

التقليب

t0 = _mm256_permutevar8x32_epi32(s0, shu0); t1 = _mm256_permutevar8x32_epi32(s1, shu1);

سنستخدم خلط 32 بت ، لأنه يعطي دقة مختلفة مقارنة بعمليات 64 بت التي نستخدمها في كل مكان (تم انتهاك محاذاة 64 بت). يمكن أن تكون أيضًا عملية عبر الحارات: يمكن أن تقوم المراوغات الأخرى بتحريك البتات داخل 128 بت اليسرى إذا بدأت على اليسار ، أو داخل 128 بت الأيمن إذا بدأت في اليمين.

خلط الثوابت:

__m256i shu0 = _mm256_set_epi32(4, 3, 2, 1, 0, 7, 6, 5),
        shu1 = _mm256_set_epi32(2, 1, 0, 7, 6, 5, 4, 3);

حتى يؤدي هذا الخلط إلى تحسين النتيجة حقًا ، سننقل الأجزاء 32 بت الضعيفة (التشتت المنخفض) من إضافات 64 بت إلى المواضع القوية ، بحيث تثريها الإضافات التالية.

لا يتحرك الجزء 32 بت المنخفض من القطعة 64 بت إلى نفس القطعة 64 بت مثل الجزء عالي الترتيب. وبالتالي ، لا يبقى كلا الجزأين داخل نفس القطعة ، مما يحسن الاختلاط.

في النهاية ، يمر كل جزء 32 بت عبر جميع المواضع في دائرة: من أ إلى ب ، ومن ب إلى ج ، ... من ح إلى أ.

لعلك لاحظت أن أبسط خلط يراعي كل هذه المتطلبات هو اثنان بت 256 بت معدل دوران (ثورات 96 بت و 160 بت إلى اليمين ، على التوالي).

إضافة

دعونا نضيف قطع 64 بت من متغيرين مؤقتين - التحول والخلط.

s0 = _mm256_add_epi64(t0, u0);              s1 = _mm256_add_epi64(t1, u1);

الإضافة هي المصدر الرئيسي للتشتت: في هذه العملية ، يتم دمج البتات في مجموعات غير قابلة للاختزال من تعبيرات XOR و AND موزعة على مواضع 64 بت.

يحفظ تخزين نتيجة الإضافة ضمن حالة دائمة هذا التشتت.

وظيفة الإخراج

من أين نحصل على الناتج؟

الأمر بسيط: تسمح لنا البنية التي أنشأناها بتوليد جزأين مستقلين للحالة s0 و s1 ، لا يؤثران على بعضهما البعض بأي شكل من الأشكال. تطبيق XOR عليهم والحصول على نتيجة عشوائية تماما.

لتعزيز الاستقلالية بين البيانات التي نطبق عليها XOR ، نحصل على نتيجة جزئية: الجزء المتحول من دولة والجزء المختلط من دولة أخرى.

o = _mm256_xor_si256(u0, t1);

هذا مشابه لتقليل تبعيات القراءة والكتابة بين التعليمات في معالج فائق السرعة ، كما لو كان u0 و t1 جاهزين للقراءة إلى s0 و s1.

ناقش الآن العداد. نعالجها في بداية الدورة. أولاً ، قم بتغيير الحالة ، ثم قم بزيادة قيمة العداد:

s1 = _mm256_add_epi64(s1, counter);
counter = _mm256_add_epi64(counter, increment);

لماذا نغير الحالة أولاً ، ثم نقوم بتحديث العداد؟ يصبح s1 متاحًا في وقت سابق ، وهذا يقلل من احتمال توقف الإرشادات اللاحقة التي تقرأه في خط أنابيب المعالج. كما يساعد هذا التسلسل على تجنب الاعتماد المباشر لعداد القراءة والكتابة.

نطبق العداد على s1 ، وليس على s0 ، لأنهما يؤثران على الإخراج على أي حال ، ومع ذلك ، تفقد s1 المزيد من البتات بسبب التحول ، وهذا يساعدها على "الوقوف على قدميها" بعد التحول.

قد لا يسجل العداد اختبار PractRand. الغرض الوحيد منه هو تعيين حد أدنى 2 ⁶⁹بايت = 512 exbibytes لفترة PRNG: نبدأ في تكرار الدورة فقط بعد ألفية العمل بسرعة 10 غيغابايت في الثانية. من غير المرجح أن تكون بطيئة للغاية للاستخدام العملي في القرون القادمة.

زيادة راتب:

__m256i increment = _mm256_set_epi64x(1, 3, 5, 7);

يتم اختيار الأرقام الفردية كزيادات ، لأن أرقام النسخ الأساسية فقط تغطي الدورة الكاملة للحقل المحدود GF (2 ⁶⁴ ) ، وجميع الأرقام الفردية هي برمجة مشتركة لـ 2. وبعبارة أخرى ، إذا قمت بزيادة بمقدار صحيح في النطاق من 0 إلى 4 ، والعودة إلى 0 بعد 4 ، نحصل على التسلسل 0-2-0-2- ... ، والذي لن يؤدي أبدًا إلى 1 أو 3. وتتجاوز الزيادة الفردية جميع الأعداد الصحيحة.

بالنسبة لجميع أرقام 64 بت في الحالة ، سنستخدم أرقامًا فردية مختلفة ، والتي ستفصلها بشكل أكبر وتزيد من الخلط قليلاً. اخترت أصغر الأرقام الفردية بحيث لا تبدو سحرية.

هذه هي الطريقة التي تعمل بها وظيفة انتقال الحالة والإخراج. كيفية تهيئة لهم؟

التهيئة

نقوم بتهيئة الحالة باستخدام الأرقام السداسية العشرية Φ ، وهو الرقم غير العقلاني الأقل تقريبًا بالكسر.

static __uint64_t phi[8] = {
  0x9E3779B97F4A7C15, 0xF39CC0605CEDC834, 0x1082276BF3A27251, 0xF86C6A11D0C18E95,
  0x2767F0B153D27B7F, 0x0347045B5BF1827F, 0x01886F0928403002, 0xC1D64BA40F335E36,
};

خذ بذرة 256 بت. غالبًا ما يتم ذلك في التشفير ولا يضر بعمل PRNGs غير المشفرة:

prng_state prng_init(SEEDTYPE seed[4]) {
  prng_state s;
  // …
  return s;
}

لا نريد إعادة تعريف الجزء الكامل من الحالة (s0 أو s1) بهذا الرقم الأولي ، نحتاج فقط إلى التأثير على النصف. بهذه الطريقة سوف نتجنب استخدام الأرقام الأولية المخففة ، التي تؤدي عن غير قصد أو عن قصد إلى حالة أولية ضعيفة معروفة.

نظرًا لأننا لا نغير نصف كل حالة ، فإننا نحتفظ بالسيطرة على 128 بت الحالة. هذا الإنتروبيا يكفي لبدء والحفاظ على موقف قوي.

s.state[0] = _mm256_set_epi64x(phi[3], phi[2] ^ seed[1], phi[1], phi[0] ^ seed[0]);
s.state[1] = _mm256_set_epi64x(phi[7], phi[6] ^ seed[3], phi[5], phi[4] ^ seed[2]);

ثم نكرر ( ROUNDS) عدة مرات التسلسل التالي:

STEPSشغّل الخطوات ( ) لتكرارات SHISHUA.
نحن نعين جزءًا من الحالة إلى حالة أخرى ، والجزء الآخر إلى الإخراج.

for (char i = 0; i < ROUNDS; i++) {
  prng_gen(&s, buf, 4 * STEPS);
  s.state[0] = s.state[1];
  s.state[1] = s.output;
}

يؤدي تعيين نتيجة الإخراج إلى زيادة تشتت الحالة. أثناء التهيئة ، لا يهم العمل الإضافي وارتباط الحالات ، لأن هذه السلسلة من العمليات يتم تنفيذها مرة واحدة. نحن مهتمون فقط بالتشتت أثناء التهيئة.

بعد تقييم التأثير على ارتباط القيم الأولية ، اخترت STEPS2 للقيمة و ROUNDS10 لـ 10. قمت بحساب الارتباط عن طريق حساب الشذوذ "غير المعتاد" و "المشبوه" الناتج عن أدوات مراقبة الجودة PRNG في PractRand.

أداء

من الصعب قياس السرعة لعدة أسباب:

قد لا يكون قياس الساعة دقيقًا بما فيه الكفاية.
, , - , -, .
, . .
: , .

أستخدم تعليمات معالج RDTSC ، الذي يحسب عدد الدورات.

حتى يتمكن أي شخص من إعادة إنتاج نتائجي ، أستخدم آلة افتراضية قائمة على السحابة. هذا لا يغير مستوى النتائج المعيارية مقارنة بالاختبارات المحلية. بالإضافة إلى ذلك ، ليس عليك شراء نفس جهاز الكمبيوتر الخاص بي. أخيرًا ، هناك العديد من المواقف التي يتم فيها إطلاق PRNG في الغيوم.

اخترت Google Cloud Platform N2 (معالج Intel) و N2D (معالج AMD). ميزة GCP هي أنها تقدم خوادم مع معالجات من كلا المنتجين. في هذه المقالة ، سنركز على Intel ، ولكن بالنسبة إلى AMD ، فستكون النتائج بنفس الترتيب.

للتعمق في الموضوع ، دعنا أولاً نتخلص من مولد التشفير RC4 القديم. غير قادر على موازنة العمل ، فهمت7.5 cpb (دورات لكل بايت تم إنشاؤه).

الآن دعنا ندير MCG شائعة جدًا وسريعة: أظهر أبسط Lehmer128 PRNG ، الذي اجتاز اختبار BigCrush ، 0.5 cpb . نجاح باهر عظيم!

ثم سنقوم بتشغيل أحدث التطوير ، والذي يستخدم لجداول التجزئة السريعة - wyrand . 0.41 cpb ، أفضل قليلاً!

بعض أوراق استراتيجية الحد من الفقر لا تجتاز اختبار PractRand بسعة 32 تيرابايت ، لكنها تعمل بسرعة كبيرة. وصل Xoshiro256 + إلى 512 ميبي بايت فقط ، ولكنه أظهر سرعة عالية جدًا: 0.34 cpb .

آخر تطور حديث لـ RomuTrio . تدعي أنها أسرع PRNG في العالم - 0.31 cpb.

هذا يكفي. ماذا اظهر شبه شيشوا؟

0.14 cpb . ضعف سرعة RomuTrio.

رائع. الآن اختبار مولد التشفير ChaCha8. وصل ... 0.12 cpb .

يا.

SIMD هو سحر حقيقي!

بالنسبة لمجتمع التشفير ، لم تكن هذه مفاجأة خاصة . ChaCha8 من السهل للغاية موازاة ذلك. هذا مجرد عداد مجزأ جيدًا في حالة منتشرة.

وتذكر أيضًا كيف حاول فريق لغة جوليا الجمع بين العديد من أمثلة هندسة Vigny لإنشاء PRNG سريع قائم على SIMD؟ دعونا نلقي نظرة على نتائجهم باستخدام هذه التقنية ( 8 قطع من Xoshiro256 + ). 0.09 قدم مكعب !

من الناحية الفنية ، يمكن أن يؤثر جهاز الكمبيوتر المحمول على النتائج. لست متأكدًا من سبب تطوير فريق Julia بشكل أسرع من ChaCha8 في GCP ، ولكنه أبطأ عند اختباره محليًا. على جهازي ، تعمل شبه SHISHUA بشكل أسرع من تطوير فريق Julia ، ولكن أبطأ من ChaCha8.

من الضروري هزيمة جميع المنافسين.

ربما تسأل بالفعل لماذا أطلقنا على الإصدار السابق من مولد شبه SHISHUA؟ لأنه تبين أنه من السهل مضاعفة السرعة إذا قمت بتشغيل نسختين من شبه شيشوا.

على غرار فكرة أمر Julia ، نقوم بشكل منفصل بتهيئة اثنين من PRNGs (أربع كتل من حالة 256 بت) ، مع توفير ناتج عملهما بالتناوب.

ولكن إذا أنشأنا المزيد من الحالات ، فيمكننا إنتاج المزيد من البيانات ، مع دمج أربع حالات في أزواج:

o0 = _mm256_xor_si256(u0, t1);
o1 = _mm256_xor_si256(u2, t3);
o2 = _mm256_xor_si256(s0, s3);
o3 = _mm256_xor_si256(s2, s1);

لذلك حصلنا على SHISHUA ، التي أظهرت سرعة 0.06 cpb .

هذا أسرع مرتين من أسرع منافس سابق في العالم ، والذي اجتاز اختبار PractRand 32 تيرابايت. والنتيجة على الرسم البياني.

أعتقد أن التطور أصبح تنافسيًا. إنه يعمل بشكل أسرع على جهاز الكمبيوتر المحمول الخاص بي - 0.03 cpb ، لكنني سألتزم بمبادئي فيما يتعلق بالمعيار.

نأمل لبضعة أسابيع أخرى أن يبقى المولد الخاص بي على منصة الأسرع في العالم (يرجى القيام بذلك).

جودة

يجتاز المولد بصدق اختبار BigCrush واختبار PractRand بسعة 32 تيرابايت. وكل ذلك بفضل أربعة تيارات الإخراج.

تشمل عيوب الهندسة المعمارية عدم رجوعها . يمكن ملاحظة ذلك عن طريق تقليل الحالة إلى 4 بت مع s0 = [a, b]و s1 = [c, d]. مع التحول ، نحصل [0, a]و [0, d]، مع التحريك ، [b, c]و [d, a]. الجديد s0يساوي [b, c] + [0, a] = [b⊕(a∧c), a⊕c]لكنه s1يساوي [d, a] + [0, c] = [d⊕(a∧c), a⊕c]. إذا a = ¬c، بعد ذلك، a⊕c = 1و a∧c = 0بالتالي، s0 = [b, 1]و s1 = [d, 1]. وهذا هو، نحصل على مجموعات من اثنين aو c، والتي تعطينا نفس الحالة النهائية.

في حالتنا ، هذه ليست مشكلة ، لأن عداد 64 بت هو أيضًا جزء من الحالة. اتضح الدورة الدنيا 2 ⁷¹بايت (128 بايت لكل حالة انتقال) ، بسرعة 10 غيغابايت / ثانية. سيستمر سبعة آلاف سنة. هذا يوازن الدول المفقودة.

بالإضافة إلى ذلك ، على الرغم من اللارجعة ، فإن متوسط الفترة الانتقالية بين الدول هو 2 ^ ((256 + 1) ÷ 2). هذا يعطي متوسط دورة ^2،135 بايت (بسرعة 10 غيغابت / ثانية. وسوف تستمر أكثر من تريليون مرة أطول من الكون الموجود). على الرغم من أنني أعتقد أن الدورات المتوسطة مبالغ فيها ، لأنها لا تخبرنا بأي شيء عن جودة المولد.

فيما يلي النتائج المرجعية:

مولد كهرباء	أداء	جودة	ارتباط البذور
شيشوا	0.06	> 32 تيرابايت	> 256 جيجا بايت
xoshiro256 + x8	0.09	1 كيب	0 كيب
ChaCha8	0.12	> 32 تيرا بايت؟	> 32 تيرا بايت؟
RomuTrio	0.31	> 32 تيرابايت	1 كيب
xoshiro256 +	0.34	512 ميجابايت	1 كيب
أرض	0.41	> 32 تيرابايت	8 كب
ليهمير 128	0.44	> 32 تيرابايت	1 كيب
RC4	7.48	1 تيرابايت	1 كيب

الأداء : عدد دورات المعالج التي يتم إنفاقها على بايت واحد تم إنشاؤه. تم استلام الطلب على الأجهزة السحابية N2 GCP و N2D (AMD) ، الأمر هو نفسه.
الجودة : المستوى الذي فشل فيه المولد في اجتياز اختبار PractRand. إذا لم تفشل ، فهناك علامة>. إذا لم يتم إثبات النتيجة ، فهناك علامة استفهام.
ارتباط أرقام البذور : اجتياز PractRand مع وحدات بايت متناوبة من ثمانية تيارات مع أرقام بذور 0 ، 1 ، 2 ، 4 ، 8 ، 16 ، 32 ، 64. نستخدم PractRand مع الالتفاف المزدوج والاختبارات المتقدمة.

بالإضافة إلى ذلك

على الرغم من أنه في حالتنا لا توجد مشاكل في اللارجعة ، لا يزال بإمكاننا تحسين SHISHUA.

في رأيي ، فإن PRNG المثالي له الخصائص التالية:

, 2¹⁰²⁴. 10 /. 10²⁸² , . «» ( ). , . , 128- NEON ARM? , , .
. , SHISHUA XOR . , .
, 2¹²⁸ ( ). SHISHUA, , . , ( ) (, , . 2).
إن تهيئة الحالة لها تشتت مثالي : كل بتات الرقم الأولي تؤثر على جميع بتات الحالة بنفس الاحتمال. أريد أن أعرف فيما يتعلق بالشيشوا.

واحدة من المشاكل التي تعوق تطور PRNGs والتشفير ككل هو عدم وجود أدوات أفضل للأغراض العامة. أحتاج إلى أداة يمكنها أن تعطيني على الفور نتيجة القياس الدقيقة حتى أتمكن من مقارنة البنى المختلفة على الطاير.

إن PracticeRand رائع مقارنة بما كان عليه من قبل:

لا يسمح بتقييم المولدات عالية الجودة ، مما يجعل من المستحيل مقارنتها ببعضها البعض. يجب أن نقول: "حسنًا ، بعد 32 تيرابايت ليس لديهم حالات شاذة ..."
يستغرق الأمر أسابيع لتشغيله ...

آمل أن يتحسن الوضع بشكل كبير قريبًا.

شيشوا: أسرع مولد أرقام عشوائية زائف في العالم

هدف