Nov 09 2008
El test de Lucas-Lehmer
En mi post de ayer hablaba sobre los dos últimos gigantescos primos de Mersenne descubiertos y decÃa que se demostraba su primalidad mediante el llamado test de Lucas-Lehmer.
Vamos a intentar describirlo pues es sencillo.
Algoritmo
El test de Lucas-Lehmer permite determinar de manera eficiente si un número de Mersenne es o no primo. El algoritmo es como sigue:
- Sea p un número primo y Mp = 2p - 1 el número de Mersenne correspondiente.
- Sea x0 = 4
- Desde i= 1 hasta p-2: calcular xi = (xi-1 2 - 2) mod Mp
Entonces Mp es primo si y solo si el último xi calculado (es decir xp-2) es cero.
Código fuente
Incluimos un sencillo código fuente en Python (enlace al final) para comprobar si M_p es o no primo.
He aquà un ejemplo de ejecución:
./Lucas_Lehmer.py 9689 M_9689 = 47822027880546120295283929866000590974149717240223 65008513345109918378950942662970278927686112707894 58682472098152425631930658505267683408748083442943 32647974258932476236883310216332089548473548057999 43341309825989013743806187109581043148680813778321 53049671560156328262441404039814320762203627219040 85907905372034752561055640715792638678752409855733 56522656108542128577321057879052328865035355873615 67936365588992571157442015383209175242284304691881 14274006621355593035168537039768126863857503762277 87949580582081831261725701003498206512329872677233 48951095346937568303703837399969677158578890563911 55226134054957071845241582192082237664420590145933 30657009722153962376853423770486138578089775621301 16781129916640736174660669780818675796691467124607 37129042005884089231863877378876752928869537970669 80967406053530122853539036965490224784924649007954 89867850331465554647550450168618735486696437455261 41206407829496224520277889621386026659331476876963 22089504278791624651519312327831756553779377194524 67339581928148666857638401959072017941334958297031 93938843888104945460403420875365636283321520731816 14300721769371426238517540520845214665313301183551 96259184955893849902534878037671647707393063443684 00844682559374434516903159993491376646389689726141 99015304906547819056227171224947070739716300953775 74344130792050186353223446654564569577433188504497 82501486634673721303920998948521451909982328787724 86650513010816769902892518719250066947215706536216 24869624056925686555429622155221156042777866254593 69988010701861626014764742934598301836512733634627 32675883060701410359254829149774339297173680765610 95959991130918978823835013163567266143596921823997 71969338743954039966236755805282112071363963708580 56051160781770985452576988032333812939272752101944 62952749031383555198519709592888523641530178921867 51410145412030961912709343690395220982803176689420 61325572349643638403056487349290884223786292887472 23121903238528103409182430661894774072726552428489 33044748614549420767990417394471658382816714104358 31206790501914527326287370339974707206016882562827 40427017032260672798034347932642573009183981307771 93224553947639606065882143266031561414907405576980 55166263044447583756711516490181193442236859424151 84379538933576543212994405485534515585927342456182 51468137147206062877810212409237080214922983496351 79527270302962970156927686511635050080407282674252 36264469571076976886613730278931360967438271901738 55084846633734761208435679830650595580729351106375 44240807350667082987233779768874938983584523095638 99612061631863439196711208646438464947096323007272 92009125861472679997624967098527695035357339244162 02657720741248683592202828983311140833923302433917 79797699031142584361935093675448381119440881276338 80842044518049124543838841808009452756266680576289 54763384641305107753773247082495804533355717481965 02507081973046642282610569751056428979895118219288 59763522290538989487376146421399109115358645058189 92696826225754111 es primo.
Con esto el programa comprueba en pocos minutos que M9689 un número con
2917 dÃgitos es efectivamente primo (el número 21 en la lista de primos de Mersenne).
Código fuente: Test de Lucas-Lehmer
