Duonprimo

En matematiko, duonprimo aŭ 2-preskaŭ primo, aŭ pq nombro estas natura nombra kiu estas produto de du (ne nepre diversaj) primoj. La unua kelkaj 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 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.

Kiel en 2007, la plej granda sciata duonprimo estas (2^32582657-1)², kiu havas pli ol 19 milionojn ciferojn. Ĝi estas kvadrato de la plej granda sciata primo. Kvadrato de ĉiu primo estas duonprimo, tiel okazas ke la plej granda sciata duonprimo estas kvadrato de la plej granda sciata primo. Estas konjekto ke oni povas trovi manieron por pruvi ĉu pli granda nombro estas duonprimo sen scio de la du faktoroj, sed la sciataj manieroj taŭgas nur por pli malgranda 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