Zenbaki lehenen test

Zenbaki lehenen testa algoritmo bat da, n zenbakia emanik lehena den edo ez jakiteko erabiltzen dena.

Marsenneren 39. zenbaki lehena. 2010. urtera arte ezagutzen zen zenbaki lehenik handiena zen.

Zenbaki lehenen testarekin n zenbakia konposatua dela dioen hipotesia egiaztatzea lortzen ez bada, lehena izango dela ondorioztatzen da, konfiantza-maila jakin batekin. Bereizi behar dira zenbaki lehenen testak emandako emaitzaren konfidantza-maila eta zenbaki lehenen froga (edo zenbaki lehenen egiazko testa) egitean lortutakoarena, azken hori froga izanik erantzuna erabateko segurtasun matematikoaz ematen delako.

Sarrera

Matematika Diskretuan badira ebazten oso zailak diren hainbat problema. Horietako bat zenbaki osoen faktorizazioaren problema da. Zenbaki lehenen testa eta zenbaki osoen faktorizazioa, biak ala biak aspalditik aztertuak izan diren problemak dira, baina ez dira nahastu behar; zenbaki oso baten faktorizazioaren problema oso konplexua da, eta oraindik ez da aurkitu hura denbora polinomikoan ebatziko duen prozedurarik.

Bestalde, badira matematikaren hainbat aplikazio faktorizazioaren probleman oinarritzen direnak. Kriptografia da arlo horietako bat, eta RSA zifratze-algoritmoa adibide argi bat. Halakoetan ausaz kalkulatutako zenbaki lehen oso handiak erabiltzeko beharra sortzen da; zenbaki lehen oso handi horiek kalkulatzeko, ondorengo algoritmoaren modukoak erabil daitezke:

Algoritmoa: Ausaz zenbaki lehen bat lortzea
/* Bertranden postulatuan oinarritua */ Sarrera: $n$ zenbaki arrunta Irteera: $p$ (ausazko zenbaki lehena) $p$ ← Funtzioa Zenbaki_bat_ausaz_sortu_tarte_batean [n, 2n] Bitartean $p$ ez da zenbaki lehena egin: $p\leftarrow p+1$ Baldin $(p=2n)$ orduan: $p\leftarrow n$ Itzuli $p$

Algoritmo horrek amaitzeko behar duen denbora ez da zehatza, baina denbora polinomikoan amaitzeko probabilitate handia dago. Horretarako, beharrezkoa da nahiko zenbaki lehen egotea eta horiek modu nahiko uniformean banaturik egotea. Euklidesen teorematik dakigu zenbaki lehenez osatutako multzoa infinitua dela. Gainera, Dirichletek zenbaki lehenetarako emandako teoremak (progresio aritmetikoetarako Dirichleten teorema izenez ere ezagutzen denak) zera dio: mkt(a,n) = 1 bada, orduan infinitu zenbaki lehen daudela a zenbakiarekin kongruenteak direnak modulu n. Hortaz, ondoriozta daiteke n edozein delarik, $\mathbb {N} _{n}^{*}$ barneko Eulerren φ funtzioarekin kongruente diren klaseetan zenbaki lehenak uniformeki banaturik daudela.

Zenbaki lehenak: Euklidesetik Lukasera

Zenbaki osoen faktorizazioaren problema eta zenbaki bat emanda lehena den edo ez erabakitzearena oso antzinakoak dira. Zenbaki lehenen azterketari buruzko lehen erregistro historikoak Euklidesen garaikoak dira (K.a. III. mendea), nahiz eta zenbaki lehenak Pitagorasen (K.a. VI. mendea) garaian ere ezagutzen zirela pentsarazten duten aztarnak egon.

Zenbaki lehenei buruzko lehen prozedura matematikoa Erastotenesen garaikoa da (K.a. II. mendea): Erastotenesen baheketa, oraindik ere lehen hezkuntzako eskoletan irakasten dena. Prozedura oso sinplea da eta emandako n zenbakia baino txikiagoak diren zenbaki lehenak lortzeko balio du. Hasteko, 1etik n-rako zenbaki osoekin zerrenda bat egiten da. Ondoren, zerrendako zenbakiak ezabatu egiten dira, zenbaki bikoitiak kendu, ondoren 3ren multiploak, ondoren 5arenak (5 delako 2 eta 3 zenbakien hurrengoa, bikoitiak eta 3ren multiploak kendu eta gero), etab. Gaur egun, algoritmo horren balioa historikoa da gehienbat, ongi funtzionatuagatik ere ez delako behar bezain eraginkorra.

Prozedura horrek ez du balio emandako zenbaki jakin bat lehena den edo ez erabakitzeko, zenbaki lehenen zerrenda osatzeko baizik (infinitua izan daitekeena). Hala ere, prozedura horretan oinarrituz diseina daiteke zenbaki lehenen testaren problema ebatziko duen beste prozedura bat; ibn al-Banna matematikari arabiarrak hainbat hobekuntza proposatu zituen mende batzuk beranduago. Horrela, 1etik n-rako zenbakien zerrenda osatu, baheketaren prozedura aplikatu eta $n$ zenbakia zerrendan ezabatu gabe mantendu bada, zenbakia lehena dela ondorioztatzen da. n zenbakia handia denean, prozeduraren kostu konputazionala oso altua da.

