25746

چگونگي تشخيص اعداد اول و آزمون هاي مربوطه

ارشد

رياضي محض

1400

31 شهريور 1400

دكتر مسعود هاديان دهكردي

دكتر سمانه مشهدي

رياضي

ﻣﻄﺎﻟﻌﻪي اﻋﺪاد اول اﻫﻤﯿﺖ زﯾﺎدي در رﯾﺎﺿﯿﺎت، ﺑﻪ وﯾﮋه ﻧﻈﺮﯾﻪ اﻋﺪاد دارد. ﺑﺎ ﭘﯿﺪاﯾﺶ ﺳﯿﺴﺘﻢﻫﺎي رﻣﺰ ﻧﺎﻣﺘﻘﺎرن مبتني برﻧﻈﺮﯾﻪ اﻋﺪاد، بررسي اول ﺑﻮدن اﻋﺪاد ﺑﺎ الگوريتمﻫﺎي ﺑﻬﯿﻨﻪ اﻫﻤﯿﺖ وﯾﮋهاي ﯾﺎﻓﺖ. در ﺑﺴﯿﺎري از ﻃﺮحﻫﺎي رﻣﺰﻧﮕﺎري ﻣﺪرن و الگوريتم هاي امنيتي ﻣﺎﻧﻨﺪ ﺳﯿﺴﺘﻢ رﻣﺰﻧﮕﺎري RSA ، ﮐﻪ ﺑﺮ ﭘﺎﯾﻪي سختي ﻣﺴﺄﻟﻪي ﺗﺠﺰﯾﻪ اﻋﺪاد اﺳﺖ، از اﻋﺪاد اول اﺳﺘﻔﺎده ميشود.اﮔﺮ ﭼﻪ الگوريتم هاي قطعي و احتمالي زﯾﺎدي ﺑﺮاي آزﻣﻮن اول ﺑﻮدن وﺟﻮد دارد، اﻣﺎ ﯾﺎﻓﺘﻦ الگوريتم قطعي در زﻣﺎن ﭼﻨﺪﺟﻤﻠﻪاي ﺑﺮاي اﯾﻦ آزﻣﻮن، در ﻣﺪت زﻣﺎن طولاني ﻣﺴﺄﻟﻪي ﺑﺎز ﺑﻮده اﺳﺖ. آﮔﺮوال، ﮐﺎﯾﺎل و ﺳﺎﮐﺴﻨﺎ ﭼﻨﯿﻦ الگوريتمي ﮐﻪ ﺑﻪ AKS ﺷﻬﺮت ﯾﺎﻓﺘﻪ اﺳﺖ، را اراﺋﻪ دادﻧﺪ. در اﯾﻦ ﭘﺎﯾﺎن ﻧﺎﻣﻪ ﺑﻪ اراﺋﻪي اﯾﻦ الگوريتم ﺑﺮاي بررسي اول ﺑﻮدن اﻋﺪاد مي پردازيم. اﯾﻦ الگوريتم اوﻟﯿﻦ الگوريتم ﺗﺸﺨﯿﺺ اول ﺑﻮدن اﻋﺪاد اﺳﺖ، ﮐﻪ ﺑﻪ ﻃﻮر ﻫﻢ زﻣﺎن ويژگي هاي مهمي ﭼﻮن ﻗﺎﺑﻠﯿﺖ اﺟﺮا ﺑﺮاي ﺗﻤﺎم اﻋﺪاد، بيچيدگي زماني ﭼﻨﺪﺟﻤﻠﻪاي، قطعي ﺑﻮدن، و ﻓﺎﻗﺪ ﺷﺮط ﻣﺤﺪود ﮐﻨﻨﺪه مي باشد

1400/09/28

recognizing of prime numbers and relevent tests

9/22/2022 12:00:00 AM

Study of prime numbers is very important in mathematics, especially in the numbers theory. Checking whether the numbers are prime or not with optimal algorithms gained a special importance with creation of asymmetric encryption systems based on the number theory. Prime Numbers are used in many modern cryptographic designs and security alghorithms such as the RSA,Cryptographic system that is based on the difficulty of parsing numbers, although, there are many definite and probable algorithms for primality testing but finding a definite algorithm in polynomial time for this test has been an open issue for long time. Agravwal,Kayal and Saxena introduced such algorithm known as RSA. In this thesis we are going to present this algorithm for determining a prime numbers. This algorithm is the first algorithm to determine prime numbers which simultaneously has important features such :Applicability for all numbers, The temporal complexity of polynomial,definiteness and Unconditional.

اﻋﺪاد اول، ﭼﻨﺪﺟﻤﻠﻪ اي روي ﻣﯿﺪان ﻫا ي ﻣﺘﻨﺎﻫﯽ، آزمون ﻓرما ، الگورﯾﺘﻢ AKS .

Prime Numbers, Polynomial Finite Fields,Fermat Test, AKS Algorithm