ریاضی کاربردی

کاربردی از ریاضیات در طراحی جاده ها و خطوط راه آهن

amath — Sat, 01 Sep 2007 21:12:18 GMT

قطار های مدل اغلب داری دو نوع ریل هستند : ریل های خمیده ، که در بیشتر اوقات کمان هایی از یک دایره به شعاع R هستند ، و ریل های راست. این ریل ها عمدتا طوری طراحی شده اند که به شکل زیر سرهم بندی می شود
مسیر های AB و CDمستقیم و مسیرهای BC و DAنیم دایره هستند.اما آیا این مسیر ها به اندازه کافی خمیده هستند ؟!
مسیر های طراحی شده بوسیله اصطکاک پایدار می ماند و اغلب ممکن است در هنگام عبور قطار از روی آنها جدا شوند.اگر چه ممکن است در وسط مسیر های خمیده یا مسیر های مستقیم اتصالات دیگری نیز وجود داشته باشد ولی در بیشتر مواقع مسیر کلی از نقاط A,B,C,D جدا می شود .
برای بررسی این اتفاق تصور کنید قطاری با سرعت ثابت در حال حرکت است بنابراین شتاب مماس آن یعنی صفر است و در نتیجه شتاب کلی آن تنها شتاب مرکز گرای آن است( شعاع خمیدگی مسیر است که برای شکل بالا بر روی مسیر خمیده مقداری برابر R دارد).بنابراین اندازه شتاب بر روی مسیر مستقیم صفر است و در مسیر نیم دایره است.به این دلیل مقدار شتاب در نقاط A,B,C,D نا پیوسته است (همانطور که در نمودار مشخص است). همین نا پیوستگی سبب می شود تا نیروی عکس العملی که از جانب قطار به ریل وارد می شود نیز در این نقاط نا پیوسته باشد . به همین دلیل نوعی شوک یا ضربه به هنگام وارد شدن و یا ترک پیچ وجود دارد ( البته حتما اثر این ضربه را در پیچ های غیر اصولی هنگام عبور خودرو و یا برعکس نیروی نرم و یکنواختی را در هنگام سفر در داخل مترو حس کرده اید) برای جلوگیری از بوجود آمدن چنین نقاط فشاری که موجب خروج قطار از ریل و یا خروج خودرو از جاده می شود مسیرها می بایست طوری طراحی شوند که خمیدگی جاده بطور یکنواخت تغییر کند.( البته این طراحی بطور نسبی و با توجه به شرایط محیطی و کمک گرفتن از شیب و اتصالات قوی تر نیز قابل بهبود است )

مثال : مسیری در امتداد منفی محور x ها و مسیر دیگری در امتداد شعاع y=x-1 ، x≥2 وجود دارد می خواهیم این دو مسیر را با استفاده از منحنی چند جمله ای f، به اندازه کافی خمیده و با حد اقل درجه ، طوری بهم وصل کنیم که هیچ گونه نا پیوستگی شتاب در نقاط اتصال احساس نشود.

راه حل : منحنی f باید طور انتخاب شود که مسیر ، شیب و خمیدگی آن در نقاط x=0 و x=2 پیوسته باشد.(همانطور که می دانیم خمیدگی عکس شعاع خم است )از آنجا که خمیدگی ( curvature ) منحنی f بصورت زیر است

و f چند جمله است ما تنها نیاز داریم f و 'f و ''f در نقاط اتصال به y=0 ، x≤0 و y=x-1 ، x≥2 مقادیر y و 'y و ''y را داشته باشد تا پیوستگی های مورد نظر اعمال شود یعنی هم مسیر پیوسته شود و هم از پیوستگی f' و f'' پیوستگی نتیجه شود و بنابراین و شتاب کل پیوسته می شود.

y(0)=f(0)=0 y'(0)=f'(0)=0 y''(0)=f''(0)=0
y(2)=f(2)=1 y'(2)=f'(2)=1 y''(2)=f''(2)=0

این شش شرط مستقل به ما چند جمله ای درجه 5 را پیشنهاد می کند :

f(x)=A+Bx+Cx²+Dx³+Ex⁴+Fx⁵
f'(x)=B+2Cx+3Dx²+4Ex³+5Fx⁴
f''(x)=2C+6Dx+12Ex²+20Fx³

سه شرط x=0 ، A=B=C=0 را نتیجه میدهد و برای سه شرط x=2 داریم :

8D+16E+32F=f(2)=1
12d+32E+80F=f'(2)=1
12D+48E+169F=f''(2)=0

