Duonprimo

En matematiko, duonprimo aŭ 2-preskaŭ primo, aŭ pq-nombro estas natura nombra, kiu estas produto de du (ne nepre diversaj) primoj. La unuaj duonprimoj estas 4, 6, 9, 10, 14, 15, 21, 22, 25, 26, ... . Kvadrato de ĉiu primo estas duonprimo, kaj ankaŭ produto de du malsamaj primoj estas duonprimo.

La valoro de eŭlera φ funkcio por duonprimo n estas:

φ(p²) = (p - 1)p     se n = p² por primo p,

φ(pq) = pq + 1 - (p + q)     se n = pq kie p kaj q estas diversaj primoj.

Laŭ la stato en 2007, la plej granda konata duonprimo estas (2^32582657-1)², kiu havas pli ol 19 milionojn da ciferoj. Ĝi estas kvadrato de la plej granda sciata primo.

Kvadrato de ĉiu primo estas duonprimo, tiel okazas, ke la plej granda konata duonprimo estas kvadrato de la plej granda konata primo. Ne estas klare, ĉu oni povas trovi manieron por pruvi, ke pli granda nombro estas duonprimo sen identigi ĝiajn du faktorojn, sed la konataj metodoj taŭgas nur por pli malgrandaj duonprimoj.

Aplikoj

Duonprimoj estas uzataj en ĉifriko, plej rimarkinde en publika ŝlosila ĉifriko, ekzemple RSA kaj ankaŭ en kvazaŭstokastaj generiloj, ekzemple Blum Blum Shub. Ĉi tiuj manieroj fidi la fakton ke trovo de du grandaj primaj kaj multipliko de ili kune estas kompute simpla, sed entjera faktorigo por trovo de la originalaj faktoroj estas malfacila.

En praktika ĉifriko, ne estas sufiĉe elekti iun ajn duonprimon. Bona nombro devas malfaciligi uzon de kelkaj algoritmoj de entjera faktorigo de speciala celo, kiuj povas rapide faktorigi nombrojn de certa formo. La faktoroj p kaj q de n devus esti tre granda, proksimume de la sama ordo de grandeco kiel la kvadrata radiko de n; ĉi tio faras provan dividon kaj ρ algoritmon de Pollard nepraktikajn. Samtempe ili devas ne esti tre proksimaj unu al la alia, alie alia simpla provo povas faktorigi la nombron. Ankaŭ, ĉiu el p-1, p+1, q-1, q+1 devas ne esti glata nombro, protektante kontraŭ uzo de ρ-1 algoritmo de Pollard aŭ ρ plus 1 algoritmo de Williams. Tamen, ĉi tiuj kontroloj, ne povas konsideri estontajn algoritmojn de speciala-celo.

Eksteraj ligiloj

• Eric W. Weisstein, Duonprimo en MathWorld.
• A001358 en OEIS - vico de duonprimoj
• La prima glosaro: duonprimo je La Primaj Paĝoj de Chris Caldwell