Turvallinen alkuluku

Turvallinen alkuluku on alkuluku, joka on muotoa 2p + 1, missä p on myös alkuluku. (Kääntäen, alkuluku p on Sophie Germainin alkuluku.) Ensimmäiset turvalliset alkuluvut ovat

5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, ...

Turvallinen alkuluku q (pois lukien luku 7) on myös muotoa 6k − 1 tai vastaavasti q ≡ 5 (mod 6) — kun p > 3. Samankaltaisesti turvallinen alkuluku q (pois lukien luku 5), voidaan ilmaista muodossa 4k − 1 tai vastaavasti muodossa q ≡ 3 (mod 4) — tämä pätee sillä (q − 1) / 2 täytyy olla pariton luonnollinen luku. Yhdistämällä molemmat muodot huomaamme, että turvallinen alkuluku q > 7 tulee olla myös muotoa 12k−1 tai vastaavasti q ≡ 11 (mod 12).

Sovellukset

Näitä alkulukuja kutsutaan "turvallisiksi" johtuen niiden kytköksistä vahvoihin alkulukuihin. Alkuluku on vahva alkuluku, jos sen arvo on suurempi kuin sitä lähinnä suuremman ja pienemmän alkuluvun keskiarvo tai toisin määriteltynä q on vahva alkuluku, jos molemmilla q + 1 ja q − 1 on suuri alkulukutekijä. Koska turvallinen alkuluku on muotoa q = 2p + 1, on luvulla q − 1 luonnollisesti suuri alkulukutekijä, nimittäin p, ja näin ollen turvallinen alkuluku q täyttää osan vahvan alkuluvun kriteereistä. Luvun, jossa q on alkulukutekijänä, tekijöihinjakoon kuluva aika erilaisilla menetelmillä laskettuna riippuu osittain luvun q − 1 alkulukutekijöiden koosta. Tämä pätee esimerkiksi käytettäessä Pollard rho-, Williamsin p + 1 - tai Pollardin p - 1 -menetelmää. Tehokkaimmat kokonaislukujen tekijöihinjakoon kehitetyt menetelmät eivät kuitenkaan riipu luvun q + 1 alkulukutekijöiden koosta. Tätä ominaisuutta hyödynnetään salakirjoitusmenetelmissä: esimerkiksi RSA-salausalgoritmi hyödyntää vahvoja alkulukuja.

Turvalliset alkuluvut ovat tärkeitä salakirjoitusmenetelmissä, koska niitä voidaan hyödyntää diskreetteihin logaritmeihin perustuvissa tekniikoissa kuten Diffie-Hellman-avaimenvaihtoprotokollassa.

Turvallisia alkulukuja, jotka noudattavat tiettyjä kongruensseja voidaan käyttää näennäissatunnaislukujen luomiseen Monte Carlon simulaatiossa.

Ominaisuuksia

Ei ole olemassa erityistä alkulukutestiä turvallisille alkuluvuille, kuten vaikkapa Fermat’n alkuluvulle ja Mersennen alkuluvulle on. Pocklingtonin kriteereitä voidaan kuitenkin käyttää todistamaan, että luku 2p+1 on alkuluku kunhan on ensin osoitettu p:n olevan alkuluku.

Pois lukien luku 5, ei ole olemassa Fermat’n alkulukua, joka olisi myös turvallinen alkuluku. Koska Fermatin alkuluvut ovat muotoa F = 2ⁿ + 1, seuraa siitä, että (F − 1)/2 on kahden potenssi.

Pois lukien luku 7, ei ole olemassa Mersennen alkulukua, joka olisi myös turvallinen alkuluku. Tämä seuraa yllä mainitusta turvallisen alkuluvun ominaisuudesta, jonka mukaan kaikki turvalliset alkuluvut, pois lukien luku 7, ovat muotoa 6k − 1. Mersennen alkuluvut ovat muotoa 2^m − 1, mutta 2^m − 1 = 6k − 1 johtaisi siihen, että 2^m on jaollinen luvulla 6, mikä on mahdotonta.

Ensimmäisen lajin Cunninghamin ketjun kaikki termit viimeistä lukuun ottamatta ovat Sophie Germainin alkulukuja, joten jokainen termi ketjussa ensimmäistä lukuun ottamatta on turvallinen alkuluku. Turvalliset alkuluvut, jotka päättyvät lukuun 7, eli ovat muotoa 10n + 7, ovat viimeisiä termejä niiden esiintyessä kyseisissä ketjuissa, sillä 2(10n + 7) + 1 = 20n + 15 on jaollinen luvulla 5 eli ei ole alkuluku.

Jos turvallinen alkuluku q on kongruentti luvulle 7 modulo 8, on se Mersennen luvun jakaja, ja sillä on q:ta vastaava Sophie Germainin alkuluku eksponenttina.

Suurin turvallinen alkuluku

Suurin löydetty turvallinen alkuluku on 18543637900515 × 2⁶⁶⁶⁶⁶⁸ − 1. Tämä turvallinen alkuluku ja sitä vastaava Sophie Germainin alkuluku löydettiin huhtikuussa 2012.