که عدد های D=1/4 و E=-1/16 و F=0 را نتیجه می دهد و در نتیجه جواب :

که در نهایت مسیر کلی بصورت زیر است:

است. البته طراحان جاده ها و سازندگان ریل قطار ها اغلب از چند جمله ای ها برای اتصال استفاده نمی کند و در عوض از خم های clothoid و Lemniscat استفاده می کنند. چرایی استفاده از خم های بالا نیز به خواص جالب آنها بر می گردد که خود قبل تامل می باشد!

حل تمرین RSA

amath — Mon, 14 May 2007 10:19:18 GMT

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

خوب این هم حل مسئله قبلی که جوابش 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 = C^d % N=5347⁶⁶⁰⁵ % 16781=?

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

5347² % 16781=12366

5347⁴ % 16781=12366² % 16781=9484

5347⁸ % 16781=9484² % 16781=96

5347¹⁶ % 16781=96² % 16781=9216

5347³² % 16781=9216² % 16781=6015

5347⁶⁴ % 16781=6015² % 16781=389

5347¹²⁸ % 16781=389² % 16781=292

5347²⁵⁶ % 16781=292²% 16781=1359

5347⁵¹² % 16781=1359²% 16781=971

5347¹⁰²⁴ % 16781=971²% 16781=3105

5347²⁰⁴⁸ % 16781=3105² % 16781=8731

5347⁴⁰⁹⁶ % 16781=8731² % 16781=11059

=> 5347⁶⁶⁰⁵ % 16781=5347^{4096+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

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

djshahriar — Wed, 21 Mar 2007 11:25:18 GMT

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

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

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

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

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

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

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

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

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

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

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

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

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

الگوریتم RSA+عیدانه+تقویم ۸۶

amath — Fri, 16 Mar 2007 05:08:18 GMT

بر چهره گل نسيم نوروز خوش است

در صحن چمن روي دلفروز خوش است

از دي که گذشت هر چه گويي خوش نيست

خوش باش و ز دي مگو که امروز خوش است

فرا رسیدن سال نو و بهار طبیعت مبارک

انشاءالله سالی پر از خیر و برکت داشته باشید.

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

راستی آخرین پروژه مشترک من و آقا شهریار هم که در زمینه تحقیق در عملیات است از لینک زیر قابل دریافت است.

برنامه ریزی نیمه معین

و در انتها تقویم ۸۶ از دوست عزیزم آقا تایماز

تقویم سال ۱۳۸۶

{فرما در حاشیه نسخه رونوشتش از Diophantus' Arithmetica می نویسد }

برای تقسیم کردن یک عدد مکعب کامل به دو مکعب دیگر ، توان 4 و در حالت کلی هر توانی از هر عددی به دو توان هم جنس همانطور که ذکر شد حالت دومی نیز ممکن است ، و من مطمئنا یک اثبات تحسین بر انگیز برای آن پیدا کرده ام ، اما حاشیه کتاب برای نوشتن آن بسیار باریک است!!!!!!
پیر فرما

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

در طول این مثال فرض کنید شخص A می خواهد یک کلید عمومی برای خود بسازد و شخص B می خواهد با استفاده از این کلید عمومی برای A پیغامی بفرستد. فرض می کنیم که A و B بر سر روشی برای برمز در آوردن متن بصورت اعداد توافق کرده اند .بنابراین این گام ها باید پیموده شود :

1. ابتدا شخص A دو عدد اول انتخاب می کند . ما از اعداد p=23 و q=41 استفاده می کنیم .

2. شخص A دو عدد p و q را در هم ضرب میکند تا به N=p.q=(23)(41)=934 برسد . 934 کلید عمومی او است ، که آنرا به نفر B می دهد ( و همچنین به باقی افرادی در جهان که متمایل باشد )

3. شخص A همچنین عدد دیگری چون e را که نسبت به (M=(p-1)(q-1 اول باشد. یعنی بزرگترین مقسوم علیه مشترک آنها یک باشد یا p-1)(q-1),e)=1)). در این مورد خاص M=(p-1)(q-1)=(22)(40)=880 بنابراین e=7 مناسب است. e نیز قسمتی از کلید عمومی است و باید علاوه بر p.q ، e نیز به شخص B گفته شود.

4. حالا B اطلاعات کافی برای برمز در آوردن یک پیغام برای A را دارد . فرض کنید که در این مثال پیغامی مورد نظر عدد P=35 باشد .

