Przedstawiam kolejny test na pierwszość liczb Mersenne'a. Raczej jeszcze nie znany. No i niestety pewnie niepraktyczny, ponieważ wymaga wykonywania obliczeń na liczbach jeszcze większych, niż liczby testowane. Nie podaję twierdzeń, ani dowodów twierdzeń na których jest oparty (nie wszystkie mam gotowe, a popracowałbym nad nimi w wypadku, gdyby algorytm rzeczywiście miał szanse na jakąś "karierę").
1. Wybieramy jakąś liczbę \(\displaystyle{ 2^n-1}\).
2. Bierzemy wszystkie liczby pierwsze \(\displaystyle{ p_{1},...,p_{k}}\) mniejsze niż \(\displaystyle{ \sqrt{2^n-1}}\) i konstruujemy dla tych liczb funkcje zdefiniowane rekurencyjnie:
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {(2^n+1) \cdot x - (2^n-p_{1})}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
.
.
.
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {(2^n+1) \cdot x - (2^n-p_{k})}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
Obliczamy dla każdej z funkcji ciągi dla \(\displaystyle{ x=1}\), jednak tylko n-elementowe, więcej iteracji nie potrzebujemy, ponadto w ciągach interesuje nas tylko ich struktura pod względem wzrostów i spadków wzlędem poprzedniej liczby, czyli relacje większości i mniejszości pomiędzy sąsiadującymi elementami.
3. Załóżmy, że mamy już wyznaczone struktury naszych ciągów (zapisujemy je odwrotnie w postaci zero-jedynkowej):
\(\displaystyle{ k_{1} = \begin{bmatrix} w_{1}\\w_{2}\\.\\.\\.\\w_{n}\end{bmatrix}}\)
.
.
.
\(\displaystyle{ k_{m} = \begin{bmatrix} w_{1}\\w_{2}\\.\\.\\.\\w_{n}\end{bmatrix}}\)
\(\displaystyle{ w_{i}=0}\) lub \(\displaystyle{ w_{i}=1}\)
Na podstawie struktur tych ciągów konstruujemy liczby - kandydaty, które mogą być czynnikami badanej liczby pierwszej:
\(\displaystyle{ k_{1} = [2^{n-1}, 2^{n-2}, ... , 1] \cdot \begin{bmatrix} w_{1}\\w_{2}\\.\\.\\.\\w_{n}\end{bmatrix}}\)
* Jest to równoważne przeliczeniu liczb zapisanych w systemie dwójkowym na liczby w systemie dziesiętnym.
4. Odrzucamy te liczby \(\displaystyle{ p_{i}}\) i \(\displaystyle{ k_{i}}\) (jako potencjalne czynniki badanej liczby Mersenne'a) które nie spełniają równania poniżej (jeżeli ustalimy, że żadne z tych liczb nie faktoryzują naszej liczby, to jest ona liczbą pierwszą):
\(\displaystyle{ 2^n-1=p_{i} \cdot k_{i}}\)
Możemy to zrobić dowolnymi metodami. Ja jednak podam tu metodę pozostającą w konwencji tego algorytmu. Mając wyznaczone \(\displaystyle{ k_{i}}\) konstruujemy dla tych liczb funkcje zdefiniowane rekurencyjnie:
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {(2^n+1) \cdot x - (2^n-k_{1})}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
.
.
.
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {(2^n+1) \cdot x - (2^n-k_{k})}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
I obliczamy dla każdej z funkcji ciągi dla \(\displaystyle{ x=1}\), jednak tylko n-elementowe, więcej iteracji nie potrzebujemy, ponadto w ciągach znów interesuje nas tylko ich struktura.
Teraz konstruujemy wektory, takie, że:
\(\displaystyle{ p_{i} = [2^{n-1}, 2^{n-2}, ... , 1] \cdot \begin{bmatrix} w_{1}\\w_{2}\\.\\.\\.\\w_{n}\end{bmatrix}}\)
** Jest to równoważne zapisaniu liczb pierwszych \(\displaystyle{ p_{i}}\) w systemie dwójkowym.
i porównujemy czy któreś z nich są identyczne co struktura ciągów obliczonych przed chwilą dla liczb \(\displaystyle{ k_{i}}\). Jeżeli dla jakichś par liczb zachodzi taka zależność to \(\displaystyle{ 2^n-1=p_{i} \cdot k_{i}}\).
Przykład:
1. Weźmy liczbę \(\displaystyle{ 2^6-1}\).
2. \(\displaystyle{ p_{1}=3}\), \(\displaystyle{ p_{2}=5}\), \(\displaystyle{ p_{3}=7}\), zatem otrzymujemy funkcje:
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {65 \cdot x - 61}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {65 \cdot x - 59}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {65 \cdot x - 57}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
Obliczamy ciągi:
\(\displaystyle{ c_{1}=1,2,1,2,1,2,1}\)
\(\displaystyle{ c_{2}=1,3,68,34,17,523,16968}\)
\(\displaystyle{ c_{3}=1,4,2,1,4,2,1}\)
3. Nasze wektory wyglądają następująco (zapisujemy je odwrotnie, zaczynając od końca):
\(\displaystyle{ k_{1} = \begin{bmatrix} 0\\1\\0\\1\\0\\1\end{bmatrix}}\) - bo \(\displaystyle{ c_{1}= 1 < 2 > 1 < 2 > 1 < 2 > 1}\)
\(\displaystyle{ k_{2} = \begin{bmatrix} 1\\1\\0\\0\\1\\1\end{bmatrix}}\) - bo \(\displaystyle{ c_{2}= 16968 > 523 > 17 < 34 < 68 > 3 > 1}\)
\(\displaystyle{ k_{3} = \begin{bmatrix} 0\\0\\1\\0\\0\\1\end{bmatrix}}\) - bo \(\displaystyle{ c_{3}= 1 < 2 < 4 > 1 < 2 < 4 > 1}\)
Kontruujemy liczby:
\(\displaystyle{ k_{1} = [2^{5}, 2^{4}, 2^{3}, 2^{2}, 2^{1}, 1] \cdot \begin{bmatrix} 0\\1\\0\\1\\0\\1\end{bmatrix}=21}\)
\(\displaystyle{ k_{2} = [2^{5}, 2^{4}, 2^{3}, 2^{2}, 2^{1}, 1] \cdot \begin{bmatrix} 1\\1\\0\\0\\1\\1\end{bmatrix}=51}\)
\(\displaystyle{ k_{3} = [2^{5}, 2^{4}, 2^{3}, 2^{2}, 2^{1}, 1] \cdot \begin{bmatrix} 0\\0\\1\\0\\0\\1\end{bmatrix}=9}\)
4. Już w tym momencie mogę odrzucić liczbę \(\displaystyle{ 51}\), ponieważ jest za duża, aby pomonożona razy \(\displaystyle{ 5}\) dawała rozważaną liczbę Mersenne'a. Podobnie mogę zakończyć algorytm zauważając, że pozostałe liczby są złożone. Dla przykładu zweryfikujemy jednak pierwszą z nich. Konstruujemy funkcję:
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {65 \cdot x -43}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
Wyznaczony ciąg to \(\displaystyle{ 1,11,36,168,84,42,21 \equiv \begin{bmatrix} 0\\0\\0\\0\\1\\1\end{bmatrix}}\)
Teraz sprawdzamy czy liczba \(\displaystyle{ p_{1}=3}\) zapisana w systemie dwójkowym wygląda tak samo jak wyznaczony powyżej wektor dla \(\displaystyle{ k_{1}=21}\). Zauważamy, że:
\(\displaystyle{ p_{1}=3=[2^{5}, 2^{4}, 2^{3}, 2^{2}, 2^{1}, 1] \cdot \begin{bmatrix} 0\\0\\0\\0\\1\\1\end{bmatrix}}\)
Wektory te są identyczne, zatem \(\displaystyle{ 63=3 \cdot 21}\).
Co myślicie o tym algorytmie?
Algorytm poszukiwania liczb pierwszych Mersenne'a
-
Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
Algorytm poszukiwania liczb pierwszych Mersenne'a
W tym momencie nie ma już nadziei aby algorytm był praktyczny (zakładając, że jest poprawny).matemix pisze: 2. Bierzemy wszystkie liczby pierwsze \(\displaystyle{ p_{1},...,p_{k}}\) mniejsze niż \(\displaystyle{ \sqrt{2^n-1}}\) i (...)
-
matemix
- Użytkownik
- Posty: 465
- Rejestracja: 10 cze 2008, o 19:38
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 12 razy
- Pomógł: 1 raz
Algorytm poszukiwania liczb pierwszych Mersenne'a
Czyli rozumiem, że tych liczb pierwszych mniejszych niż pierwiastek z badanej liczby jest po prostu za dużo dla dużych liczb Mersenne'a. Ogólnie algorytm można zacząć od dowolnych liczb co do których mamy podejrzenie, że są czynnikami badanej liczby, tylko, że chyba nie ma metody jakiegoś selektywnego wyboru tylko niektórych liczb spośród tych mniejszych od pierwiastka z badanej liczby.
Cóż, w takim razie algorytm pozostanie tylko ciekawostką.
-- 24 lutego 2013, 23:36 --
Właśnie przypomniałem sobie o twierdzeniu które znacznie pozwala zmniejszyć wielkość ciągów na których wykonujemy obliczenia. Dlatego zamieszczam poniżej jeszcze raz zmieniony algorytm (na znacznie mniejszych ciągach).
1. Wybieramy jakąś liczbę \(\displaystyle{ 2^n-1}\).
2. Bierzemy wszystkie liczby pierwsze \(\displaystyle{ p_{1},...,p_{k}}\) mniejsze niż \(\displaystyle{ \sqrt{2^n-1}}\) i konstruujemy dla tych liczb funkcje zdefiniowane rekurencyjnie:
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {x + p_{1}}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
.
.
.
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {x + p_{k}}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
Obliczamy dla każdej z funkcji ciągi dla \(\displaystyle{ x=1}\), jednak tylko n-elementowe, więcej iteracji nie potrzebujemy, ponadto w ciągach interesuje nas tylko ich struktura pod względem wzrostów i spadków wzlędem poprzedniej liczby, czyli relacje większości i mniejszości pomiędzy sąsiadującymi elementami.
3. Załóżmy, że mamy już wyznaczone struktury naszych ciągów (zapisujemy je odwrotnie w postaci zero-jedynkowej):
\(\displaystyle{ k_{1} = \begin{bmatrix} w_{1}\\w_{2}\\.\\.\\.\\w_{n}\end{bmatrix}}\)
.
.
.
\(\displaystyle{ k_{m} = \begin{bmatrix} w_{1}\\w_{2}\\.\\.\\.\\w_{n}\end{bmatrix}}\)
\(\displaystyle{ w_{i}=0}\) lub \(\displaystyle{ w_{i}=1}\)
Na podstawie struktur tych ciągów konstruujemy liczby - kandydaty, które mogą być czynnikami badanej liczby pierwszej:
\(\displaystyle{ k_{1} = [2^{n-1}, 2^{n-2}, ... , 1] \cdot \begin{bmatrix} w_{1}\\w_{2}\\.\\.\\.\\w_{n}\end{bmatrix}}\)
* Jest to równoważne przeliczeniu liczb zapisanych w systemie dwójkowym na liczby w systemie dziesiętnym.
4. Odrzucamy te liczby \(\displaystyle{ p_{i}}\) i \(\displaystyle{ k_{i}}\) (jako potencjalne czynniki badanej liczby Mersenne'a) które nie spełniają równania poniżej (jeżeli ustalimy, że żadne z tych liczb nie faktoryzują naszej liczby, to jest ona liczbą pierwszą):
\(\displaystyle{ 2^n-1=p_{i} \cdot k_{i}}\)
Możemy to zrobić dowolnymi metodami. Ja jednak podam tu metodę pozostającą w konwencji tego algorytmu. Mając wyznaczone \(\displaystyle{ k_{i}}\) konstruujemy dla tych liczb funkcje zdefiniowane rekurencyjnie:
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {x + k_{1}}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
.
.
.
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {x + k_{k}}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
I obliczamy dla każdej z funkcji ciągi dla \(\displaystyle{ x=1}\), jednak tylko n-elementowe, więcej iteracji nie potrzebujemy, ponadto w ciągach znów interesuje nas tylko ich struktura.
Teraz konstruujemy wektory, takie, że:
\(\displaystyle{ p_{i} = [2^{n-1}, 2^{n-2}, ... , 1] \cdot \begin{bmatrix} w_{1}\\w_{2}\\.\\.\\.\\w_{n}\end{bmatrix}}\)
** Jest to równoważne zapisaniu liczb pierwszych \(\displaystyle{ p_{i}}\) w systemie dwójkowym.
i porównujemy czy któreś z nich są identyczne co struktura ciągów obliczonych przed chwilą dla liczb \(\displaystyle{ k_{i}}\). Jeżeli dla jakichś par liczb zachodzi taka zależność to \(\displaystyle{ 2^n-1=p_{i} \cdot k_{i}}\).
Przykład:
1. Weźmy liczbę \(\displaystyle{ 2^6-1}\).
2. \(\displaystyle{ p_{1}=3}\), \(\displaystyle{ p_{2}=5}\), \(\displaystyle{ p_{3}=7}\), zatem otrzymujemy funkcje:
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {x +3}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {x +5}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {x +7}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
Obliczamy ciągi:
\(\displaystyle{ c_{1}=1,2,1,2,1,2,1}\)
\(\displaystyle{ c_{2}=1,3,4,2,1,3,4}\)
\(\displaystyle{ c_{3}=1,4,2,1,4,2,1}\)
3. Nasze wektory wyglądają następująco (zapisujemy je odwrotnie, zaczynając od końca):
\(\displaystyle{ k_{1} = \begin{bmatrix} 0\\1\\0\\1\\0\\1\end{bmatrix}}\) - bo \(\displaystyle{ c_{1}= 1 < 2 > 1 < 2 > 1 < 2 > 1}\)
\(\displaystyle{ k_{2} = \begin{bmatrix} 1\\1\\0\\0\\1\\1\end{bmatrix}}\) - bo \(\displaystyle{ c_{2}= 4 > 3 > 1 < 2 < 4 > 3 > 1}\)
\(\displaystyle{ k_{3} = \begin{bmatrix} 0\\0\\1\\0\\0\\1\end{bmatrix}}\) - bo \(\displaystyle{ c_{3}= 1 < 2 < 4 > 1 < 2 < 4 > 1}\)
Kontruujemy liczby:
\(\displaystyle{ k_{1} = [2^{5}, 2^{4}, 2^{3}, 2^{2}, 2^{1}, 1] \cdot \begin{bmatrix} 0\\1\\0\\1\\0\\1\end{bmatrix}=21}\)
\(\displaystyle{ k_{2} = [2^{5}, 2^{4}, 2^{3}, 2^{2}, 2^{1}, 1] \cdot \begin{bmatrix} 1\\1\\0\\0\\1\\1\end{bmatrix}=51}\)
\(\displaystyle{ k_{3} = [2^{5}, 2^{4}, 2^{3}, 2^{2}, 2^{1}, 1] \cdot \begin{bmatrix} 0\\0\\1\\0\\0\\1\end{bmatrix}=9}\)
4. Już w tym momencie mogę odrzucić liczbę \(\displaystyle{ 51}\), ponieważ jest za duża, aby pomonożona razy \(\displaystyle{ 5}\) dawała rozważaną liczbę Mersenne'a. Podobnie mogę zakończyć algorytm zauważając, że pozostałe liczby są złożone. Dla przykładu zweryfikujemy jednak pierwszą z nich. Konstruujemy funkcję:
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {x+21}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
Wyznaczony ciąg to \(\displaystyle{ 1,11,16,8,4,2,1 \equiv \begin{bmatrix} 0\\0\\0\\0\\1\\1\end{bmatrix}}\)
Teraz sprawdzamy czy liczba \(\displaystyle{ p_{1}=3}\) zapisana w systemie dwójkowym wygląda tak samo jak wyznaczony powyżej wektor dla \(\displaystyle{ k_{1}=21}\). Zauważamy, że:
\(\displaystyle{ p_{1}=3=[2^{5}, 2^{4}, 2^{3}, 2^{2}, 2^{1}, 1] \cdot \begin{bmatrix} 0\\0\\0\\0\\1\\1\end{bmatrix}}\)
Wektory te są identyczne, zatem \(\displaystyle{ 63=3 \cdot 21}\).
Cóż, w takim razie algorytm pozostanie tylko ciekawostką.
-- 24 lutego 2013, 23:36 --
Właśnie przypomniałem sobie o twierdzeniu które znacznie pozwala zmniejszyć wielkość ciągów na których wykonujemy obliczenia. Dlatego zamieszczam poniżej jeszcze raz zmieniony algorytm (na znacznie mniejszych ciągach).
1. Wybieramy jakąś liczbę \(\displaystyle{ 2^n-1}\).
2. Bierzemy wszystkie liczby pierwsze \(\displaystyle{ p_{1},...,p_{k}}\) mniejsze niż \(\displaystyle{ \sqrt{2^n-1}}\) i konstruujemy dla tych liczb funkcje zdefiniowane rekurencyjnie:
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {x + p_{1}}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
.
.
.
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {x + p_{k}}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
Obliczamy dla każdej z funkcji ciągi dla \(\displaystyle{ x=1}\), jednak tylko n-elementowe, więcej iteracji nie potrzebujemy, ponadto w ciągach interesuje nas tylko ich struktura pod względem wzrostów i spadków wzlędem poprzedniej liczby, czyli relacje większości i mniejszości pomiędzy sąsiadującymi elementami.
3. Załóżmy, że mamy już wyznaczone struktury naszych ciągów (zapisujemy je odwrotnie w postaci zero-jedynkowej):
\(\displaystyle{ k_{1} = \begin{bmatrix} w_{1}\\w_{2}\\.\\.\\.\\w_{n}\end{bmatrix}}\)
.
.
.
\(\displaystyle{ k_{m} = \begin{bmatrix} w_{1}\\w_{2}\\.\\.\\.\\w_{n}\end{bmatrix}}\)
\(\displaystyle{ w_{i}=0}\) lub \(\displaystyle{ w_{i}=1}\)
Na podstawie struktur tych ciągów konstruujemy liczby - kandydaty, które mogą być czynnikami badanej liczby pierwszej:
\(\displaystyle{ k_{1} = [2^{n-1}, 2^{n-2}, ... , 1] \cdot \begin{bmatrix} w_{1}\\w_{2}\\.\\.\\.\\w_{n}\end{bmatrix}}\)
* Jest to równoważne przeliczeniu liczb zapisanych w systemie dwójkowym na liczby w systemie dziesiętnym.
4. Odrzucamy te liczby \(\displaystyle{ p_{i}}\) i \(\displaystyle{ k_{i}}\) (jako potencjalne czynniki badanej liczby Mersenne'a) które nie spełniają równania poniżej (jeżeli ustalimy, że żadne z tych liczb nie faktoryzują naszej liczby, to jest ona liczbą pierwszą):
\(\displaystyle{ 2^n-1=p_{i} \cdot k_{i}}\)
Możemy to zrobić dowolnymi metodami. Ja jednak podam tu metodę pozostającą w konwencji tego algorytmu. Mając wyznaczone \(\displaystyle{ k_{i}}\) konstruujemy dla tych liczb funkcje zdefiniowane rekurencyjnie:
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {x + k_{1}}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
.
.
.
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {x + k_{k}}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
I obliczamy dla każdej z funkcji ciągi dla \(\displaystyle{ x=1}\), jednak tylko n-elementowe, więcej iteracji nie potrzebujemy, ponadto w ciągach znów interesuje nas tylko ich struktura.
Teraz konstruujemy wektory, takie, że:
\(\displaystyle{ p_{i} = [2^{n-1}, 2^{n-2}, ... , 1] \cdot \begin{bmatrix} w_{1}\\w_{2}\\.\\.\\.\\w_{n}\end{bmatrix}}\)
** Jest to równoważne zapisaniu liczb pierwszych \(\displaystyle{ p_{i}}\) w systemie dwójkowym.
i porównujemy czy któreś z nich są identyczne co struktura ciągów obliczonych przed chwilą dla liczb \(\displaystyle{ k_{i}}\). Jeżeli dla jakichś par liczb zachodzi taka zależność to \(\displaystyle{ 2^n-1=p_{i} \cdot k_{i}}\).
Przykład:
1. Weźmy liczbę \(\displaystyle{ 2^6-1}\).
2. \(\displaystyle{ p_{1}=3}\), \(\displaystyle{ p_{2}=5}\), \(\displaystyle{ p_{3}=7}\), zatem otrzymujemy funkcje:
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {x +3}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {x +5}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {x +7}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
Obliczamy ciągi:
\(\displaystyle{ c_{1}=1,2,1,2,1,2,1}\)
\(\displaystyle{ c_{2}=1,3,4,2,1,3,4}\)
\(\displaystyle{ c_{3}=1,4,2,1,4,2,1}\)
3. Nasze wektory wyglądają następująco (zapisujemy je odwrotnie, zaczynając od końca):
\(\displaystyle{ k_{1} = \begin{bmatrix} 0\\1\\0\\1\\0\\1\end{bmatrix}}\) - bo \(\displaystyle{ c_{1}= 1 < 2 > 1 < 2 > 1 < 2 > 1}\)
\(\displaystyle{ k_{2} = \begin{bmatrix} 1\\1\\0\\0\\1\\1\end{bmatrix}}\) - bo \(\displaystyle{ c_{2}= 4 > 3 > 1 < 2 < 4 > 3 > 1}\)
\(\displaystyle{ k_{3} = \begin{bmatrix} 0\\0\\1\\0\\0\\1\end{bmatrix}}\) - bo \(\displaystyle{ c_{3}= 1 < 2 < 4 > 1 < 2 < 4 > 1}\)
Kontruujemy liczby:
\(\displaystyle{ k_{1} = [2^{5}, 2^{4}, 2^{3}, 2^{2}, 2^{1}, 1] \cdot \begin{bmatrix} 0\\1\\0\\1\\0\\1\end{bmatrix}=21}\)
\(\displaystyle{ k_{2} = [2^{5}, 2^{4}, 2^{3}, 2^{2}, 2^{1}, 1] \cdot \begin{bmatrix} 1\\1\\0\\0\\1\\1\end{bmatrix}=51}\)
\(\displaystyle{ k_{3} = [2^{5}, 2^{4}, 2^{3}, 2^{2}, 2^{1}, 1] \cdot \begin{bmatrix} 0\\0\\1\\0\\0\\1\end{bmatrix}=9}\)
4. Już w tym momencie mogę odrzucić liczbę \(\displaystyle{ 51}\), ponieważ jest za duża, aby pomonożona razy \(\displaystyle{ 5}\) dawała rozważaną liczbę Mersenne'a. Podobnie mogę zakończyć algorytm zauważając, że pozostałe liczby są złożone. Dla przykładu zweryfikujemy jednak pierwszą z nich. Konstruujemy funkcję:
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {x+21}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
Wyznaczony ciąg to \(\displaystyle{ 1,11,16,8,4,2,1 \equiv \begin{bmatrix} 0\\0\\0\\0\\1\\1\end{bmatrix}}\)
Teraz sprawdzamy czy liczba \(\displaystyle{ p_{1}=3}\) zapisana w systemie dwójkowym wygląda tak samo jak wyznaczony powyżej wektor dla \(\displaystyle{ k_{1}=21}\). Zauważamy, że:
\(\displaystyle{ p_{1}=3=[2^{5}, 2^{4}, 2^{3}, 2^{2}, 2^{1}, 1] \cdot \begin{bmatrix} 0\\0\\0\\0\\1\\1\end{bmatrix}}\)
Wektory te są identyczne, zatem \(\displaystyle{ 63=3 \cdot 21}\).
-
matemix
- Użytkownik
- Posty: 465
- Rejestracja: 10 cze 2008, o 19:38
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 12 razy
- Pomógł: 1 raz
Algorytm poszukiwania liczb pierwszych Mersenne'a
No tak. Z tego artykułu także wynika, że znajdowanie dużych liczb pierwszych za pomocą tego algorytmu jest wykluczone.ksisquare pisze:
Jakkolwiek kolejny raz go uprościłem, a właściwe niemal zupełnie zmieniłem. Tym razem, aby sprawdzić czy liczba \(\displaystyle{ 2^n-1}\) dzieli się przez dowolną liczbę \(\displaystyle{ d}\), wystarczy sprawdzić po ilu iteracjach zapętla się ciąg:
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {x}{2} + \frac {d}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
dla \(\displaystyle{ x=1}\).
Przykład:
\(\displaystyle{ d=23}\)
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {x}{2} + \frac {23}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
Ciąg dla liczby \(\displaystyle{ x=1}\) wygląda następująco: \(\displaystyle{ 12,6,3,13,18,9,16,8,4,2,1}\). Ciąg osiąga znów jedynkę po \(\displaystyle{ 11}\) iteracjach, zatem liczba \(\displaystyle{ 11}\) dzieli liczbę \(\displaystyle{ 2^{11}-1}\).
Algorytm możemy odwrócić i sprawdzić jaką liczbę Mersenne'a dzieli wybrany dzielnik. Największy wynik jaki obliczyłem tą metodą, to, że liczba \(\displaystyle{ 65655522517}\) dzieli liczbę \(\displaystyle{ 2^{14828906748}-1}\), przy czym zajęło to mojemu komputerowi lekko ponad 8 minut.
-
ksisquare
- Użytkownik
- Posty: 132
- Rejestracja: 1 cze 2012, o 07:04
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Pomógł: 15 razy
Algorytm poszukiwania liczb pierwszych Mersenne'a
ma się zapętlić, czy wystarczy, że dojdzie do czegoś?matemix pisze:[..] wystarczy sprawdzić po ilu iteracjach zapętla się ciąg:[...]
Otrzeźwieję, przemyślę, ciekawy chyba sposób
-
matemix
- Użytkownik
- Posty: 465
- Rejestracja: 10 cze 2008, o 19:38
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 12 razy
- Pomógł: 1 raz
Algorytm poszukiwania liczb pierwszych Mersenne'a
Zaczynając od jedynki mamy dojść do jedynki - i ustalić po ilu iteracjach to się dzieje. Czyli ma się zapętlić, ale nie badamy innych iksów początkowych (startowych) niż \(\displaystyle{ x=1}\).ksisquare pisze:ma się zapętlić, czy wystarczy, że dojdzie do czegoś?matemix pisze:[..] wystarczy sprawdzić po ilu iteracjach zapętla się ciąg:[...]
Otrzeźwieję, przemyślę, ciekawy chyba sposób