Sekura primo

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo

En matematiko,sekura primo estas primo de formo 2p+1, kie ankaŭ p estas primo. Tiam, la nombro p estas primo de Sophie Germain.

La unuaj kelkaj sekuraj primoj estas

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, 1907.

Escepte de 5, ĉiu sekura primo q estas de formo q=4k-1 aŭ, ekvivalente, q ≡ 3 (mod 4), pro tio ke (q-1) / 2 devas esti nepara entjero. Plu, escepte de 5 kaj 7, ĉiu sekura primo q estas de formo q=12k-1 aŭ ekvivalente q ≡ 11 (mod 12), ĉar ĉiu primo de Sophie Germain p>3 estas de formo p=6k-1, kaj do q=2p+1=2·(6k-1)+1=12k-1.

Ne estas speciala primeca provo por sekuraj primoj. Tamen, kriterio de Pocklington povas esti uzata por pruvi primeco de 2p+1 se estas pruvita primeco de p.

Escepte de 5, ne estas primo de Fermat kiu estas sekura primo, pro tio ke primoj de Fermat estas de formo q=2n+1 kaj do (q-1)/2 estas para nombro se n>1.

Escepte de 7, ne estas primo de Mersenne kiu estas sekura primo. Ĉi tiu sekvas de tio ke ĉiu sekura primo escepte de 7 estas de formo 6k-1. Ĉiu primoj de Mersenne estas de formo 2m-1, kaj el 2m-1=6k-1 sekvas ke 2m estas dividebla per 6, kio neeblas.

Simile al tio ke ĉiu membro krom la lasta de ĉeno Cunningham de la unua speco estas primo de Sophie Germain, ĉiu membro krom la unua de tia ĉeno estas sekura primo. Sekuraj primoj kun la lasta cifero 7, tio estas, de formo 10n+7, estas la lastaj membroj en tiaj ĉenoj kiam ili okazas, ĉar 2·(10n+7)+1 = 20n+15 divideblas je 5.

Se sekura primo 2p+1 estas kongrua al 7 mod 8, tiam ĝi estas dividanto de la nombro de Mersenne kun ĝia orimo de Sophie Germain kiel eksponento.

Kiel en januaro de 2007, la plej granda sciata sekura primo estas 48047305725·2172404-1. Ĉi tiu primo, kune kun la respektiva plej granda sciata primo de Sophie Germain, estis trovitaj de David Underbakke en la 25-a de januaro de 2007 per programoj TwinGen kaj LLR [1].

Uzoj[redakti | redakti fonton]

Ĉi tiuj primoj estas nomata kiel sekuraj pro ilia interrilato al fortaj primoj. Primo q estas forta primo se ambaŭ q+1 kaj q-1 havas grandajn primajn faktorojn. Rultempo de iuj manieroj de faktorigo de nombro kun q kiel prima faktoro dependas parte de amplekso de la primaj faktoroj de q-1. Ĉi tio estas vera, ekzemple, por la +1 kaj −1 ρ algoritmoj de Pollard. Kvankam la plej kompetentaj sciataj faktorigaj manieroj ne dependas de amplekso de primaj faktoroj de q-1, ĉi tio estas tamen konsiderita grava en ĉifriko: ekzemple, normo ANSI X9.31 statas ke fortaj primoj estu uzataj por RSA moduloj.

Sekuraj primoj estas ankaŭ grava en ĉifriko pro ilia uzi en manieroj bazitaj je diskreta logaritmo, ekzemple ŝlosila interŝanĝo de Diffie-Hellman. Se 2p+1 estas sekura primo, la multiplika grupo de nombroj module 2p+1 havas subgrupo de granda prima ordo. Kutime ĉi tiu subgrupo kun prima ordo estas dezirinda, kaj tiel la sekuraj primoj estas uzataj por ke la modulo estu kiel eblas malgranda relative al p.

En la 18-a de junio de 2005, Antoine Joŭ kaj Reynald Lercier anoncis ke ili komputis diskretan logaritmon module de 130-cifera sekura primo [2].

Eksteraj ligiloj[redakti | redakti fonton]

  1. [1]
  2. [2]