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



    Podstrony: 1 [2] [3]
    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.Rozkład na czynniki lub faktoryzacja – proces, w którym dla danego obiektu znajdują się obiekty, takie że ich iloczyn jest jemu równy, przez co są one w pewnym sensie od niego prostsze.

    Czynnik pierwszy – dowolna liczba pierwsza, która dzieli bez reszty daną liczbę naturalną złożoną. Na przykład jednym z czynników pierwszych liczby 20 jest 5.

    Jedna z podstawowych obserwacji dotyczących liczb naturalnych mówi: każda liczba naturalna większa od 1 jest albo pierwsza, albo ma przynajmniej jeden czynnik pierwszy. Z niej wynika kolejna: każda liczba naturalna większa od 1 jest pierwsza lub daje się zapisać w postaci iloczynu liczb pierwszych. Twierdzenie to nazywa się podstawowym twierdzeniem arytmetyki.

    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.

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

    Na przykład:

    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.Twierdzenie o dzieleniu z resztą – twierdzenie matematyczne mówiące o możliwości przedstawienia danej liczby całkowitej, dzielnej, w postaci sumy iloczynu ilorazu przez (niezerowy) dzielnik oraz reszty. Innymi słowy twierdzenie mówi, ile razy (iloraz) dana liczba (dzielnik) mieści się w całości w innej (dzielna) oraz jaka część (reszta) tej liczby nie została wydzielona. Stosuje się także skróconą wersję nazwy: twierdzenie o dzieleniu.

    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
  • i przy czym
  • każda liczba naturalna postaci 6k + 5 jest albo pierwsza, albo ma przynajmniej jeden czynnik pierwszy tej postaci
  • i przy czym
  • 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).

    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.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.

    Rozkład liczby wymiernej na czynniki[ | edytuj kod]

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


    gdzie są liczbami całkowitymi.

    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.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.

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

    Podstrony: 1 [2] [3]




    Warto wiedzieć że... beta

    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.
    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).
    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)).

    Reklama

    Czas generowania strony: 0.02 sek.