سلام دوستان
من هنوز در جستجوی راه حل ضرب یک عدد در خودش توسط همنهشتی هستم. البته اون الگوریتم دوست خوبمون نیز بسیار جالب بود ولی باید با همنهشتی نوشته بشه.
سوال اول:
بحث مربوط به مجموعه ها و زیر مجموعه ها در تئوری اعداد
یک مثالی در کتاب اومده. فرض کنید که می خواهیم عدد 2 را 5 بار در خودش ضرب کنیم. مجموعه حاصل که اون رو Z نامیده و پایین Z نیز عدد 6 گذاشته یعنی پیمانه 6.
1-حالا 2 به پیمانه 6 می شه 2
2-2*2 به پیمانه 6 می شه 4
3-2*2*2 به پیمانه 6 می شه 0
4-2*2*2*2 به پیمانه 6 می شه 2
5-2*2*2*2*2 به پیمانه 6 می شه 4
جواب های 2و4و0و2و4 را اینگونه حساب می کند که:
توان عدد 2 ضرب در خود عدد2 به پیمانه 6. مثلاً 8 برابر است با 2 به قوه 4، پس 2*4=8 و 8 به پیمانه 6 می شود عدد 2.
حالا می خواهیم زیر مجموعه های این مجموعه را به دست آوریم:
کد:
<0>={0}
<1>={0,1,2,3,4,5}
<2>={0,2,4}
<a>={a^k:k>=1}
ولی من نمی دونم این زیر مجموعه ها چگونه حساب می شوند و چه ربطه ای می تونن به ضرب یک عدد در خودش به اندازه n بار داشته باشند؟
سوال دوم:
در کتاب آمده است که الگوریتمی وجود دارد که همنهشتی را در زمان
محاسبه می کند. زمان لازم برای gcd(a,n) نیز logn است.
حالا فرض کنیم که می خواهیم 2^6 را حساب کنیم. در ابتدا
کد:
2≡2(mod 3) 2logn
2*2≡4(mod 3) 1 multiplication + 2logn
حالا این مقدار در حافظه باقی می ماند و دیگر حساب نمی شود.
کد:
2*2*2*2≡16(mod 3) 1 multiplication + 2logn
و حالا گام آخر:
کد:
2*2*2*2*2*2≡64(mod 3) 1 multiplication + 2logn
64≡1(mod 3) 2logn
پس در نهایت، ما 3 عمل ضرب و 8 عمل همنهشتی داشتیم.
آیا این استدلال درست است؟ آیا هزینه حساب همنهشتی ها نمایی نمی شود؟ چون دقیقاً به تعداد همنهشتی ها 2logn داریم.
چه ارتباطی بین سوال اول(مجموعه ها و زیر مجموعه ها) با سوال دوم وجود دارد؟
