„Prímtényező” változatai közötti eltérés
[nem ellenőrzött változat] | [ellenőrzött változat] |
a Visszaállítottam a lap korábbi változatát 213.197.88.16 (vita) szerkesztéséről 213.197.90.174 szerkesztésére Címkék: Visszaállítás Visszaállítva |
Visszavontam az utolsó 4 változtatást (213.197.90.174, 213.197.88.16 és Pallerti), visszaállítva Dkuratowski szerkesztésére Címke: Kézi visszaállítás |
||
21. sor: | 21. sor: | ||
Egy ''n'' pozitív egész számra a prímtényezők ''száma'' és a prímtényezők ''összege'' (a multiplicitást nem tekintve) olyan [[számelméleti függvény]]ek, melyek additívak, de nem totálisan additívak.<ref>{{cite book | title=Additive Number Theory: the Classical Bases | volume=164 | series=Graduate Texts in Mathematics | author=Melvyn B. Nathanson | publisher=Springer-Verlag | year=1996 | isbn=0-387-94656-X }}</ref> |
Egy ''n'' pozitív egész számra a prímtényezők ''száma'' és a prímtényezők ''összege'' (a multiplicitást nem tekintve) olyan [[számelméleti függvény]]ek, melyek additívak, de nem totálisan additívak.<ref>{{cite book | title=Additive Number Theory: the Classical Bases | volume=164 | series=Graduate Texts in Mathematics | author=Melvyn B. Nathanson | publisher=Springer-Verlag | year=1996 | isbn=0-387-94656-X }}</ref> |
||
== |
==Négyzetszámok== |
||
A [[négyzetszám]]ok arról ismerhetőek meg, hogy minden prímtényezőjük páros multiplicitással rendelkezik. Például a 144 (a 12 négyzete) prímtényezői: |
A [[négyzetszám]]ok arról ismerhetőek meg, hogy minden prímtényezőjük páros multiplicitással rendelkezik. Például a 144 (a 12 négyzete) prímtényezői: |
||
:<math> 144 = 2 \times 2 \times 2 \times 2 \times 3 \times 3 = 2^4 \times 3^2.</math> |
:<math> 144 = 2 \times 2 \times 2 \times 2 \times 3 \times 3 = 2^4 \times 3^2.</math> |
||
29. sor: | 28. sor: | ||
Mivel minden prímtényező páros számúszor jelenik meg, az eredeti szám kifejezhető valamely kisebb szám négyzeteként. Hasonlóan, a [[köbszám]]ok prímtényezőinek multiplicitása a 3 többszöröse s.í.t. |
Mivel minden prímtényező páros számúszor jelenik meg, az eredeti szám kifejezhető valamely kisebb szám négyzeteként. Hasonlóan, a [[köbszám]]ok prímtényezőinek multiplicitása a 3 többszöröse s.í.t. |
||
== |
==Relatív prímek== |
||
A közös prímtényezővel nem rendelkező pozitív egész számokat [[relatív prímek]]nek (angolul: coprime) nevezik. Ha ''a'' és ''b'' pozitív egész számok relatív prímek, ha [[legnagyobb közös osztó]]juk lnko(''a'', ''b'') = 1. Az [[euklideszi algoritmus]]sal meghatározható, hogy két szám relatív prím-e prímtényezőik ismerete nélkül is; az algoritmus a számjegyek száma szerint polinomiális időben fut le. |
A közös prímtényezővel nem rendelkező pozitív egész számokat [[relatív prímek]]nek (angolul: coprime) nevezik. Ha ''a'' és ''b'' pozitív egész számok relatív prímek, ha [[legnagyobb közös osztó]]juk lnko(''a'', ''b'') = 1. Az [[euklideszi algoritmus]]sal meghatározható, hogy két szám relatív prím-e prímtényezőik ismerete nélkül is; az algoritmus a számjegyek száma szerint polinomiális időben fut le. |
||
Az 1 szám minden pozitív egésszel és önmagával is relatív prím. Ennek oka, hogy nincsenek prímtényezői, ő az [[üres szorzat]]. Tehát lnko(1, ''b'') = 1 bármely ''b'' ≥ 1. |
Az 1 szám minden pozitív egésszel és önmagával is relatív prím. Ennek oka, hogy nincsenek prímtényezői, ő az [[üres szorzat]]. Tehát lnko(1, ''b'') = 1 bármely ''b'' ≥ 1. |
||
== |
==Kriptográfiai alkalmazásai== |
||
A számok [[prímfelbontás]]a [[titkosítás]]i rendszerek [[kriptográfia]]i biztonságának fontos részét képezi;<ref>{{cite book |
A számok [[prímfelbontás]]a [[titkosítás]]i rendszerek [[kriptográfia]]i biztonságának fontos részét képezi;<ref>{{cite book |
||
| last = Menezes | first = Alfred |
| last = Menezes | first = Alfred |
||
46. sor: | 43. sor: | ||
== Omega-függvények == |
== Omega-függvények == |
||
⚫ | |||
⚫ | |||
Ha |
Ha |
||
:<math>n = \prod_{i=1}^{\omega(n)} p_i^{\alpha_i}</math>, |
:<math>n = \prod_{i=1}^{\omega(n)} p_i^{\alpha_i}</math>, |
||
58. sor: | 54. sor: | ||
*{{math|Ω(''n'')}} értéke {{math|''n''}} = 1, 2, 3…-ra 0, 1, 1, 2, 1, 2, 1, 3, 2, … {{OEIS|id=A001222}}. |
*{{math|Ω(''n'')}} értéke {{math|''n''}} = 1, 2, 3…-ra 0, 1, 1, 2, 1, 2, 1, 3, 2, … {{OEIS|id=A001222}}. |
||
== |
==Fordítás== |
||
* {{fordítás|en|Prime factor|oldid=694839918|n=a|4=angol}} |
* {{fordítás|en|Prime factor|oldid=694839918|n=a|4=angol}} |
||
== Kapcsolódó szócikkek == |
== Kapcsolódó szócikkek == |
||
* [[Összetett szám]] |
* [[Összetett szám]] |
||
* [[ |
* [[Osztó]] |
||
* [[Eratoszthenész szitája]] |
* [[Eratoszthenész szitája]] |
||
* [[Erdős–Kac-tétel]] |
* [[Erdős–Kac-tétel]] |
||
71. sor: | 65. sor: | ||
== További információk == |
== További információk == |
||
* [https://youproof.hu/kriptografia/16-oszhatosag-egyseg-asszocialt-felbonthatatlan-prim-szamelmelet-alaptetele Alice és Bob - 16. rész: Alice és Bob alaptétele] |
* [https://youproof.hu/kriptografia/16-oszhatosag-egyseg-asszocialt-felbonthatatlan-prim-szamelmelet-alaptetele Alice és Bob - 16. rész: Alice és Bob alaptétele] |
||
A lap 2021. május 17., 13:01-kori változata
A számelméletben egy pozitív egész szám prímtényezőin vagy törzstényezőin a szám prímszám osztóinak összességét értjük.[1] Egy pozitív egész szám prímfelbontása: a szám prímtényezőinek listázása, annak figyelembevételével, hogy hányszor szerepelnek a szám osztói között. A számelmélet alaptétele kimondja, hogy minden pozitív egész szám egyféleképpen bontható fel prímtényezők szorzatára.[2]
A prímtényezős felbontást a rövidség érdekében hatványformában szokás felírni. Például
melyben a 2, 3 és 5 prímtényezők multiplicitása 3, 2 illetve 1.
A felbontást a szám kanonikus alakjának is nevezik (pl. ).
Egy n szám p prímtényezőjét tekintve p multiplicitása az a legnagyobb a kitevő, amire pa osztója n-nek.
Egy n pozitív egész számra a prímtényezők száma és a prímtényezők összege (a multiplicitást nem tekintve) olyan számelméleti függvények, melyek additívak, de nem totálisan additívak.[3]
Négyzetszámok
A négyzetszámok arról ismerhetőek meg, hogy minden prímtényezőjük páros multiplicitással rendelkezik. Például a 144 (a 12 négyzete) prímtényezői:
Ezeket átrendezve:
Mivel minden prímtényező páros számúszor jelenik meg, az eredeti szám kifejezhető valamely kisebb szám négyzeteként. Hasonlóan, a köbszámok prímtényezőinek multiplicitása a 3 többszöröse s.í.t.
Relatív prímek
A közös prímtényezővel nem rendelkező pozitív egész számokat relatív prímeknek (angolul: coprime) nevezik. Ha a és b pozitív egész számok relatív prímek, ha legnagyobb közös osztójuk lnko(a, b) = 1. Az euklideszi algoritmussal meghatározható, hogy két szám relatív prím-e prímtényezőik ismerete nélkül is; az algoritmus a számjegyek száma szerint polinomiális időben fut le.
Az 1 szám minden pozitív egésszel és önmagával is relatív prím. Ennek oka, hogy nincsenek prímtényezői, ő az üres szorzat. Tehát lnko(1, b) = 1 bármely b ≥ 1.
Kriptográfiai alkalmazásai
A számok prímfelbontása titkosítási rendszerek kriptográfiai biztonságának fontos részét képezi;[4] a probléma ismereteink szerint a polinomiálisnál hosszabb időt vesz igénybe; viszonylag könnyű olyan problémát megalkotni, aminek megoldása az univerzum életkoránál hosszabb időt venne igénybe jelenlegi algoritmusainkkal.
Omega-függvények
Az ω(n) (omega) megmutatja az n szám különböző prímtényezőinek számát, míg a Ω(n) (nagy omega) függvény, az n szám összes prímtényezőjének a számát[2] Ha
- ,
akkor
- .
Például 24 = 23 × 31, így ω(24) = 2 és Ω(24) = 3 + 1 = 4.
- ω(n) értéke n = 1, 2, 3…-ra 0, 1, 1, 1, 1, 2, 1, 1, 1, … (A001221 sorozat az OEIS-ben).
- Ω(n) értéke n = 1, 2, 3…-ra 0, 1, 1, 2, 1, 2, 1, 3, 2, … (A001222 sorozat az OEIS-ben).
Fordítás
- Ez a szócikk részben vagy egészben a Prime factor című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
Kapcsolódó szócikkek
További információk
Jegyzetek
- ↑ Jensen, Gary R.. Arithmetic for Teachers: With Applications and Topics from Geometry. American Mathematical Society (2004)
- ↑ a b Riesel, Hans (1994), Prime numbers and computer methods for factorization, Basel, Switzerland: Birkhäuser, ISBN 978-0-8176-3743-9
- ↑ Melvyn B. Nathanson. Additive Number Theory: the Classical Bases, Graduate Texts in Mathematics. Springer-Verlag (1996). ISBN 0-387-94656-X
- ↑ Menezes, Alfred, van Oorschot, Paul C.; Vanstone, Scott A.. Handbook of Applied Cryptography. CRC Press (1996. október 1.). ISBN 0-8493-8523-7