تبليغاتX
ریاضی کاربردی ریاضی کاربردی      ریاضیات کاربردی و علوم کامپیوتر

                 

 

 

صفحه نخست
پست الکترونيک
آرشيو وبلاگ

 

درباره وبلاگ

آيا کساني که مي دانند با کساني که نمي دانند يکسانند. قرآن کريم
ریاضی کابردی شاخه ای از ریاضیات نیست بلکه جهت حرکت در آن است.
نویسندگان :
شهریار میرزاده روزبه ابرازی
دانشجویان ریاضی کاربردی
دانشگاه خواجه نصیر الدین طوسی
E-Mail:R.Ebrazi@gmail.com

 

نویسندگان وبلاگ

روزبه ابرازی
شهریار میرزاده


 آرشيو موضوعي

  عمومی
تئوری بازی ها
تئوری اعداد
سیستم های خبره
بهینه سازی
ریاضیدانان
توپولوژی
رمزنگاری

 

نوشته هاي پيشين

شهریور 1386
اردیبهشت 1386
فروردین 1386
اسفند 1385
بهمن 1385
مهر 1385
شهریور 1385
مرداد 1385
تیر 1385
اردیبهشت 1385
فروردین 1385
اسفند 1384
بهمن 1384
دی 1384
آذر 1384
مهر 1384
شهریور 1384
مرداد 1384

 

جستجو و آمار

Google

در اين سايت

در كل اينترنت
 



 

 

13:50دوشنبه بیست و چهارم اردیبهشت 1386

حل تمرین RSA

روزبه ابرازی

بینهایت ! هیچ سوال دیگری تا به حال به این اندازه روح انسان را متحول نساخته .
دیوید هیلبرت

خوب  این هم  حل مسئله قبلی که جوابش 16657  بود:
 
فرض مسئله :


 
N=p.q=97x173=16781

M=(p-1)(q-1)=96x172=16512

(غ.ق.ق)e = 2 => gcd(e, 16512) = 2
(غ.ق.ق)e = 3 => gcd(e, 16512) = 3
(غ.ق.ق)e = 4 => gcd(e, 16512) = 4
e = 5 => gcd(e, 16512) = 1=> e=5

؟=C = Pe % n=5347                  &            p

حل مسئله :

برای حل مسئله مجبوریم d را پیدا کنیم اما کاملا دقت داشته باشید که تنها کسی می تواند d  را پیدا کند که از m و در نتیجه از q و p مطلع باشد :

ed=1(mod (p-1)(q-1))   =>   ed=1(mod  M)   =>    

= > de % M = 1   =>     de = 1 + nM

=>  d = (1 +nM) / e

 

n = 1 => d = 16513 / 5 (غ.ق.ق)
n = 2 => d = 33025/ 5 =6605 (ق.ق)     => d= 6605

 

خوب حالا برای رمزگشایی بصورت زیر عمل می کنیم :

P = Cd % N=53476605 % 16781=?

 

6605=4096+2048+256+128+64+8+4+1

 

 

53472 % 16781=12366

 

53474 % 16781=123662 % 16781=9484

 

53478 % 16781=94842 % 16781=96

 

534716 % 16781=962 % 16781=9216

 

534732 % 16781=92162 % 16781=6015

 

534764 % 16781=60152 % 16781=389

 

5347128 % 16781=3892 % 16781=292

 

5347256 % 16781=2922 % 16781=1359

 

5347512 % 16781=13592 % 16781=971

 

53471024 % 16781=9712 % 16781=3105


53472048 % 16781=31052  % 16781=8731

 

53474096 % 16781=87312  % 16781=11059

 

 

=>  53476605 % 16781=53474096+2048+256+128+64+8+4+1 % 16781

 

=11059 x 8731 x 1359 x 292 x 389 x 96 x 9484 x 5347  % 16781

 

=16657


14:56چهارشنبه یکم فروردین 1386

يك سوال جالب نظريه اعداد

شهریار میرزاده

سلام به عاشقان ریاضی

قبل از هر چيز فرا رسيدن عيد سعيد باستاني را به همه شما تبريك مي گويم.در سالي كه گذشت وبلاگ رياضي كاربردي با زحمات دوست عزيزم روزبه ابرازي كه صاحب اصلي وبلاگ هم است، بهتر و پر بار تر شده است. اميدوارم روزبه در راهي كه در آن قرار دارد روز به روز موفق تر گردد.

