الضرب السلاسل التي تؤدي ثابتة نمطية قوة 2

Question

هل هناك عملية خوارزمية أن يعطي "الضرب سلاسل"

لتوضيح الهدف هو إنتاج الضرب تغيير التعسفي و الدقيق طول
الضرب سلاسل من طول 1 هي تافهة.

و "الضرب سلسلة" يمكن تعريفها على أنها أرقام 2, {بداية} و {مضاعفة} ، وتستخدم في التعليمات البرمجية:

 Given a pointer to array of size [{count}]   // count is a parameter
 a = start;
 do 
 {
      a = a * multiplier;  // Really: a = (a * multiplier) MOD (power of 2
      *(pointer++) = a;   
 }
 while (a != {constant} )
 // Postcondition:  all {count} entries are filled.  

أود أن تجد الروتينية التي تستغرق ثلاث معلمات
1.قوة 2
2.وقف {مستمر}
3.{count} - عدد مرات حلقة تكرار

الروتين سيعود {start} و {مضاعفة}.

من الناحية المثالية, {مستمر} القيمة 0 يجب أن تكون سارية المفعول.

تافهة سبيل المثال:

power of 2 = 256  
stopping constant = 7
number of times for the loop = 1  
returns {7,1} 

بديهي سبيل المثال:

power of 2 = 256  
stopping constant = 1
number of times for the loop = 49
returns {25, 19}  

أقصى {count} من أجل إعطاء قوة 2 يمكن أن تكون صغيرة إلى حد ما.
على سبيل المثال, 2^4 (16) ويبدو أن تقتصر على عدد 4

Answer 1

هنا هو طريقة لحساب قيم بدء مضاعف من أجل القضية عندما المستمر غريب:

1. تجد هذا غريبا m (m = المضاعف) هذا أمر من م مودولو 2^D على الأقل العد ، وهذا يعني أن أصغر ن هذه م^ن = 1 (mod 2^د) على الأقل العد.أنا لا أعرف أي طريقة أخرى لإيجاد مثل م مما جعل تخمين عشوائي ، ولكن من تجريب قليلا يبدو أن نصف الأرقام الفردية بين 1 و 2^د النظام 2^(د-2) الذي هو القصوى.(حاولت D في معظم 12.)

2. حساب x بحيث x * م^count = 1 (mod 2^د) وتعيين تبدأ = x * ثابت (mod 2^د).

مثل x يمكن العثور على "تمديد خوارزميه اقليدس":نظرا a و b مع أي القاسم المشترك يعطيك x و y بحيث a * x + b * y = 1.هنا a=m^العد وزارة الدفاع 2^د و ب = 2^D.

تحرير: إذا كان ثابت يحدث أن تكون حتى يمكنك تقسيمه مع قوة من 2 ، 2^k, في الغريب ، ثم القيام أعلاه لإدخال {المستمر/2^k ، عدد ، 2^(د ك)} و أخيرا عودة {ابدأ*2^k,مضاعف}.

Answer 2

كنت طالبا غير بديهي الحلول التالية وحدات المعادلة:

s * m^N = C (mod 2^D)

حيث

• s هو الانطلاق المستمر
• م هو مضاعف
• N هو عدد التكرارات (قدمها المشكلة)
• ج هو النهائية ثابت (قدمها المشكلة)
• د الأس من قوة 2 (قدمها المشكلة)

إلقاء نظرة على نظرية أويلر في عدد من الناحية النظريه.

بالنسبة التعسفي الغريب م (الذي هو رئيس الوزراء مع 2^د) لديك

m^phi(2^D) = 1 (mod 2^D)

وهكذا

C * m^phi(2^D) = C (mod 2^D)

وأخيرا

C * m^(phi(2^D)-N) * m^N = C (mod 2^D)

تأخذ

s = C * m^(phi(2^D)-N)

والانتهاء من ذلك.على يولر فاي وظيفة من قوة 2 هو نصف أن قوة من 2 ، أي:

phi(2^D) = 2^(D-1)

على سبيل المثال.السماح

• N = 5
• ج = 3
• 2^D = 16
• فاي(16) = 8

اختيار تعسفي m = 7 (الغريب), وحساب

3 * 7^(8-5) = 1029
s = 1029 mod 16 = 5

الآن

s * m^N = 5 * 7^5 = 84035
84035 mod 16 = 3 == C

Answer 3

لماذا هذا لن تلبي المتطلبات ؟

start = constant;
multiplier = 1;

تحديث:أرى الآن أن عدد الحلقات هو واحد من معلمات الإدخال.يبدو أن هذه المشكلة هي حالة خاصة ، أو على الأقل ذات الصلة ، اللوغاريتم منفصلة المشكلة.