Кіріспе
Мерсенндік алғашқы сандарды іздеу үшін бағдарламалық құралдарды пайдаланатын еріктілер жобасы. Ұлы Интернет Мерсенндік алғашқы сандарды іздеу (GIMPS) – еріктілердің бірлескен жобасы, олар тегін қолжетімді бағдарламалық құралдарды пайдаланып Мерсенндік алғашқы сандарды іздейді. GIMPS 1996 жылы Джордж Уолтман құрды, ол Prime95 клиентін және оның Linux нұсқасы MPrime-ды жазды. Скотт Куровски 1997 жылы өзі құрған Entropia компаниясының ерікті есептеу бағдарламалық құралын көрсету үшін PrimeNet серверін жазды. GIMPS Mersenne Research, Inc. ретінде тіркелді, Куровски – атқарушы вице-президент және директорлар кеңесінің мүшесі. GIMPS зерттеу мақсатында интернеттегі еріктілердің үлкен ауқымды компьютерлік жобаларының бірі болып саналады. 2022 жылға дейін жоба барлығы он жеті Мерсенндік алғашқы санды тапты, олардың он бесеуі аталған уақыттағы ең үлкен белгілі алғашқы сан болып танылды. 2022 жылға дейін ең үлкен белгілі сан – 282,589,933 − 1 (немесе қысқаша M82,589,933) және ол 2018 жылдың 7 желтоқсанында Патрик Ларошпен табылды. 2020 жылдың 4 желтоқсанында жоба 100 миллионнан төменгі барлық көрсеткіштер кем дегенде бір рет тексерілгеннен кейін маңызды кезеңнен өтті. 2018 жылға дейін жоба негізінен Лукас-Лехмер алғашқылық тестіне сүйенді, себебі бұл алгоритм Мерсенндік алғашқы сандарды тексеруге арналған және екілік компьютерлік архитектураларда тиімді. Оны белгілі бір Мерсенндік санға қолданғанға дейін, кішкентай бөлгіштері бар көптеген Мерсенндік сандарды жылдам жою үшін сынаққа бөлу кезеңі қолданылды. Поллардтың p − 1 алгоритмі тегіс бөлгіштерді іздеу үшін де пайдаланылады. 2018 жылы GIMPS Ферманың алғашқылық тестін алғашқылықты тексерудің баламалы әдісі ретінде қабылдады, сонымен бірге Лукас-Лехмер тестісін Ферма тестісімен ықтимал алғашқы сандар ретінде анықталған Мерсенндік сандарды екі рет тексеру үшін сақтап қалды. (Лукас-Лехмер тестісі детерминистік, ал Ферма тестісі тек ықтималдық болғанымен, Ферма тестісі алғашқы сан емес Ферма псевдоалғашқысын табу ықтималдығы компьютерлік аппараттық қателерге байланысты Лукас-Лехмер тестісінің қателік деңгейінен әлдеқайда төмен.) 2020 жылдың қыркүйегінде GIMPS тексерілетін кешігу функцияларына негізделген алғашқылықты дәлелдеуді қолдауға кірісті. Дәлелдеме файлдары Ферманың алғашқылық тестісі жүргізіліп жатқанда жасалады. Бұл дәлелдемелер Роберт Гербиц жасаған қателерді тексеру алгоритмімен бірге сынақ нәтижесінің дұрыстығына толық сенімділік береді және екі рет тексеру қажеттігін жояды. Lucas Lehmer тестілеуі 2021 жылдың сәуір айында алғаш рет қолданылмай қалды. GIMPS белгілі композиттік Мерсенндік және Ферма сандарын факторлау бойынша да жобаларды жүзеге асырады.
The Great Internet Mersenne Prime Search (GIMPS) is a collaborative project of volunteers who use freely available software to search for Mersenne prime numbers. GIMPS was founded in 1996 by George Woltman, who also wrote the Prime95 client and its Linux port MPrime. Scott Kurowski wrote the back end PrimeNet server to demonstrate volunteer computing software by Entropia, a company he founded in 1997. GIMPS is registered as Mersenne Research, Inc. with Kurowski as Executive Vice President and board director. GIMPS is said to be one of the first large scale volunteer computing projects over the Internet for research purposes. as of 2022, the project has found a total of seventeen Mersenne primes, fifteen of which were the largest known prime number at their respective times of discovery. The largest known prime as of 2022 is 282,589,933 − 1 (or M82,589,933 for short) and was discovered on December 7, 2018, by Patrick Laroche. On December 4, 2020, the project passed a major milestone after all exponents below 100 million were checked at least once. From its inception until 2018, the project relied primarily on the Lucas–Lehmer primality test as it is an algorithm that is both specialized for testing Mersenne primes and particularly efficient on binary computer architectures. Before applying it to a given Mersenne number, there was a trial division phase, used to rapidly eliminate many Mersenne numbers with small factors. Pollard's p − 1 algorithm is also used to search for smooth factors. In 2018, GIMPS adopted a Fermat primality test as an alternative option for primality testing, while keeping the Lucas Lehmer test as a double check for Mersenne numbers detected as probable primes by the Fermat test. (While the Lucas Lehmer test is deterministic and the Fermat test is only probabilistic, the probability of the Fermat test finding a Fermat pseudoprime that is not prime is vastly lower than the error rate of the Lucas Lehmer test due to computer hardware errors.) In September 2020, GIMPS began to support primality proofs based on verifiable delay functions. The proof files are generated while the Fermat primality test is in progress. These proofs, together with an error checking algorithm devised by Robert Gerbicz, provide a complete confidence in the correctness of the test result and eliminate the need for double checks. First time Lucas Lehmer tests were deprecated in April 2021. GIMPS also has sub projects to factor known composite Mersenne and Fermat numbers.
Тарих
Жоба 1996 жылдың қаңтар айының басында i386 компьютерлерінде іске қосылған бағдарламамен басталды. Жобаның атын оның ерте ізденушілерінің бірі, сондай-ақ 29-шы Мерсенді санын бірге ашқан Люк Уэлш таңдады. Бірнеше айдың ішінде ондаған адам қосылды, ал алғашқы жылдың соңына қарай мыңнан астам адам қатысты. Жобаға қатысушы Жоел Арменго 1996 жылдың 13 қарашасында M1,398,269 санының жай сан екенін анықтады. Осыдан бері GIMPS әдетте 1-2 жыл сайын жаңа Мерсенді санын табады. Дегенмен, 2018 жылдан бері ешқандай жаңа Мерсенді сан табылған жоқ, бұл жоба басталғаннан бергі жаңа ашылудың ең ұзақ кезеңі болып табылады (2024 жылдың қаңтарына қарай 5 жылдан астам).
Мәртебе
2022 жылға қарай GIMPS-тің тұрақты орташа жиынтық өнімділігі шамамен 4,71 PetaFLOPS (немесе PFLOPS) құрайды. 2012 жылдың қарашасында GIMPS 95 TFLOPS деңгейінде болды, бұл теориялық тұрғыдан GIMPS виртуалды компьютеріне әлемдегі ең қуатты 500 компьютерлік жүйе тізімінде 330-шы орынды берді. Осыған дейін бұл орынды Hewlett Packard компаниясының "HP Cluster Platform 3000 BL460c G7" машинасы иеленген. 2021 жылдың шілдесіндегі TOP500 нәтижелері бойынша, GIMPS-тің қазіргі көрсеткіштері тізімге енбейді. Ал бұрын, 2010 жылдың басында бұл көрсеткіш шамамен 50 TFLOPS, 2008 жылдың ортасында 30 TFLOPS, 2006 жылдың ортасында 20 TFLOPS, ал 2004 жылдың басында 14 TFLOPS болған.
Бағдарламалық жасақтама лицензиясы
GIMPS бағдарламалық жасақтамасының бастапқы коды қоғамға ашық болғанымен, техникалық тұрғыдан ол тегін бағдарламалық жасақтама емес, себебі пайдаланушылар жобаның тарату шарттарын орындауға міндетті. Атап айтқанда, егер бағдарламалық жасақтама 100 000 000 ондық таңбадан кем емес алғашқы санды табу үшін қолданылса, пайдаланушы Electronic Frontier Foundation ұсынған 150 000 долларлық жүлденің тек 50 000 долларын ғана жеңіп алады. Ал кішкентайрақ алғашқы санды тапқан жағдайда, ол жүлдеге үміткер болмаса да, 3 000 доллар алады. Мерсенн сандарын тексеруге арналған Mlucas және Glucas (x86 емес жүйелер үшін) сияқты үшінші тарап бағдарламаларында мұндай шектеулер жоқ. GIMPS сондай-ақ "осы EULA-ны ескертусіз және шартты түрде кері күшпен өзгерту құқығын өзінде сақтайды". GIMPS 35-тен бастап барлық белгілі Мерсенн алғашқы сандарын тапқан.
as of 2023, 65,723,341 is the largest exponent below which all other prime exponents have been checked twice, so it is not verified whether any undiscovered Mersenne primes exist between the 48th (M57885161) and the 51st (M82589933) on this chart; the ranking is therefore provisional. Furthermore, 114,055,847 is the largest exponent below which all other prime exponents have been tested at least once, so all Mersenne numbers below the 51st (M82589933) have been tested. The number M82589933 has 24,862,048 decimal digits. To help visualize the size of this number, if it were to be saved to disk, the resulting text file would be nearly 25 megabytes long (most books in plain text format clock in under two megabytes). A standard word processor layout (50 lines per page, 75 digits per line) would require 6,629 pages to display it. If one were to print it out using standard printer paper, single sided, it would require approximately 14 reams (14 × 500 = 7000 sheets) of paper. Whenever a possible prime is reported to the server, it is verified first (by one or more independent tests on different machines) before being announced. The importance of this was illustrated in 2003, when a false positive was reported to the server as being a Mersenne prime but verification failed. The official "discovery date" of a prime is the date that a human first noticed the result for the prime, which may differ from the date that the result was first reported to the server. For example, M74207281 was reported to the server on September 17, 2015, but the report was overlooked until January 7, 2016.
| # | Табылған күні | Алғашқы сан Mp | Сандар саны | Процессор |
|---|---|---|---|---|
| 35 | 1996 жылдың 13 қарашасы | M1398269 | 420,921 | Pentium (90 МГц) |
| 36 | 1997 жылдың 24 тамызы | M2976221 | 895,932 | Pentium (100 МГц) |
| 37 | 1998 жылдың 27 қаңтары | M3021377 | 909,526 | Pentium (200 МГц) |
| 38 | 1999 жылдың 1 маусымы | M6972593 | 2,098,960 | Pentium (350 МГц) |
| 39 | 2001 жылдың 14 қарашасы | M13466917 | 4,053,946 | AMD T Bird (800 МГц) |
| 40 | 2003 жылдың 17 қарашасы | M20996011 | 6,320,430 | Pentium (2 ГГц) |
| 41 | 2004 жылдың 15 мамыры | M24036583 | 7,235,733 | Pentium 4 (2.4 ГГц) |
| 42 | 2005 жылдың 18 ақпаны | M25964951 | 7,816,230 | Pentium 4 (2.4 ГГц) |
| 43 | 2005 жылдың 15 желтоқсаны | M30402457 | 9,152,052 | Pentium 4 (2 ГГц, 3 ГГц-қа дейін айнымалы жиілікте) |
| 44 | 2006 жылдың 4 қыркүйегі | M32582657 | 9,808,358 | Pentium 4 (3 ГГц) |
| 45 | 2008 жылдың 6 қыркүйегі | M37156667 | 11,185,272 | Intel Core 2 Duo (2.83 ГГц) |
| 46 | 2009 жылдың 4 маусымы | M42643801 | 12,837,064 | Intel Core 2 Duo (3 ГГц) |
| 47 | 2008 жылдың 23 тамызы | M43112609 | 12,978,189 | Intel Core 2 Duo E6600 CPU (2.4 ГГц) |
| 48 | 2013 жылдың 25 қаңтары | M57885161 | 17,425,170 | Intel Core 2 Duo E8400 @ 3.00 ГГц |
| 49 | 2016 жылдың 7 қаңтары | M74207281 | 22,338,618 | Intel Core i7 4790 |
| 50 | 2017 жылдың 26 желтоқсаны | M77232917 | 23,249,425 | Intel Core i5 6600 |
| 51 | 2018 жылдың 7 желтоқсаны | M82589933 | 24,862,048 | Intel Core i5 4590T |
as of 2023, 65,723,341 is the largest exponent below which all other prime exponents have been checked twice, so it is not verified whether any undiscovered Mersenne primes exist between the 48th (M57885161) and the 51st (M82589933) on this chart; the ranking is therefore provisional. Furthermore, 114,055,847 is the largest exponent below which all other prime exponents have been tested at least once, so all Mersenne numbers below the 51st (M82589933) have been tested. The number M82589933 has 24,862,048 decimal digits. To help visualize the size of this number, if it were to be saved to disk, the resulting text file would be nearly 25 megabytes long (most books in plain text format clock in under two megabytes). A standard word processor layout (50 lines per page, 75 digits per line) would require 6,629 pages to display it. If one were to print it out using standard printer paper, single sided, it would require approximately 14 reams (14 × 500 = 7000 sheets) of paper. Whenever a possible prime is reported to the server, it is verified first (by one or more independent tests on different machines) before being announced. The importance of this was illustrated in 2003, when a false positive was reported to the server as being a Mersenne prime but verification failed. The official "discovery date" of a prime is the date that a human first noticed the result for the prime, which may differ from the date that the result was first reported to the server. For example, M74207281 was reported to the server on September 17, 2015, but the report was overlooked until January 7, 2016.
2023 жылғы деректер бойынша, 65,723,341 көрсеткішінен төменгі барлық алғашқы көрсеткіштер екі рет тексерілді, сондықтан осы кестедегі 48-ші (M57885161) және 51-ші (M82589933) алғашқы сандары арасында жаңа Мерсенн алғашқы саны бар-жоқ екені әлі расталмады, демек, олардың орналасуы уақытша. Сонымен қатар, 114,055,847 көрсеткішінен төменгі барлық алғашқы көрсеткіштер кем дегенде бір рет тексерілді, сондықтан 51-ші (M82589933) алғашқы санынан төменгі барлық Мерсенн сандары тексерілді. M82589933 санының ондық цифрларының саны 24,862,048-ге тең. Бұл санның үлкендігін түсіну үшін, оны дискіге сақтасаңыз, нәтижедегі мәтіндік файлдың көлемі шамамен 25 мегабайтты құрайды (жай мәтін форматындағы көптеген кітаптардың көлемі екі мегабайттан кем). Стандартты мәтін редакторында (бір бетте 50 жол, бір жолда 75 цифр) оны көрсету үшін 6629 бет қажет болады. Оны стандартты принтер қағазына, бір жақты басып шығарсаңыз, шамамен 14 қайырма (14 × 500 = 7000 парақ) қағаз қажет болады. Серверге мүмкін болатын алғашқы сан туралы хабарланған кезде, оны жариялау алдында тәуелсіз сынақтар арқылы әр түрлі машиналарда тексеріледі. Мұның маңыздылығы 2003 жылы, серверге Мерсенн алғашқы саны ретінде жалған оң нәтиже жіберілгенімен, тексеру сәтсіз аяқталғанда көрсетілді. Алғашқы санның ресми "табылу күні" - бұл адам алғаш рет оның нәтижесін байқаған күн, ол нәтиже серверге алғаш рет хабарланған күннен өзгеше болуы мүмкін. Мысалы, M74207281 2015 жылдың 17 қыркүйегінде серверге хабарланды, бірақ ол 2016 жылдың 7 қаңтарына дейін назардан тыс қалды.
as of 2023, 65,723,341 is the largest exponent below which all other prime exponents have been checked twice, so it is not verified whether any undiscovered Mersenne primes exist between the 48th (M57885161) and the 51st (M82589933) on this chart; the ranking is therefore provisional. Furthermore, 114,055,847 is the largest exponent below which all other prime exponents have been tested at least once, so all Mersenne numbers below the 51st (M82589933) have been tested. The number M82589933 has 24,862,048 decimal digits. To help visualize the size of this number, if it were to be saved to disk, the resulting text file would be nearly 25 megabytes long (most books in plain text format clock in under two megabytes). A standard word processor layout (50 lines per page, 75 digits per line) would require 6,629 pages to display it. If one were to print it out using standard printer paper, single sided, it would require approximately 14 reams (14 × 500 = 7000 sheets) of paper. Whenever a possible prime is reported to the server, it is verified first (by one or more independent tests on different machines) before being announced. The importance of this was illustrated in 2003, when a false positive was reported to the server as being a Mersenne prime but verification failed. The official "discovery date" of a prime is the date that a human first noticed the result for the prime, which may differ from the date that the result was first reported to the server. For example, M74207281 was reported to the server on September 17, 2015, but the report was overlooked until January 7, 2016.