اما  اجازه بديد وارد اصل مطلب بشويم.زماني كه در دبيرستان مفيد مشغول درس خواندن در رشته رياضي فيزيك بودم، يكي از دوستانم در يكي از روزهاي سال سوم دبيرستان سوالي را از من پرسيد بدين صورت:"كدام عدد 4 رقمي است كه اگر در 4 ضرب گردد ،مقلوب آن عدد حاصل ميگردد"منظور از مقلوب يك عدد ، عددي است كه ارقام آن دقيقا عكس ارقام عدد مذكورمي باشد به عنوان مثال مقلوب عدد 3 رقمي 123 عدد 321 است

.آن زمان پس از حدود يك ساعت فكر كردن  و پس از آزمايش وخطا جواب مورد نظر را يافتم:"2178"

بله اگر عدد 2178 در عدد 4 ضرب گردد عدد 8712 كه مقلوب آن است،توليد ميشود.(به راحتي مي توانيد صحت اين مطلب را بررسي كنيد)

4 سال از آن روز گذشت تا اينكه ديروز ذهن من مجددا متوجه آن سوال شد، اين بار آنچه ذهن من را مشغول ميكرد پيدا كردن حالت كلي براي اعدادي مانند 2178 بودو يا بطور شفاف اعدادي كه مقلوب خود را عاد مي كنند ، آيا مي توان قانوني را در مورد چينش ارقام آن ها بيان كرد؟

مسلما در همان ابتدا اين قانون فوق الذكر در مورد اعدادي كه با مقلوب خود برابرند مشخص بود،مثلا ما به راحتي ميتوانيم اعدادي مانند 121و4224و25652و... را بسازيم كه با مقلوب خود برا برند.اسلوب ساخت اين اعداد كه داراي خاصيت جناس قلب مي باشند(palindrome numbers)براي همه ما و حتي براي آن هايي كه ميانه اي با رياضيات ندارند بديهي  و كاملا آسان به نظر مي رسد.

اگر اين اعداد زيبا را موقتا كنار بگذاريم و توجه خود را تنها معطوف اعدادي كنيم كه مقسوم عليهي نابديهي از مقلوب خود هستند،آنگاه شايد ديگر نتوانيم آن ها را به سهولت بيابيم.

منظور از مقسوم عليه نابديهي يك عدد مقسوم عليهي از آن است كه مخالف 1وخود آن عدداست .يكي از اعدادي كه دنبال آن هستيم همان 2178 است كه مقسوم عليهي نابديهي از مقلوب خود يعني 8712 ميباشد،ديگري 1089 است كه 9801 را عاد ميكند.(البته اين يكي از جستجوهاي روزبه جان است)

اما  از ديروز به بعد با فكر كردن و البته مشورت با دوست عزيزم آ قاي ابرازي تقريبا توانسته ايم حالت كلي را براي اين اعداد  بيابيم، اما تصور مي كنيم اگر شما دوستان هم درباره اين سوال جالب فكر كنيد به زيبايي نظريه اعداد بيش از پيش پی ببريد.

لذا شما بزرگواران اگر وقت داشتيد درباره سوال مطرح شده در ایام تعطيلات فكر كنيد(مطمئن باشيد شما هم از حل آن لذت خواهيد برد!!!)

در نهايت وبلاگ رياضي كاربردي تا هر زمان كه شما دوستان مايل باشيد به بحث ومشورت درباره جواب اين سوال مي پردازد. پس بار ديگر سوال را مشخصا مطرح ميكنيم:

سوال:آيا ميتوانيد ساختمان كلي تمام اعدادي كه مقسوم عليه نابديهي مقلوب خود مي باشند را بيان كنيد؟(مثلا  8712 | 2178)


3:40پنجشنبه دهم فروردین 1385

تجربیات وارینگ

روزبه ابرازی

 تجربیات وارینگ

وارینگ

 

بیان یک عدد بصورت حاصل جمع های مربعات و یا توان های دیگر از پیشینه تاریخی   طولانی ای برخوردار است.