5. شخص B مقدار(C=P^e(mod N)=35⁷(mod 943 را حساب می کند.

۶.535⁷=6433929687 و ۵64339296875(mod 943)=545

عدد 545در واقع پیغام رمزگذاری شده ای است که B به A می فرستد.

7. حالا A می خواهد 545 را رمزگشایی کند برای این کار او عددی را چون d نیاز دارد طوری که((ed=1(mod (p-1)(q-1 ، یا در این مثال(7d=1(mod 880جواب فرد A برای d عدد 503 خواهد بود ، زیرا داریم(7x503=3521=(4x(880)+1)(mod 800.

8. برای پیدا کردن متن رمزگشایی شده ، A مجبور است

(C^d (mod N)=545⁵⁰³ (mod 943

را حساب کند. در ابتدا به نظر می آید که این کار بسیار دشوار است اما توجه کنید

503 = 256+128+64+32+16+4+2+1

(که در واقع بسط دودویی عدد 503 است ) بنابر این خواهیم داشت

545⁵⁰³ = 545^{256+128+64+32+16+4+2+1}= 545²⁵⁶545¹²⁸ … 545¹

اما از آنجا که ما تنها علاقمند به پیدا کردن باقی مانده به پیمانه 943 هستیم ، می توانیم با محاسبه باقیمانده تمام عامل های ضربی در این پیمانه به مقصودمان برسیم و این کار را می توانیم با به توان 2 رساندن های متوالی عدد 545 انجام دهیم زیرا تمام توان های عامل های ضربی ، مضربی از 2 هستند.
به عنوان مثال برای اینکه به باقی مانده توان 4 ام عدد 545 برسیم داریم :

545²(mod 943) = 545 . 545 = 297025(mod 943) = 923

با به توان 2 رساندن مجدد داریم :

5454(mod 943) =(545²)²(mod 943) = 923 . 923 = 851929(mod 943) = 400

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

545¹(mod 943) = 545

545²(mod 943) = 923

545⁴(mod 943) = 400

545⁸(mod 943) = 633

545¹⁶(mod 943) = 857

545³²(mod 943) = 795

545⁶⁴(mod 943) = 215

545¹²⁸(mod 943) = 18

545²⁵⁶(mod 943) = 324

بنابراین عدد مورد نظر ما به صورت زیر بدست می آید :

545⁵⁰³(mod 943) = 324 . 18 . 215. 795. 857. 400. 923. 545(mod 943) = 35

بوسیله چنین عملیات کسالت آوری ( البته برای رایانه این محاسبات کاملا ساده و دارای سخت افزار راحتی است ) شخص A می تواند پیام B را رمزگشایی کند و به پیام اصلی یعنی P=35 برسد.

خوب اگر می خواهید با هم یک دور دیگه الگوریتم را مرور کنیم مثال ساده تر زیر را در نظر بگیرید :

ابتدا دو اول پیدا میکنیم :

p = 7
q = 19

تعیین مقدار N:

N=7x19=133

تعیین مقدار M:

M=(7-1)X(19-1)=108

انتخاب عدد کوچک e که نسبت به M اول باشد :

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

gcd : greatest common divisor

ب.م.م بزرگترین مقسوم علیه مشترک

انتخاب d طوریکه((ed=1 (mod (p-1)(q-1 یا de % M = 1

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

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

=> d = (1 +nM) / e

n = 0 => d = 1 / 5 (غ.ق.ق)
n = 1 => d = 109 / 5 (غ.ق.ق)
n = 2 => d = 217 / 5 (غ.ق.ق)
n = 3 => d = 325 / 5 = 65 (ق.ق)

رمزگذاری متن(عدد) p=6:

C = P^e % n
= 6⁵ % 133
= 7776 % 133
= 62

رمزگشایی متن رمز گذاری شده C=62:

P = C^d % n
= 62⁶⁵ % 133
= 62 * 62⁶⁴ % 133
= 62 * (62²)³² % 133
= 62 * 3844³² % 133
= 62 * (3844 % 133)³² % 133
= 62 * 120³² % 133

با ادامه کاهش توان به روش فوق که توان عبارت 6265 به 12032 کاهش داد و در واقع همان روش فوق یعنی تجزیه توان به جمعوند هایی که توان های 2 هستند ولی این بار در جهت عکس حرکت می کنیم یعنی از جمعوند آخری داریم :

= 62 * 36¹⁶ % 133
= 62 * 99⁸ % 133
= 62 * 92⁴ % 133
= 62 * 85² % 133
= 62 * 43 % 133
= 2666 % 133
= 6

که با متن اولیه p=6 مطابق است . بنابراین الگوریتم RSA درست کار می کند !

تمرین

حالا برای تمرین فرض کنید شما شخص ، A هستید و عدد های p=97 و q=173 را بعنوان عدد های اول و همچنین عدد e را 5 انتخاب کرده اید . بنابراین شما عدد N=16781 ( که همان حاصل p.q ) و e=5 را در اختیار فرد B می گذارید .
او متنی را(یک عدد) برای شما رمزگذاری می کند و برای شما عدد رمزگذاری شده 5347 را می فرستد . خوب حالا ببینید می توانید عدد اصلی را رمز گشایی کنید .

کلید واژه ها :الگوریتم رمزنگاری آر اس ای RSA Encryption Algorithm متن رمزگشایی شده (متن اصلی) Plaintext متن رمزگذاری شده Ciphertext

مروری بر رمزنگاری RSA

amath — Sat, 03 Mar 2007 04:16:18 GMT

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

در مطالب گذشته مفهوم رمزنگاری یکطرفه با همان سیستم کلید عمومی توضیح داده شد یک از معروفترین مدل های این روش، RSA است حروف RSA ابتدای نام سه پدید آورنده آن است:

Ronald Rivest, Adi Shamir ,Leonard Adleman.

از چپ به راست Leonard Adleman، Ronald Rivest، Adi Shamir کار های اولیه بر روی RSA به زمان دانشجوی آنها در MIT بر میگردد.

این روش بر پایه ایده ای به ظاهر ساده ولی زیرکانه است که در زیر مطرح می شود:

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

اگر عدد 14459160519 را به شما داده باشند و گفته باشند که این عدد با ضرب دو عدد صحیح به دست آمده است.آیا می توانید این دو عدد را تعیین کنید.این سوال نسبتا سخت است انصافاٌ رایانه این عدد را به سرعت تجزیه میکند (البته در این کار از لم های خاصی استفاده می شود ) ، اساسا این کار با امتحان کردن تعداد زیادی ترکیب احتمالی صورت می گیرد.رایانه برای اینکه هر عدد ، با هر اندازه ای ، را تجزیه کند مجبور است تقریبا در حدود «ریشه دوم آن عدد» ترکیب احتمالی را امتحان کند.مثلا در این مورد خاص تقریبا 38000 مورد بررسی می شود.

البته بررسی 38000 احتمال برای رایانه زیاد وقت گیر نیست ولی ، اگر عدد داده شده 10 رقمی نباشد و مثلا 400 رقمی باشد چه اتفاقی می افتد؟! ریشه دوم عددی 400 رقمی تقریبا 200 رقم دارد . عمر جهان تقریبا 10¹⁸ ثانیه است یعنی یک عدد 18 رقمی . حالا فرض کنید یک رایانه بتواند هر یک میلیون ترکیب احتمالی را در یک ثانیه چک کند ، در طول عمر جهان این رایانه قادر به چک کردن 10²⁴ مورد است اما برای عدد 400 رقمی 10²⁰0 احتمال وجود دارد . به این معنی رایانه برای تجزیه این عدد 10¹⁷⁸ برابر عمر جهان مشغول به محاسبه خواهد بود.
اما چک کردن اینکه یک عدد اول است یا نه به این اندازه دشوار نیست – به عبارت دیگر امتحان کنیم که ، آیا یک عدد می تواند قابل تجزیه شدن نباشد!

RSA هم به همین ترتیب عمل می کند . ابتدا دو عدد اول بسیار بزرگ ، p و q،پیدا می کنیم بطوری که هر کدام 100 یا 200 رقم داشته باشد. این اعداد محرمانه هستند ( در واقع همان کلید خصوصی ما هستند ) ، سپس این اعداد را در هم ضرب می کنیم تا عدد N=p.q ساخته شود .اساسا عدد N ی که به این ترتیب ساخته می شود کلید عمومی ما تلقی می شود. رسیدن به عدد N نسبتا کار ساده ای برای ما خواهد بود ، اما اگر شخصی بخواهد عدد N را تجزیه کند کار بسیار مشکل و تقریبا غیر ممکنی برایش خواهد بود.

اما چگونه می توان یک پیغام را بوسیله N برمز در آورد ؟ و چطور می توانیم مطلب برمز در آورده شده را با p و q رمزگشایی کرد؟

ادامه دارد...

کلید واژه ها :رمزنگاری آر اس ای RSA Encryption

تایید هویت

amath — Fri, 23 Feb 2007 05:14:18 GMT

"ریاضیات عبارت است از اثبات بدیهی ترین چیز به نا بدیهی ترین روش ممکن "
جورج پوليا

در پست قبلی به ارائه توضیحاتی پیرامون مفهوم کلید عمومی پرداختیم در این پست به توضیح مسئله تایید هویت که در حقیقت مکملی برای تامین کامل امنیت پیغام ارسالی در روش کلید عمومی است می پردازیم.

2.1. تایید هویت

در طرح کلید عمومی مشکلی وجود داشت ، از آنجا که کلید عمومی واقعاً در دسترس عموم قرار می گیرد ، هر کسی می تواند یک پیام جعلی را برای شما بفرستد . بنابراین دشمنان می توانند وانمود کنند که دوست شما هستند و پیامی کاملا مشابه با پیام دوستان شما برایتان بفرستند زیرا هم دوستان و هم دشمنان شما به کلید عمومی دسترسی دارند . اطلاعات نادرست دشمن می تواند شما را کاملا گمراه کند .بنابراین چگونه می توان مطمئن شد که متنی که ادعا دارد که از طرف دوست شما رسیده واقعاً از طرف دوست شما رسیده باشد .
حال برای انجام این کار روشی را مطرح میکنیم :
فرض کنید شما و دوستتان همانطور که قبلا اشاره داشتیم کلید های عمومی و خصوصی Eb،Ea و Db ، Da را دراختیار داشته باشید . حال فرض کنید شما می خواهید پیامی را به دوستتان بفرستید به طوری که دوستتان از هویت واقعی شما در پیام اطمینان پیدا کند.
ابتدا فرض میکنید اسم خودتان یک متن رمزگذاری شده است ، سپس آن با استفاده از Da رمزگشایی میکنید . شما تنها کسی هستید که می توانید این کارا انجام دهید زیرا تنها فردی که Da را میداند شما هستید . سپس این متن رمز گذاری شده (که همان امضای دیجیتال نامه است ) را در کنار متن اصلی که می خواهید آنرا برای دوستتان ارسال کنید ، قرار میدهید ، و پس از انجام این کار تمامی متن بدست آمده را با استفاده از Eb رمزگذاری می کنیم یعنی کلید عمومی ای که کلید خصوصی آن تنها در دست دوست شماست.
وقتی دوست شما پیغام را دریافت میکند ، ابتدا آنرا با استفاده از Db رمزگشایی میکند و بنابراین او متنی خواهد داشت که دارای قسمتی الحاقی است که این قسمت دارای مفهوم خاصی نیست . این کاراکتر های نا منظم همان اسم شما است که با کلید عمومی خودتان رمزگذاری کرده بودید بنابراین او براحتی میتواند این کاراکتر های نامنظم را با استفاده از Ea رمزگذاری کند و با این کار به اسم شما برسد و از هویت واقعی شما اطمینان پیدا کند.

این کار به این دلیل قابلیت اجرایی دارد که :
تنها کسی که میداند چگونه متنی تولید کند که در هنگام رمزگذاری به اسم شما تبدیل شود ، خود شما هستید ، به همین خاطر دوست شما می تواند اطمینان پیدا کند که این پیغام از جانب شماست.

شما هر متنی را می توانید برای تایید هویت رمزگذاری کنید که این متن رمز گشایی شده با کلید خصوصی ( یا به عبارتی رمزگذاری شده با کلید خصوصی )در واقع همان امضای دیجیتال شماست و تقریبا باید در هر پیام این متن عوض شود که کار بسیار ساده ای است. متن پیغام شما به این صورت خواهد بود :

«هنگام طلوع صبح حمله می کنیم !!!.رمز گشایی شده رشته کاراکتر "ABCDEFG" رشته کاراکتر "JDLEODK" است.»

برای مطمئن بودن از امنیت نامه ها در هر بار " ABCDEFG " و متن رمزگشایی شده مشتق از آن " JDLEODK " در هر پیغام عوض می شود.

اما در این سیستم خطری برای صحت اطلاعات رسیده وجود دارد . بیایید فرض کنیم شخصی در میانه راه از طریقی این اطلاعات برمز در آورده شده را سرقت کرده و قطعه امضا شده را بیابد و نامه ای ترتیب دهد که هم شامل امضا و هم شامل اطلاعات تحریف شده باشد در این حالت چه باید کرد؟

برای جلوگیری از این اتفاق سعی می شود امضای ما به نوعی به کل نامه برگردد . در عمل کل نامه امضا نمی شود بلکه از تابع هش (hash) استفاده می شود که بطور خلاصه به این معنی است که رشته بلندی از اطلاعات را توسط تابعی با رشته کوچکی جایگزین کنیم ( البته تابعی با شرایطی خاص ) سپس امضا روی این تکه انجام شود . بنابراین حتی اگر شخص نفوذ کننده امضای نامه نیز پیدا کند نمی تواند متن دلخواه خود را جایگزین متن اصلی کند و عملا بنابر ویژگی های ساختاری الگوریتم هش پیدا کردن متنی که داراری خروجی هش یکسان باشند غیر ممکن است. به این ترتیب نامه ای با امضای دیجیتالی در اختیار داریم که همچون اثر انگشت متعلق به خود همان نامه است.
البته توضیح و ارائه نمونه هایی از الگوریتم های هش خود نیازمند به مقاله ای جدا گانه است که انشاء ا.. در یکی از پست های بعدی به آن خواهیم پرداخت.

در پست بعدی یکی از الگوریتم های متداول رمزنگاری را ارائه می دهیم که بر پایه کلید عمومی استوار است.

کلید واژه ها : تایید هویت امضای دیجیتال تابع هش Certification Digital Signatures Hash Function ّ

مفهوم کلید عمومی

amath — Thu, 15 Feb 2007 08:33:18 GMT

"در ابتدا امری بدیهی به نظر می رسد اما بیشتر که فکر می کنی نتیجه گیری های این اصل ناشناخته تر می شود و در انتها از تلاش برای فهمیدن اینکه منظور آن چیست دست می کشی"

برتراند راسل

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

1.مفهوم کلید عمومی یا Public Key:

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

1.1.به رمز در آوردن یک طرفه(سیستم کلید عمومی):

حال این شرایط را در نظر بگیرید ، فرض کنید شما روش مخصوصی برای رمز نگاری در اختیار دارید که تقریبا یک طرفه است به این معنی که رمزگذاری اطلاعات ارسالی خیلی آسان ، ولی رمزگشایی آن خیلی سخت باشد. بنابر این هر کسی در هر کجای جهان ، می تواند پیغام خود را برای شما رمزگذاری کند اما تنها یک نفر قادر است تا این اطلاعات را رمزگشایی کند. چنین روشی هم اکنون موجود است و با نام های "برمز در آوردن یک طرفه " یا " برمز در آوردن دریچه ای " نامیده می شود.
روش کار به این صورت است که برای هر اطلاعات محرمانه ای ، یک کلید رمزگذاری و کلید دیگری برای رمز گشایی وجود دارد . اگر کلید رمزگشایی را بدانید ، درست کردن کلید رمزگذاری برایتان ساده است ولی عکس این عمل تقربیا غیر ممکن است – یعنی رسیدن کلید رمزگشایی از طریق کلید رمزگذاری کاملا مشکل است.
حال برای ارتباط با دوستتان در تهران هر کدام از شما دریچه ای یک طرفه برای انتقال اطلاعات دارید. ابتدا شما یک کد رمزگشایی Da می سازید و سپس از آن کلید رمز گذاری Ea متناظرش را می سازید . دوست شما هم در تهران همین کار را می کند با این تفاوت که او کلید رمزگشایی Db و کلید رمزگذاری Eb مخصوص خودش را دارد. شما کلید رمزگذاری Ea (و نه کلید رمزگشایی Da ) را در اختیار دوستتان می گذارید و دوستتان هم Eb ( و نه Db ) خود را در اختیار شما قرار میدهد . بنابر این شما قادر خواهید بود پیغامتان را با استفاده از Eb رمزگذاری کنید و برای دوستان بفرستید در حالی که تنها کسی که قادر به رمزگشایی آن است تنها دوست شما در تهران است (چون فقط اوست که Db را در اختیار دارد) و بالعکس دوست شما در تهران می تواند همین کار را انجام دهد.
حال اگر شما بخواهید کلید خود را عوض کنید ، مسئله بزرگی پیش نمی آید و تنها کافی است جفت کلید جدید خود را بسازید و جایگزین جفت کلید قبلی تان بکنید.یعنی مجددا کلید رمزگذاری جدیدتان را بدون در نظر گرفتن امنیت مسیر و از هر طریقی برای دوستتان بفرستید.
اگر کلید رمزگذاری شما دزدیده شود کسی که کلید شما را دزدیده ، تنها می تواند پیغام ها را رمزگذاری کند ( که البته با روش های تشخیص هویت این قبیل پیغام ها از پیغام های اصلی شناسایی می شود) و او قادر نخواهد بود که پیغام های ارسال شده به شما را رمزگشایی کند.
در حقیقت می توان کلید های رمزگذاری که گاهی به آنها کلید عمومی هم گفته می شود عینا در مکانی شناخته شده برای عموم گذاشته شود و مطمئن بود که کلید های رمزگشایی شما (کلید خصوصی) سری باقی خواهد ماند . درست مانند این است که بخواهید به من یک پیغام خصوصی ارسال کنید ، بنابراین از کلید های عمومی من استفاده می کنید و من تنها کسی خواهم بود که می توانم آن را بخوانم.

کلید واژه ها : رمزنگاری کلید عمومی کلید خصوص Encryption Cryptography
Public Key private key Trap-Door Ciphers

کاربردی از هندسه فراکتال

amath — Fri, 02 Feb 2007 15:58:18 GMT

«این جمله که "هر چیزی قطعیت ندارد "، خودش فاقد قطعیت است.»

بلز پاسکال

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

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

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

نمونه ها :

در ادامه مطلب نمونه هایی از این فراکتال ها ارائه می شود

فراکتال توزیع که در موارد گوناگون توزیع و جمع آوری سیال بطور یکنواخت کاربرد دارد، اندازه این وسیله از چند سانتیمتر تا بالای 6 متر تغییر میکند و در فرآیند های چند فازی شامل گازها ، آب و حلال های ارگانیک ، اسید های غلیظ و سایر محیط های خورنده فلزات کاربرد دارد.

این وسیله بر پایه تکنولوژی چند فراکتالی ساخته شده و به طور کلی برای مقیاس بندی و توزیع دو سیال یا بیشتر به طور همزمان کاربرد دارد. این وسیله با انژری کم کار می کند و گرداب های غیر یکنواخت را حذف میکند و همچنین دارای واکنش آنی به تغییرات فرآیندی است.(اینرسی فرآیندی پایین)

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

فراکتال اژدها یا پارک ژوراسیک

amath — Sun, 24 Sep 2006 08:31:18 GMT

افلاطون گفت :«خدا هندسه دان است .» ژاکوبی این جمله را چنین تغییر داد : «خدا حساب دان است .» سپس کرونکر آمد و این سخن به یاد ماندنی را باب کرد: « خدا عدد های طبیعی را آفرید ، مابقی کار انسان است »فلیکس کلاین

اول یک تکه کاغذ 30x2cm تهیه کنید حالا این نوار کاغذی را به موازات عرض و هر بار از وسط 4 بار تا بزنید به طوری که تمام خط های تا به موازات عرض قرار بگیرد .حالا شروع کنید به باز کردن کاغذ از روی خط های تا اما دقت کنید زاویه های ایجاد شده روی هر یک از خط های تا 90 درجه باشد به عبارت دیگر دو لبه ی هر خط تا با هم زاویه 90 درجه بسازند یعنی یه چیزی شبیه به تصویر پایین:

حالا این شکل چیه ؟ این کجاش شبیه یک شکل فراکتالی زیباست ! صبر کنید "همیشه اشکال فراکتالی در مراحل اولیه کلید های کمی از ساختار ریاضیاتی زیبای خود ارائه می دهند" نوار کاغذی ما بعد از باز شدن از کنار مانند تصویر زیر است:

شکل(1)

ما نمی تونیم بیش از 8 تا به کاغذ بزنیم بعد هم تمام زوایا را بصورت 90 درجه در بیاوریم پس برای ادامه راه از همون موجود کودنی که در مقابل هوش سرشار شما قرار گرفته استفاده می کنیم یعنی اینکه قاعد کلی حرکت این خطوط را استخراج می کنیم و می دیم دست رایانه!

اگر خوب به ابتدای مسیر حرکتی (خطوط قرمز) که از بالا شروع میشود نگاه کنیم می بینمی که ابتدا متحرک ما به سمت راست پیچیده خوب ما این حرکت را با یک R نشان می دهیم سپس دوباره بسمت راست و بعد از ان به سمت چپ L و.... حالا خودتون به رشته حروف زیر دقت کنید ببینید می توانید قاعده اصلی را بدست بیاورید:

......R->RR->RRL->RRLR->RRLRRLL

خوب حالا اگر این 2 تا قاعده را اجرا کنید می توانید بقیه مسیر رو بدون نگاه کردن به باقی شکل بنویسید:

1.ابتدا با یک حرکت R شروع کنید.
2.متمّم رشته حرکات قبل از R ی که هم اکنون نوشته شده را از انتها به ابتدا وارد کنید، ( اگر متوجه نشدید صبر کنید) به عبارت دیگر به حرکت ماقبل R نوشته شده نگاه کنید اگر R بود شما L را به بعد از R اضافه کنید و اگر R بود شما L را به بعد از R دستور(1) اضافه کنید و همین کار را برای حرکت های قبلی هم تکرار کنید تا به اولین حرکت برسید.

خوب اگر دقت کنید برای اولین R قانون دوم اجرا نمی شود چون در سمت چپ آن حرفی نیست . حالا برای اینکه بهتر متوجه ماجرا بشیم به چند گام ابتدایی زیر دقت کنید و آن را با رشته حرکاتی که پیش از این نوشتیم مقایسه کنید .

R
RRL
RRLRRLL
RRLRRLLRRRLLRLL
RRLRRLLRRRLLRLLRRRLRRLLLRRLLRLL
.
.
.

من R های قانون اول را پر رنگ تر نوشتم ولی R هایی که از قانون دوم بدست آمده با حروف معمولی نوشته شده. رشته حروف چهارم دقیقا تمام شکل(1) را کامل میکند ولی رشته پنجم به شکل زیر است :

حالا فکر می کنید اگر این قاعده 20 بار و در مسیر های کوتاه اجرا شود چه شکلی بدست می آید، برای دیدن چهره واقعی این فراکتال زیبا از برنامه کوچکی (18k )که دوست عزیزم آقا تایماز برای اون نوشته استفاده کنید اینم لینک برنامه:

The Jurassic Park Fractal

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

اما در انتها می خواهیم ببینیم چطور میشه حرکت nام ( راست یا چپ بودن )را پیدا کنیم :

ابتدا عدد n را بصورت K2n بنویسید طوری که k یک عدد فرد باشد حالا اگر باقیمانده k بر 4 عدد 1 شد nامین حرکت R و اگر باقیمانده 3 بود nامین حرکت L است.

مثال: می خواهیم جهت حرکت 10 را حساب کنیم :

۵x2¹ à 5 mod 4 = 1

پس حرکت 10 ام به سمت راست R است.
یا مثلا حرکت 76376

76376 = 9547 x 8 =9547 x 2³

۹۵۴۷mod4 = 3

بنابراین حرکت 76376 به سمت چپ L است.

حالا اگر می خواهید ببینید که این فراکتال با چه تابع تکرار شونده ای تعریف میشه و دنباله حرکات در مبنای 2 یا 8 کدام دنباله ها از اعداد را میدهد ، نمودار رخداد (recurrence plot ) این فراکتال چگونه است ، تاریخچه و تصاویر دیگر آن به چه نحو است، به لینک های منبع مراجعه کنید.

منابع :

http://math.rice.edu/~lanius/frac/jurra.html

http://en.wikipedia.org/wiki/Dragon_curve

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

یک ترفند هندسی معروف یا قانون " از کجا آوردی "

amath — Tue, 12 Sep 2006 22:28:18 GMT

«در بسیاری از شاخه های علم ، هر نسل آنچه را نسل قبلی ساخته است ویران می سازد ، و چیزی را که کسی بنا کرده دیگری از میان بر می دارد. فقط در ریاضیات است که هر نسل طبقه جدیدی به ساختمان قدیم می افزاید.» هرمان هانکل

اول از همه به خاطر این چند روز غبتم عذر خواهی می کنم ولی این جور غیبت ها در ایام آغازی سال تحصیلی و همچنین در طول آن اجتناب ناپذیره. ضمنا از compphio عزیز هم به خاطر همه نظرات صمیمانش تشکر میکنم لا اقل می تونم بگم که همش رو خواندمو ... . از دوستانم می خوام که آپ شدن وبلاگشون رو به من خبر ندن! چون من هر چند روز یکبار از طرق کدهای آر.اس.اس وبلاگ همه دوستان رو چک میکنم .

بله ، درسته که به قول این دوست عزیز ما بعضی وقت ها وقتی تو مهندسی عدد پی را با عدد نپر (e)ساده می کنند پس دیگه یک واحد مساحت ارزش زیادی نداره! ولی توی دنیای ریاضیات که قراره عدالت کامل برقرار بشه قانون " از کجا آوردی " که بعد از یه عالمه مکافات هنوز در کشور ما اجرا نشده ، از ابتدا اجرا می شده و می شه.

فریاد از این بهت سبک زنهار از این خواب گران

حالا اگر علاقه مند شدی بزن روی ادامه مطلب