Pirmreizinātājs
Vikipēdijas raksts
Pirmreizinātājs ir kāda naturāla skaitļa pirmdalītājs (pirmskaitlis ar ko dalās šis skaitlis). Piemēram, skaitļa 12 pirmreizinātāji ir 2 un 3. Skaitli sadalīt pirmreizinātājos nozīmē izteikt to kā vairāku pirmskaitļu reizinājumu, katram norādot arī kāpinātāju, ar kādu tas ietilpst dotajā skaitlī. Tā piemēram, 
, 
, utt. Ir zināms, ka katru naturālu skaitli, kas lielāks par 1, var sadalīt pirmreizinātājos, pie tam vienā vienīgā veidā (neņemot vērā pirmdalītāju kārtību). Skaitlim 1 nav neviens pirmdalītājs, jo tas dalās tikai ar 1, kas nav pirmskaitlis.
Izmantojot faktu, ka katrs pirmskaitlis nav mazāks par 2, var viegli pierādīt, ka jebkura naturāla skaitļa n pirmdalītāju skaits nepārsniedz [log2n].
Jāatzīmē, ka skaitļa n sadalīšana pirmreizinātājos ir grūts uzdevums, sevišķi ja n ir liels. Gandrīz visi zināmie algoritmi šo uzdevumu veic eksponenciālā laikā. Tāpēc izmantojot šo faktu, ir radīti grūti uzlaužami šifrēšanas algoritmi. Kamēr netiks izveidoti ātri algoritmi skaitļu sadalīšanai pirmreizinātājos, tikmēr šie algoritmi ir praktiski neuzlaužami. Populārākāis no šādiem algoritmiem ir RSA algoritms.