شیوه های متفاوت نشان دادن یک عدد صحیح به صورت حاصل جمع اجزای کوچکتر مدت های مدیدی هم از ریاضیدانان حرفه ای و هم از ریاضیدانان آماتور دلربائی کرده .

بعنوان نمونه دنباله مربعات اعداد صحیح را در نظر بگیرید :

1 ,  4 , 9 , 16 , 25  , 36 , …     

به  قول  مرحوم مصاحب  و قس عليهذا .  همین طور که دنباله پیشرفت می کند شکاف مابین جملات دنباله بزرگتر میشود . این نکته بدیهی است که بیشتر اعداد   مکعب  اعداد صحیحی نیستند .

خیلی از اعداد صحیح قابل بیان بصورت مجموع دو   مربع کامل هستند مانند :

8=4+4     10= 9+1   13= 9+4

و به همین ترتیب اعداد دیگر .سایر اعداد را نمی توان   بصورت حاصل جمع فقط دو عدد صحیح بیان کرد بعنوان مثال   برای نشان دادن عدد 6 بصورت حاصل جمع  مربعات تنها مربع های کاملی که در اختیار داریم 4 و1 هستند و با این   دو عدد هم  هدف ما را تامین نمی کنند .در عوض عدد  6 یک حاصل جمع   3 مربعی خواهد داشت :

6=4+1+1

در واقع بیشتر اعداد صحیح مثبت قابل بیان   بصورت 3 مربع کاملند و   بعنوان مثال :

11=9+1+1                12= 4+4+4

از طرف دیگر 7 مثالی است که قابل بیان بصورت 3 مربع کامل هم نیست   و به 4 مربع کامل نیاز دارد :

7=4+1+1+1

حال این سوال برای ما پیش می آید که آیا برای   نشان دادن سایر اعداد ، به بیش از 4 مربع کامل نیاز پیدا می کنیم؟ در سال   1770 ،  لاگرانژ  Joseph-Louis Lagrange (1813-1736) ریاضیدان فرانسوی مسئله ای را ثابت کرد که  باعث  شک و تردید ریاضیدانان پیش از او را برانگیخته بود و یا آنها را با خود سرگرم کرده بود: هر عدد صحیحی  یا خودش مربع کامل است و یا به صورت حاصل جمع  2 ، 3 ، یا 4 مربع کامل قابل بیان است.

مشابه این سال ها که ریاضیدانان به این مسئله فکر می کردند و بعد از آن ، با حدس ادوارد وارینگ (1798-1736 Edward Waring )  ، یک  فیزیکدان تجربی و  همچنین پروفسور ریاضی  از دانشگاه کمبریج  مجددا خلق شد او حکمی مشابه را برای  مکعبات ، توان های 4 و   مانند آن قابل اثبات دانست . او این گزاره را بدون اثبات بیان کرده بود که برای بیان هر عدد صحیح بصورت حاصل جمع حد اکثر به 9   مکعب کامل یا 19 توان 4 نیاز است .

وارینگ  بعنوان ریاضیدانی درخشان شهرت داشت که این شهرت بیشتر به خاطر نظریات بنیادی وی در ریاضیات   بود. علاقه  او  کاربردهای تجربی  نبود بلکه   روشن ساختن طبیعت ریاضی آنها مورد علاقه وی بود.

متاسفانه عدم وجود ترکیب بندی مناسب  و نفوذ ناپذیری  نوشته های وارینگ  مانع از رسیدن به شناخت بسیاری از اثر های پیشگامانه  وی شد . نام او ، که  به طور وسیعی شناخته شده نیست، همراه مسئله هایی در باب مجموع توانهای   اعداد صحیح است.

وارینگ احتمالا باجمع آوری داده ها و مشاهده الگو ها به این حدس راجع به مکعبات و توانهای 4 رسیده .

مکعبات اعداد صحیح شامل دنباله :

1 , 8 , 27 , 64 , 125 , …

است.عدد7  بصورت مجموع 7   مکعب کامل (1+1+1+1+1+1+1=7)نوشته می شود ، 15 به   8 مکعب کامل (1+1+1+1+1+1+1+8=15) نیاز دارد ، 23 به 9 مکعب(1+1+1+1+1+1+1+8+8=23)، 31به فقط 5 مکعب (1+1+1+1+27=31)نیاز دارد.بر پایه  مشاهدات ، این معقولانه به نظر می رسد که فرض کنیم هیچ عدد صحیحی مجموع   بیش از 9 مربع کامل نیست.

