Enkel multiplikator

I talteorin är primtalsfaktorer ( primtalsdelare ) av ett positivt heltal primtal  som delar det numret med en faktor ( utan rest ) [1] . Att extrahera primtalsfaktorerna för ett positivt heltal innebär att lista dessa primtalsfaktorer tillsammans med deras multipliciteter. Processen att bestämma primtalsfaktorer kallas heltalsfaktorisering . Den grundläggande aritmetikens sats säger att vilket naturligt tal som helst kan representeras som en enda (upp till ordning) produkt av primtalsfaktorer [2] .

För att förkorta uttrycket representeras primtalsfaktorer ofta som primtals potenser (multiplikitet). Till exempel,

där faktorerna 2, 3 och 5 har multipliciteten 3, 2 respektive 1.

För en primfaktor p av n är multipliciteten av p  den största av exponenterna a för vilka padelar n jämnt.

För ett positivt heltal n är antalet primtalsfaktorer n och summan av primtalsfaktorerna n (utan multiplicitet) exempel på aritmetiska funktioner från n ( additiva aritmetiska funktioner [3] ).

Hel kvadrat

Kvadraten på ett tal har egenskapen att alla dess primtalsfaktorer har jämn multiplicitet. Till exempel har talet 144 (ruta 12) primtalsfaktorer

I en mer begriplig form:

Eftersom varje primtal är närvarande här ett jämnt antal gånger, kan det ursprungliga talet representeras som kvadraten på något tal. På samma sätt är kuben för ett tal  ett tal vars primtal är delbart med tre osv.

Samprimtal

Positiva heltal som inte har några gemensamma primtalsfaktorer kallas coprime . Två heltal a och b kan sägas vara coprime om deras största gemensamma divisor gcd( a , b ) = 1. Om två heltal inte har sina primtalsfaktorer så används Euklids algoritm för att avgöra om de är coprima ; Algoritmen körs i polynomtid på antalet siffror.

Heltalet 1 är coprime för vilket positivt heltal som helst, inklusive sig själv. Med andra ord har siffran 1 inga primtalsfaktorer, det är en tom produkt . Detta betyder att gcd(1, b ) = 1 för varje b ≥ 1.

Kryptografiska applikationer

Att bestämma primtalsfaktorerna för ett tal är ett exempel på ett problem som ofta används för att tillhandahålla kryptografisk säkerhet i krypteringssystem [4] . Detta problem är tänkt att ta superpolynomtid i antalet siffror. Det betyder att det är relativt enkelt att konstruera ett problem som skulle ta längre tid att lösa än universums kända ålder med den nuvarande utvecklingen av datorer och med hjälp av moderna algoritmer.

Omega-funktioner

Funktionen ω ( n ) (omega) är antalet olika primtalsfaktorer n , medan funktionen Ω( n ) (stora Omega) är antalet primtalsfaktorer n omräknat med multiplicitet [2] . Om en

sedan

Till exempel, 24 = 2 3 × 3 1. Så ω ​​(24) = 2 och Ω(24) = 3 + 1 = 4 .

Se även

Länkar

  1. ↑ Jensen, Gary R. Aritmetik för lärare: Med tillämpningar och ämnen från  geometri . — American Mathematical Society, 2004.
  2. ↑ 1 2 Riesel, Hans (1994), Primtal och datormetoder för faktorisering , Basel, Schweiz: Birkhäuser, ISBN 978-0-8176-3743-9 
  3. ↑ Melvyn B. Nathanson. Additiv talteori: de klassiska  baserna . - Springer-Verlag , 1996. - Vol. 234. - (Examinerade texter i matematik). — ISBN 0-387-94656-X .
  4. ↑ Menezes, Alfred; van Oorschot, Paul C.; Vanstone, Scott A. Handbook of Applied Cryptography  (obestämd) . - CRC Press , 1996. - ISBN 0-8493-8523-7 .