Matematikan ohikoa den moduan, zenbaki lehenen problema ere arabiarren eskutik sartu zen Europa modernoan. Harrez geroztik, zenbait mende pasa behar izan ziren Fibonacci (edo Pisako Leonardo) matematikari italiarrak gaiari buruzko lehen idatziak eta ebazpena argitaratu zituen arte: $n$ zenbakiak ez badu ${\sqrt {n}}$ baino txikiagoa den zatitzaile lehenik, $n$ lehena da. Algoritmo horren abantaila determinista izatea da; hau da, edozein zenbakitarako zehaztu dezake zenbaki hori lehena ote den. Hala ere, zenbaki handiak tratatzeko garaian motelegia da. Gaur egun metodoa saiakuntzazko zatiketa izenez ezagutzen da.

Gerora hainbat matematikarik egin du lan zenbaki lehenekin. Aipatzea merezi duten matematikari klasikoetako batzuk honakoak dira: Pietro Antonio Cataldi ($2^{n}-1$ lehena bada, orduan $n$ ere lehena da eta $2^{n-1}(2^{n}-1)$ perfektua da), Marin Mersenne (haren omenez izendatuak izan ziren Mersenne-ren zenbaki lehenak), Pierre de Fermat (gaur egun zenbaki lehenen testerako teknika modernoetan funtsezkoa den emaitza lortu zuen zenbaki lehenei buruz: Fermat-en teorema txikia), Leonhard Euler (Fermat-ek egindako lanen ildotik segitu zuen), Legendre eta Gauss (zenbaki lehenen faktorizazioaren problemarekin egin zuten lan) eta Edouard Lucas (Mersenne-ren zenbaki lehenetarako emaitza aipagarriak lortu zituen).

Testa eta froga

Aurreko atalean komentatu den moduan, zenbaki lehenen testa eta zenbaki osoen faktorizazioa erlazionatuta dauden problemak dira. Hala ere, bi arazo horiek oso ezberdinak dira. Zenbaki baten faktorizazioa egin dela argi uzteko nahikoa da zenbaki horren faktoreak erakustea. Baina, zenbaki lehenen testaren emaitza (hau da, zenbaki bat lehena badela edo ez dela) sinestaraztea ez da hain erraza. Fortuné Landry matematikari paristarrak XIX. mendean esan zuenez, zenbaki bat lehena dela onartzea fede kontua da, zenbakia lehena dela egiaztatzeko metodoak ezagutzen eta kalkuluak egiten ez dituen edonorentzat; ikuspuntu matematikoa.

Ingeniariaren ikuspuntutik gauzak ez dira zuriak edo beltzak. Horregatik, testaren eta frogaren (edo egiazko testaren) arteko ezberdintasuna ulertzea komeni da. Hona hemen bi kontzeptuen definizioak:

Definizioa: zenbaki lehenen testa egitea algoritmo bat aplikatzea da, sarrera moduan n zenbakia jaso eta zenbaki hori konposatua dela frogatzen duen teorema baten hipotesia egiaztatzen saiatzen dena.

Hau da, zenbaki lehenen testa n konposatua dela frogatzen saiatzen da eta lortzen ez duenean lehena dela ondorioztatzen du, konfiantza-maila jakin batekin; definizioz, zenbaki lehenen frogak (egiazko testak) baino konfiantza-maila txikiagoa du. Izan ere, zenbakia lehena denik ezin du frogatu erabateko segurtasun matematikoaz.

Definizioa: zenbaki lehenen froga (edo egiazko testa) algoritmo determinista da, sarrera moduan n zenbakia jaso eta zenbaki hori lehena dela frogatzen duen teorema baten hipotesia egiaztatzen duena; zenbaki lehenen froga egitea teoremaren egiaztapen konputazionala da.

Hortaz, bi ziurtasun-maila existitzen dira: zenbaki lehenen frogarena (ziurtasun matematikoa) eta zenbaki lehenen testarena (ziurtasun praktikoa).

Sasikodea

Zenbaki lehenen testerako algoritmo baten sasikodea da honakoa (oso handiak ez diren zenbakietarako egokia izan daiteke):

 funtzioa lehena_da(n)
     baldin n ≤ 1
        itzuli false
     bestela baldin n ≤ 3
        itzuli true
     bestela baldin n mod 2 = 0 edo n mod 3 = 0
        itzuli false
     i ← 5
     bitartean i * i ≤ n egin
        baldin n mod i = 0 edo n mod (i + 2) = 0
            itzuli false
        i ← i + 6
     itzuli true

Ikus, gainera

• Zenbaki osoen faktorizazioa
• Saiakuntzazko zatiketa
• Kriptografia

Kanpo estekak

• Datuak: Q829546