عدد صحیح

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

حداقل مکعب کامل

  برای ساخت

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

2

 

عدد صحیح

17

18

19

20

21

22

23

24

25

26

2

28

29

30

31

32

حداقل مکعب کامل

  برای ساخت

3

4

5

6

7

8

9

2

3

4

1

2

3

4

5

2

توانهای 4 (1و16و81و256.....)هم همین رفتار را نشان می دهند:مثلا 15بصورت حاصل جمع 15 توان 4 قابل بیان است ،31 به 16 توان 4 نیاز دارد ،47به 17 ،63 به 18 و79 به 19 توان 4نیاز دارد .

حدس وارینگ ریاضیدان ها را به حجم زیادی از فعالیتهای ریاضیاتی تحریک کرد .در ابتدای قرن 19هم  یک ریاضیدان از برلین بنام کارل گوستاو  ژاکوب1851-1804 (Karl Gustav Jacob Jacobi ) این مسئله را به کامپیوتر واگذار کرد ، دستیاری که لیستی  12000 تایی از اعداد صحیحی ابتدایی  را مورد پردازش قرار داد و هر کدام را با کمترین شمار از اعداد مکعب کامل بیان کرد .

در این لیست به غیر از 23تنها عددی   که به 9 مکعب کامل برای نوشته شدن به صورت حاصل جمع نیاز دار د 239 است .  15 عدد دست کم به 8 مربع کامل احتیاج دارند

15,22,50,114,167,175,186,212,213,238,303,364,420,428,454

لیست اعدادی که به 7 مکعب کامل نیاز دارند خیلی بلند تر است ، اما شامل هیچ عددی بزرگتر از 8,042 نمی شود .

اگرچه چنین مجموعه ای از اطلاعات یک حدس را اثبات نمی کند و تنها در پیشنهاد اینکه چه چیز میتواند درست باشد  به کار میرود.حقیقتاً ، ریاضیدانان زمانی طولانی را برای ثابت کردن حدس ابتدایی وارینگ گذاشتند ، و  مجبور شدند برای انجام این کار به روش های بسیار پیچیده ای  روی بیاورند.

در سال 1909 یک   ریاضیدان بزرگ آلمانی به نام دیوید هیلبرت1943-1862(David Hilbert )با اثبات تعمیمی از این حدس گامی مهم در راستای اثبات آن برداشت او ثابت کرد که   برای مکعبات ، توانهای 4 ، و  همه توانهای بالاتر حداقل تعداد جملاتی وجود دارد که برای  بیان هر عدد صحیح کافی است . گرچه این اثبات هیچ گونه راهنمایی برای تعیین حداقل شمار جملات   از هر توان که برای بیان یک عدد لازم است ارائه نمی داد.

در سال 1912 آبری جی کمپنر( Aubrey J. Kempner )  تلاش های سال   1909  ویفریچ(A. Wieferich ) برای اثبات   اینکه هر عدد صحیح باحاصل جمع  9 مکعب کامل قابل بیان است را یک بار و برای  همیشه کامل کرد. در سال 1940 هم اس.اس فیلای  (S.S. Pillai ) نشان داد که هر عدد صحیح قابل بیان با  مجموع  73 جمله با توان 6 است.

ادعای اینکه37 جمله با توان  5 کافی است را چن جینگرون (Chen Jingrun ) در سال 1964ثابت کرد.طولی نکشید تا در سال 1986 ، Ramachandran Balasubramanian ، François Dress ، Jean-Marc Deshouillers  ثابت  کردند که به بیش از 19 توان   4 برای بیان هر عدد بصورت حاصل  جمع  نیازی نیست.

ریاضیدانان  با این سوال هم  که مرتبط  با سوال های قبلی است مواجه بودند که چه تعداد جمله برای بیان هر عدد صحیح بقدر کافی بزرگ(مثلا از یک مقدار مشخص بزرگتر) به صورت مجموع جمله های با توان kام ، لازم است.

