• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Czynnik pierwszy

    Przeczytaj także...
    Teoria złożoności obliczeniowej – dział teorii obliczeń, którego głównym celem jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Rozważanymi zasobami są takie wielkości jak czas, pamięć lub liczba procesorów.Podstawowe twierdzenie arytmetyki – ważne twierdzenie teorii liczb o rozkładzie liczb naturalnych na czynniki pierwsze.
    Liczba pierwsza – liczba naturalna większa od 1, która ma dokładnie dwa dzielniki naturalne: jedynkę i siebie samą, np.

    Czynnik pierwszy danej liczby naturalnej złożonej, to dowolna liczba pierwsza, która dzieli ją bez reszty. Na przykład jednym z czynników pierwszych liczby 20 jest 5.

    Jedna z podstawowych obserwacji dotyczących liczb naturalnych mówi, że każda liczba naturalna większa od 1 jest albo pierwsza, albo ma przynajmniej jeden czynnik pierwszy. Wynika stąd dalej, że każda liczba naturalna większa od 1 jest pierwsza lub daje się zapisać w postaci iloczynu liczb pierwszych. Twierdzenie to nazywane jest często podstawowym twierdzeniem arytmetyki.

    RSA – jeden z pierwszych i obecnie najpopularniejszych asymetrycznych algorytmów kryptograficznych z kluczem publicznym, zaprojektowany w 1977 przez Rona Rivesta, Adi Shamira oraz Leonarda Adlemana. Pierwszy algorytm, który może być stosowany zarówno do szyfrowania jak i do podpisów cyfrowych. Bezpieczeństwo szyfrowania opiera się na trudności faktoryzacji dużych liczb złożonych. Jego nazwa pochodzi od pierwszych liter nazwisk jego twórców.Liczby naturalne – liczby służące podawaniu liczności (trzy osoby, zob. liczebnik główny/kardynalny) i ustalania kolejności (trzecia osoba, zob. liczebnik porządkowy), poddane w matematyce dalszym uogólnieniom (odpowiednio: liczby kardynalne, liczby porządkowe). Badaniem własności liczb naturalnych zajmują się arytmetyka i teoria liczb. Według finitystów, zwolenników skrajnego nurtu filozofii matematyki, są to jedyne liczby, jakimi powinna zajmować się matematyka - słynne jest stwierdzenie propagatora arytmetyzacji wszystkich dziedzin matematyki Leopolda Kroneckera: Liczby całkowite stworzył dobry Bóg. Reszta jest dziełem człowieka.

    Przedstawienie danej liczby złożonej w postaci iloczynu czynników pierwszych nazywamy rozkładem liczby na czynniki pierwsze. Rozkład ten jest jednoznaczny w tym sensie, że każde dwa rozkłady danej liczby na czynniki pierwsze różnią się tylko kolejnością czynników.

    Na przykład: 20 = 2•2•5 = 5•2•2 = 2•5•2 = 2•5.

    W matematyce p-adyczny system liczbowy dla dowolnej liczby pierwszej p stanowi rozszerzenie arytmetyki liczb wymiernych w sposób istotnie różny od rozszerzenia do liczb rzeczywistych bądź zespolonych. Rozszerzenie to uzyskuje się przez alternatywną interpretację pojęcia "bliskości" czy też wartości bezwzględnej. W szczególności, dwie liczby p-adyczne są bliskie, gdy ich różnica jest podzielna przez wysoką potęgę p. Ta własność sprawia, że liczby p-adyczne dobrze służą do opisu kongruencji. Okazuje się, że dzięki temu znajdują zastosowanie w teorii liczb, w tym w słynnym dowodzie Wielkiego Twierdzenia Fermata odkrytym przez Andrew Wilesa.Teoria liczb - dziedzina matematyki, zajmująca się badaniem własności liczb – początkowo tylko naturalnych, i do dziś dla wielu specjalistów są one szczególnie atrakcyjne.

    Dla czynników pierwszych prawdziwe są m.in. poniższe stwierdzenia:

  • każda liczba złożona ma czynnik pierwszy, który nie przekracza pierwiastka kwadratowego z tej liczby;
  • każda liczba naturalna postaci 4k + 3 jest albo pierwsza, albo ma przynajmniej jeden czynnik pierwszy tej postaci
  • 63 = 4•15 + 3 i 63 = 9•7, przy czym 7 = 4•1 + 3;
  • każda liczba naturalna postaci 6k + 5 jest albo pierwsza, albo ma przynajmniej jeden czynnik pierwszy tej postaci
  • 119 = 6•19 + 5 i 119 = 7•17, przy czym 17 = 6•2 + 5
  • Rozkład liczby naturalnej na czynniki pierwsze ma wysoką złożoność obliczeniową, co stanowi podstawę algorytmów stosowanych w kryptografii asymetrycznej (patrz np. klucz RSA).

    Kryptografia klucza publicznego (nazywana również kryptografią asymetryczną) to rodzaj kryptografii, w którym używa się zestawów dwu lub więcej powiązanych ze sobą kluczy, umożliwiających wykonywanie różnych czynności kryptograficznych. Jeden z kluczy może być udostępniony publicznie bez utraty bezpieczeństwa danych zabezpieczanych tym kryptosystemem.Liczba złożona – liczba naturalna większa od 1 niebędąca liczbą pierwszą, tj. mająca co najmniej jeden naturalny dzielnik różny od jedności i niej samej.

    Rozkład liczby wymiernej na czynniki[]

    Rozkład na czynniki pierwsze można też jednoznacznie wykonać dla dowolnej dodatniej liczby wymiernej . Wówczas:


    gdzie są liczbami całkowitymi.

    Definicja intuicyjna: Ułamki liczb całkowitych o niezerowym mianowniku; liczby rzeczywiste mające skończone, bądź okresowe od pewnego miejsca rozwinięcie dziesiętne.Ideał pierwszy – w teorii pierścieni taki ideał właściwy pierścienia przemiennego z jedynką, dla którego z należenia do niego iloczynu dwóch danych elementów pierścienia wynika przynależność do niego choć jednego czynników, tzn. ideał I pierścienia R nazywany jest pierwszym, gdy z należenia ab ∈ I wynika, że a ∈ I lub b ∈ I (a, b ∈ R).

    Taki rozkład ma duże znaczenie w teorii liczb, w szczególności służy do konstrukcji liczb p-adycznych.

    Algorytm rozkładu na czynniki pierwsze[]

    Elementarnym sposobem rozkładu liczb na czynniki pierwsze jest wykonywanie kolejnych dzieleń, np.:

    Szukamy najmniejszej liczby pierwszej dzielącej daną liczbę (56). Jest to 2. Dzielimy: 56/2=28. Powtarzamy tę czynność dla kolejnych wyników aż do uzyskania w ilorazie liczby 1. Otrzymujemy wówczas wszystkie dzielniki pierwsze szukanej liczby. Na schemacie znajdują się one po prawej stronie.

    Rho Pollarda to algorytm rozkładu liczb na czynniki pierwsze, opracowany przez Johna Pollarda w 1975 roku. Jest szczególnie efektywny przy rozkładaniu liczb mających niewielkie dzielniki. Dla liczb będących iloczynem dwóch liczb pierwszych tej samej długości, jego złożoność jest rzędu O(n polylog(n)).

    Zobacz też[]

  • ideał pierwszy
  • algorytm faktoryzacji rho Pollarda
  • Linki zewnętrzne[]

  • Strona umożliwiająca rozkład danej liczy na czynniki pierwsze (działa dla dużych liczb)



  • w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Reklama

    Czas generowania strony: 0.021 sek.