خوارزمية باخ

خوارزمية باخ هي خوارزمية احتمالية متعددة الحدود لتوليد الأعداد العشوائية وتحليلها إلى عواملها الأولية . نُشرت هذه الخوارزمية بواسطة إريك باخ عام ١٩٨٨. لا توجد خوارزمية معروفة تُحلل الأعداد العشوائية إلى عواملها الأولية بكفاءة، لذا فإن الطريقة المباشرة، أي توليد عدد عشوائي ثم تحليله إلى عوامله الأولية، غير عملية. ^{[ ١ ]}

تُجري الخوارزمية، في المتوسط، O (log n ) من اختبارات أولية الأعداد . وهناك خوارزمية أبسط ولكنها أقل كفاءة (تُجري، في المتوسط، O (log ² n ) من اختبارات أولية الأعداد)، وهي من ابتكار آدم كالاي . ^{[ 2 ] [ 3 ]}

يمكن استخدام خوارزمية باخ كجزء من بعض طرق توليد المفاتيح في علم التشفير. ^{[ 4 ]}

تنتج خوارزمية باخ رقمًا${\displaystyle x}$بشكل عشوائي منتظم في النطاق${\displaystyle N/2<x\leq N}$(لإدخال معين)${\displaystyle N}$)، بالإضافة إلى تحليله إلى عوامله الأولية. ويتم ذلك عن طريق اختيار عدد أولي.${\displaystyle p}$وأس${\displaystyle a}$بحيث${\displaystyle p^{a}\leq N}$وفقًا لتوزيع معين. ثم تقوم الخوارزمية بتوليد رقم بشكل متكرر${\displaystyle y}$في النطاق${\displaystyle M/2<y\leq M}$، أين${\displaystyle M=N/p^{a}}$، بالإضافة إلى تحليل${\displaystyle y}$ثم يقوم بضبط${\displaystyle x=p^{a}y}$ويلحق${\displaystyle p^{a}}$إلى تحليل${\displaystyle y}$لإنتاج تحليل العوامل لـ${\displaystyle x}$وهذا يعطي${\displaystyle x}$مع توزيع لوغاريتمي على النطاق المطلوب؛ ثم تُستخدم معاينة الرفض للحصول على توزيع منتظم. ^{[ 1 ] [ 5 ]}

• باخ، إريك . الأساليب التحليلية في تحليل وتصميم الخوارزميات النظرية للأعداد ، مطبعة معهد ماساتشوستس للتكنولوجيا، 1984. الفصل 2، "توليد التحليلات العشوائية"، جزء منه متاح عبر الإنترنت هنا .