بطور مثال باوجود اینکه هر عدد صحیح قابل بیان با حداقل  9 مکعب است، هر عدد صحیح بزرگتر از یک مقدار مشخص (شاید 8042) می توان با حاصل جمع حداکثر 7 مکعب کامل نشان داد.با مشاهده رفتار   اعداد  بزرگتر،ریاضیدانان شک کردند که : شاید هر عدد صحیح بقدر کافی بزرگ را بتوان با حاصل جمعی از مکعبات که تعداد جملات آن   از 4 بیشتر نباشد نشان داد.بزرگترین عدد شناخته شده که قابل بیان با 4 مکعب کامل نیست  7,373,170,279,850 است.

ریاضیدانان   به کار بر روی جنبه های مختلف مسئله وارینگ   و گوناگونی های آن  ادامه داده اند . آنها الگوهای دیگری که در ارتباط با توانها باشد را نیز جستجو کرده اند، .بر روی   حاصل جمع های مخلوطی از توان ها  (بطور مثال بیان یک عدد صحیح با توانهای 2 و 3)و  استفاده از توان های اعداد منفی و مثبت که باهم اجازه استفاده دارند نیز کار کرده اند.

با استفاده از کامپیوتر  وضعیتی مشابه این موارد توسط Kaplansky و William C. Jagy برای یک مربع و دو مکعب در مورد اعدادی که  در بازه –4,000,000 تا 2,000,000 قرار داشتند بررسی شد .محاسبات اضافی این حدس را تایید کرد که   برای این قاعده که هر عدد قابل بیان با یک مربع و دو مکعب است شمار متناهی  استثناء وجود دارد.

Kaplansky, Jagy  و دیگران بازه وسیعی از ترکیبات محتمل  را مورد کاوش قرار داند ولی باز هم زمینه حاصلخیزی   از تحقیق و تفکر برای مشخصا آماتور ها باقی مانده  .

این تحقیقات تجربیات موروثی ریاضیات را در کمک  برای یافتن الگو ها ، حدس های دیگر و  قضایای  جدید ادامه می دهد . آن چیزی که در مورد حساب اعداد صحیح برجسته است فاصله بین سادگی   آشکار  مواد خام  و پیچیدگی بی اندازه و ظرافت اثبات ها است.

" علم حساب پیشرفته تر ما را با انباری پایان ناپذیر از  حقایقی دلچسب آشنا می کند  از حقایقی که نتنها مجزا نیستند بلکه  در فاصله ای  نزدیکی نسبت به دیگری قرار دارند و در این بین با هر پیشرفت متوالی علم ، ما پیوسته  نقاط  تازه و کاملا غیر منتظره  اتصال را پیدا میکنیم "  این جمله را گوس  بزرگ1855-1777 (Carl Friedrich Gauss ) در سال 1849 بیان میکند.

او ادامه می دهد" قسمت اعظمی از قضایای حساب   از یک جذابیت اضافی از حالت و ویژگی ای نتیجه میشود که ما به آسانی گزاره های مهم را مقایسه می کنیم و نتیجه میگیرم که نشان سادگی ظاهر آنهاست اما اثبات چیزی که در ژرفای آن قرار دارد کشف نخواهد شد مگر  پس از انجام مقدار زیادی تلاش بی ثمر،  تنها زمانی رسیدن به ان میسر میشود که مقداری  مراحل ملالت بار و   ساختگی  پیموده شود، بازه زمانی که روشهای ساده تر برای اثبات مدتهای زیادی از دید ما پنهان میمانند"

بیوگرافی وارینگ در لینک زیر موجود است:

http://www-history.mcs.st-and.ac.uk/history/Mathematicians/Waring.html

اطلاعات اضافی راجع به مسئله وارینگ از اینجا قابل دسترسی است :

http://mathworld.wolfram.com/WaringsProblem.html

پیوند به متن اصلی:

http://www.maa.org/mathland/mathtrek_07_19_04.html


9:5یکشنبه یازدهم دی 1384

بخش پذیری بر«7»

روزبه ابرازی

بخش پذیری بر«7»

 

گفتن اینکه یک عدد صحیح داده شده بر 2 بخش پذیر است یا نه کار آسانی است . این کار فقط با بررسی زوج بودن آخرین رقم میسر است . روش های ساده ی دیگری هم برای تعیین بخش پذیری یک عدد بر 3و4و5و6و8و9 یا 10 وجود دارد . تنها استثنا عدد 7 است.