faktoryzacja

Blog o faktoryzacji liczb naturalnych

Twierdzenie Wilsona

Nie daje mi spokoju test pierwszości Wilsona:
http://pl.wikipedia.org/wiki/Twierdzenie_Wilsona
Zastanawiam się czy nie da się go uprościć/ulepszyć (ewentualnie wykorzystać potem do stworzenia wzoru na liczby pierwsze).

Liczba p jest pierwsza jeśli liczba (p-1)!+1 jest podzielna przez nią.
Lub inaczej (p-1)!%p=p-1

Zrobiłem na tej podstawie równanie:
(p-1)!=pk+(p-1)
Stwierdziłem, że można jeszcze uściślić:
(p-1)!=p*(p-1)*k+(p-1)
lub:
(p-1)!=(p-1)(pk+1)

Na razie nie mam pomysłu co z tym dalej zrobić.

Reklamy

wzór na liczby złożone

W końcu udało mi się znaleźć osobisty punkt zaczepienia w kwestii liczb pierwszych i faktoryzacji.
Wzór na liczby nieparzyste złożone:
n=2*(pk*\frac{(p-1)}{2})+1
,gdzie p to liczba pierwsza, a   k    to krotność.

Na tej podstawie można próbować wymyślić test pierwszości, sprawdzając w jakiś sposób czy dana liczba jest w tej formie.
Można też próbować wymyślić metodę faktoryzacji. Metoda musiałaby szukać liczby p(czyli pierwszej) takiej, że n%p=(p-1)/2

Jak na razie nie ma pomysłu w tych dwóch kwestiach.

Faktoryzacja a liczby trójkątne

Udało mi się wymyślić ogólny wzór na dzielniki dla n będącego różnicą dwóch liczb trójkątnych o różnej parzystości.Podaje poniżej wzór zawarty w hipotezie(nie mam dowodu :p ).

Hipoteza:
Jeśli różnica liczb trójkątnych x-y=n  gdzie x=\frac{(a*(a+1))}{2} , y=\frac{(b*(b+1))}{2}   i  jednocześnie a  i  b są takiej samej parzystości to:
n=(\frac{((2a+1)-(2b+1))}{4})*(\frac{(2a+2b+2)}{2})
czyli
n=\frac{(a-b)}{2}*(a+b+1)

Dla a i b o różnej parzystości:
n=(a-b)*\frac{(a+b+1)}{2}

Aktualizacja:

Nie jestem matematykiem więc ciężko mi odróżnić czy dany wzór jest prosty do wyprowadzenia.Szukałem informacji na temat różnicy dwóch liczb trójkątnych i natrafiłem na wzór który podałem(z tym, że zamiast n jest 2n ale to nic nie zmienia):

http://www.fluxionsdividebyzero.com/p1/math/number/n016.xml

Następnym razem będę dokładniej sprawdzać.Dalej pozostaje kwestia znajdowania danych x i y bez znajomości dzielników(to już nie będzie takie łatwe 🙂 )  i  kwestia wykorzystania kongruencji trójkątnych.

Dodatkowo podaje ciekawy dokument, który znalazłem:

www.fq.math.ca/Scanned/39-3/nyblom.pdf

Pierwszy Wpis

Na początek wyjaśnienie czym jest owa faktoryzacja  liczby złożonej naturalnej.Jest to po prostu znalezienie jej dzielników pierwszych i przedstawienie jej jako iloczynu tych liczb pierwszych np.  35=5*7,  1007=19*53, 3233=53*61, 210=2*3*5*7
Liczby pierwsze to liczby  naturalne podzielne tylko przez siebie i przez jedynkę(z pominięciem liczby 1). Kolejne liczby pierwsze: 2,3,5,7,11,13,17,19,23,29,31…

Wracając do faktoryzacji…faktoryzacja dużych liczb(np. 309 cyfrowych) ,szczególnie pół-pierwszych takich, które mają dzielniki daleko od siebie stanowi spory problem co zostało użyte w RSA. Najszybszy(dla dużych liczb) obecnie algorytm ogólnego zastosowania to GNFS(Ogólne sito ciała liczbowego). RSA stanowi  np. podstawę bezpieczeństwa naszego hasła gdy logujemy się na pocztę.Używane jest także w podpisach cyfrowych.

Lista algorytmów/metod (mogłem coś pominąć):
metoda kolejnych dzieleń, metoda koła, metoda rho Pollarda, metoda p-1, metoda p+1, metoda Fermata, metoda Eulera, metoda krzywych eliptyczny Lenstry(ecm), metoda Shanksa, metoda Dixona, sito kwadratowe, metoda ułamków łańcuchowych(CFRAC), metoda sita liczbowego, SNFS(Specjalne sito ciała liczbowego), GNFS

Dla komputerów kwantowych :
kwantowy algorytm Shora