Кіріспе
Мерсен санының қарапайым сан екенін тексеру. Лукас-Лехмер сынағы тек Мерсен сандарына ғана қолданылады.
the Lucas–Lehmer test that applies only to Mersenne numbers
Математикада Лукас-Лехмер сынағы (LLT) – Мерсен сандарының қарапайымдығын анықтау тесті. Бұл тест алғаш рет 1878 жылы Эдуард Лукаспен әзірленген, ал 1930 жылы Деррик Генри Лемер оны дәлелдеген.
Бастапқы баламалы мәндер
4-тен басқа s0 бастапқы мәндері де болуы мүмкін, мысалы 10, 52 және тағы да басқалары. Егер Mp Мерсенді саны болса, осы баламалы бастапқы мәндермен есептелген Лукас-Лемер қалдығы да нөлге тең болады. Дегенмен, тізбектің мүшелері өзгеше болады және Mp Мерсенді сан болмаса, Лукас-Лемер қалдығының сандық мәні s0 = 4 болғанда есептелген мәннен өзгеше болады. (2 mod Mp)(3 mod Mp)−1 бастапқы мәнін пайдалануға да болады, ол әдетте 2/3 деп қысқартылады. Бұл бастапқы мән қолмен есептеу кезінде, соның ішінде Лукастың M127 санының Мерсенді екенін дәлелдеуінде жиі қолданылған. Тізбектің алғашқы мүшелері: 3, 7, 47, ...
Соңғыдан кейінгі мерзімнің белгісі
Егер sp−2 = 0 mod Mp болса, онда соңғыдан бұрынғы мүше sp−3 = ± 2(p+1)/2 mod Mp тең болады. Бұл соңғыдан бұрынғы мүшенің таңбасы Лемер символы ϵ(s0, p) деп аталады. 2000 жылы С. Я. Гебре Эгзиябхер 2/3 бастапқы мәні және p ≠ 5 үшін мынаны дәлелдеді: яғни, ϵ(2/3, p) = +1 егер p = 1 (mod 4) және p ≠ 5 болса. Екі p биттік санды көбейту үшін Фюрер алгоритмі сияқты тиімді көбейту алгоритміне белгілі бір уақыт керек. Қарама-қарсылық ретінде, жалпы бүтін сандар үшін ең тиімді кездейсоқ біріншілік сынағы, Миллер-Рабин біріншілік сынағы, n цифрлы сан үшін FFT көбейтуді пайдалана отырып, O(k n2 log n log log n) бит операцияларын қажет етеді, мұнда k – итерациялар саны және қателік деңгейімен байланысты. Тұрақты k үшін бұл Лукас-Лемер сынағымен бірдей күрделілік класына жатады. Бірақ практикада көптеген итерациялар жасау және басқа да айырмашылықтар Миллер-Рабиннің нашар жұмыс істеуіне алып келеді. Кез келген n цифрлы сан үшін ең тиімді детерминистік біріншілік сынағы, AKS біріншілік сынағы, ең жақсы белгілі нұсқасында Õ(n6) бит операцияларын қажет етеді және тіпті салыстырмалы түрде кішкентай мәндер үшін де өте баяу.
That is, ϵ(2/3, p) = +1 if p = 1 (mod 4) and p ≠ 5. An even more efficient multiplication algorithm, Fürer's algorithm, only needs time to multiply two p bit numbers. By comparison, the most efficient randomized primality test for general integers, the Miller–Rabin primality test, requires O(k n2 log n log log n) bit operations using FFT multiplication for an n digit number, where k is the number of iterations and is related to the error rate. For constant k, this is in the same complexity class as the Lucas Lehmer test. In practice however, the cost of doing many iterations and other differences leads to worse performance for Miller–Rabin. The most efficient deterministic primality test for any n digit number, the AKS primality test, requires Õ(n6) bit operations in its best known variant and is extremely slow even for relatively small values.
Қолданбалар
Лукас-Лехмер сынағы – Ұлы Интернет Мерсенн просты сандарын іздеу (GIMPS) жүйесі қолданатын маңызды просты сандарды анықтау әдістерінің бірі. Бұл іздеуге арқалай, бүгінгі күнге дейін белгілі ең ірі алғашқы сандардың көптегені табылды. Бұл сынақ құнды болып есептеледі, себебі ол үлкен көлемдегі өте ірі сандардың алғашқылығын салыстырмалы түрде аз уақытта нақты анықтауға мүмкіндік береді. Ал, Ферма санының кез келгені үшін дәл осы деңгейде жылдам Пепин сынағын есептеу мүмкіндігі шектеуге жеткенше, әлдеқайда аз сандар жиынында ғана қолдануға болады.