Discussion:
(nowy) algorytm poszukiwania liczb pierwszych
(Wiadomość utworzona zbyt dawno temu. Odpowiedź niemożliwa.)
o***@interia.pl
2013-03-03 08:42:08 UTC
Permalink
Mam kolejne pytanie, a nie ma sensu robić off-topic'a w moich poprzednich tematach, więc zakładam nowy.

Jakie są najszybsze obecnie znane algorytmy poszukiwania zwykłych liczb pierwszych (nie będących żadnej szczególnej postaci)?

Czy istnieje coś szybszego niż trial division:

http://en.wikipedia.org/wiki/Trial_division

Przypatrzyłem się trochę funkcji:

f(x) = x/2 + d/2 - gdy x jest nieparzyste
f(x) = x/2 - gdy x jest parzyste

dla x startowego x=1, pod kątem badania w ogóle liczb pierwszych (nie tylko Mersenne'a) i wykazuje ona pewne właściwości. Po pierwsze czasy stopów (ilość iteracji po których funkcja, zaczynając od x=1 znów osiągnie x=1) dla różnych liczb pierwszych d nie powtarzają się oraz są zawsze mniejsze niż same testowane liczby, a dodatkowo liczby pierwsze d postaci:

- 2^k-1, mają w niej czas stopu = k (a także nie - pierwsze)
- 2^(2^k)+1, mają w niej czas stopu = 2^(k+1) (a także nie - pierwsze)
- zwykłe liczby pierwsze d, mają czasy stopów t, takie, że t dzieli d-1

Wydaje się, że żadna liczba złożona nie wykazuje ostatniej własności. Dlatego można by wykorzystać tę funkcje, do testowania liczb pod kątem pierwszości. Mianowicie, aby sprawdzić czy dana liczba d jest pierwsza wystarczyłoby sprawdzić czy jest ona wielokrotnością swojego czasu stopu, w powyższej funkcji. Co więcej sprawdzenie pierwszości liczby tą metodą nie wymaga znajomości żadnej z liczb pierwszych mniejszych niż jej pierwiastek, ani tym podobnych.

Czy gdyby algorytm okazał się poprawny miałby szanse konkurować ze współcześnie stosowanymi?


Na koniec zaznaczam, że powyższe przypuszczenia podaję, tylko jako (obserwacyjne) hipotezy, których co więcej, tym razem nie mam pojęcia jak udowodnić. Stąd też znaleziona w ten sposób liczba pierwsza wymagałaby weryfikacji klasyczną metodą.
bartekltg
2013-03-03 10:50:43 UTC
Permalink
Post by o***@interia.pl
Mam kolejne pytanie, a nie ma sensu robić off-topic'a w moich
poprzednich tematach, więc zakładam nowy.
Jakie są najszybsze obecnie znane algorytmy poszukiwania zwykłych
liczb pierwszych (nie będących żadnej szczególnej postaci)?
http://en.wikipedia.org/wiki/Trial_division
Tak, to najprostszy i najwolniejszy algorytm
(co zresztą piszą w pierwszym zdaniu:))

Masz już ten artykuł, przejrzyj tabelkę na końcu.
Szczególnie "Primality tests" i "Prime generating algorithms".

Te pierwsze pobierają liczbę i sprawdzają, czy jest pierwsza.
Druga kategoria "odsiewa" liczby pierwsze z przedziału <n.

Do poszukiwania dużych liczb druga kategoria nadaje
się dość kiepsko (bo 'wypisuje' zbyt dużo liczb).
Za to taki test Millera-Rabina szybciutko sprawdza,
czy liczba jest pierwsza (z pewnym prawdopodobieństwem
pomyłki), a liczby pierwsze są dość gęsto.
Tak np generuje się duże liczby pierwsze do kryptografii.
Post by o***@interia.pl
f(x) = x/2 + d/2 - gdy x jest nieparzyste f(x) = x/2 - gdy x jest
parzyste
dla x startowego x=1, pod kątem badania w ogóle liczb pierwszych (nie
d to badana liczba?
Post by o***@interia.pl
Wydaje się, że żadna liczba złożona nie wykazuje ostatniej własności.
Dlatego można by wykorzystać tę funkcje, do testowania liczb pod
kątem pierwszości. Mianowicie, aby sprawdzić czy dana liczba d jest
pierwsza wystarczyłoby sprawdzić czy jest ona wielokrotnością swojego
czasu stopu, w powyższej funkcji. Co więcej sprawdzenie pierwszości
liczby tą metodą nie wymaga znajomości żadnej z liczb pierwszych
mniejszych niż jej pierwiastek, ani tym podobnych.
Rozumiem, że dowodu nie masz. A testy jakie zrobiłeś?
Post by o***@interia.pl
Czy gdyby algorytm okazał się poprawny miałby szanse konkurować ze
współcześnie stosowanymi?
Jeśli d jest pierwsza i jest wielokrotnością
swojego czasu stopu, to czas stopu to albo d,
albo 1. 1 odpada dla liczb rozsądnego rozmiaru.

Chcesz więc wykonać d operacji na liczbie rozmiaru
log(d).
Już nawet dzielenie przezz wszytkie liczby <sqrt(n)
zajmie log(d)^2 * sqrt(d) czyli znacznie szybciej.

Oba testy mają wykładniczy czas względem liczby
cyfr w liczbie - są wolne.

M-R przy naiwnej implementacji liczy
O(k*log(d)^3) gdzie k to liczba powtórzeń
(w końcu to alg probabilistyczny)
W każdym razie, wynik jest wielomianowy względem rozmiaru liczby.
Post by o***@interia.pl
Na koniec zaznaczam, że powyższe przypuszczenia podaję, tylko jako
(obserwacyjne) hipotezy, których co więcej, tym razem nie mam pojęcia
jak udowodnić. Stąd też znaleziona w ten sposób liczba pierwsza
wymagałaby weryfikacji klasyczną metodą.
Rozumiem, że udowodnić nie możesz, ale przetestować możesz.
A szczegolnie mozesz czytać artykuły z wiki, które sam podsyłasz;>

pzdr
bartekltg
Marcin
2013-03-03 15:17:37 UTC
Permalink
Post by bartekltg
Rozumiem, że udowodnić nie możesz, ale przetestować możesz.
A szczegolnie mozesz czytać artykuły z wiki, które sam podsyłasz;>
pzdr
bartekltg
Wydaje sie, ze sprawdzanie czy liczba jest liczba pierwsza
deterministycznie w czasie wielomianowym bez zakladania prawdziwosci
zadnej hipotezy jest na topie. Wyscig sie zaczal w 2002, kiedy powstal
pierwszy algorytm tego typu. Narazie chyba sa one slabsze numerycznie od
poprzednich testow.

Pozdrawiam
Marcin
bartekltg
2013-03-03 15:36:08 UTC
Permalink
Post by Marcin
Post by bartekltg
Rozumiem, że udowodnić nie możesz, ale przetestować możesz.
A szczegolnie mozesz czytać artykuły z wiki, które sam podsyłasz;>
pzdr
bartekltg
Wydaje sie, ze sprawdzanie czy liczba jest liczba pierwsza
deterministycznie w czasie wielomianowym bez zakladania prawdziwosci
zadnej hipotezy jest na topie. Wyscig sie zaczal w 2002, kiedy powstal
pierwszy algorytm tego typu. Narazie chyba sa one slabsze numerycznie od
poprzednich testow.
2002 się zgadza:
http://en.wikipedia.org/wiki/AKS_primality_test
To rzeczywiście ciekawe. Widzę jeszcze jedne, nowszy:
http://en.wikipedia.org/wiki/Elliptic_curve_primality_proving
ale nic więcej.

Na razie rzeczywiście do zastąpienia M-R trochę brakuje.


pzdr
bartekltg
o***@interia.pl
2013-03-03 16:09:09 UTC
Permalink
Post by bartekltg
d to badana liczba?
Tak.
Post by bartekltg
Rozumiem, że dowodu nie masz. A testy jakie zrobiłeś?
Nie mam dowodu, ani nie mam pomysłu na dowód jak na razie. Testowałem liczby do 200, i wybrane liczby do około 10^10, więc niewiele jak na razie.
Post by bartekltg
Chcesz więc wykonać d operacji na liczbie rozmiaru
log(d).

Właściwie nie bardzo rozumiem te oszacowania złożoności obliczeniowej (dlatego nie mogę sobie sam odpowiedzieć na pytanie czy mój algorytm się do czegoś nadaje). Więc zakładając najgorszy wariant (konieczność wykonania d-1 iteracji dla każdej testowanej liczby d), jaką ten mój algortym ma złożoność?

A gdyby okazało się, że dla dużych liczb d czasy stopów wynoszą średnio np. ln(d), to jaką by miał złożoność?
bartekltg
2013-03-03 17:17:08 UTC
Permalink
Post by o***@interia.pl
Post by bartekltg
d to badana liczba?
Tak.
Post by bartekltg
Rozumiem, że dowodu nie masz. A testy jakie zrobiłeś?
Nie mam dowodu, ani nie mam pomysłu na dowód jak na razie. Testowałem
liczby do 200, i wybrane liczby do około 10^10, więc niewiele jak na
razie.
Post by bartekltg
Chcesz więc wykonać d operacji na liczbie rozmiaru
log(d).
Właściwie nie bardzo rozumiem te oszacowania złożoności obliczeniowej
A co tu do rozumienia?
Napisałeś "Mianowicie, aby sprawdzić czy dana liczba d jest
pierwsza wystarczyłoby sprawdzić czy jest ona wielokrotnością
swojego czasu stopu, w powyższej funkcji."

To ile możę wynosić czas stopu? n*d.
A co to oznacza? że musisz sykonać n*d kroków.
Post by o***@interia.pl
(dlatego nie mogę sobie sam odpowiedzieć na pytanie czy mój algorytm
się do czegoś nadaje). Więc zakładając najgorszy wariant (konieczność
wykonania d-1 iteracji dla każdej testowanej liczby d), jaką ten mój
algortym ma złożoność?
Przecież napisałem. d*log(d)
d bo ilość kroków. W każym kroku dochodzi log(d) bo wykonmujesz
mnożęnie przez amłą liczbę i dodawanie liczb rzędu d.
A takie mają log(d) cyfr, czyli muszą zajmować tyle komórek
pamięci.
Post by o***@interia.pl
A gdyby okazało się, że dla dużych liczb d czasy stopów wynoszą
średnio np. ln(d), to jaką by miał złożoność?
Widzę tu niekonsekwencję. Napisałeś, że dowodem
pierwszości ma być podzielność liczby d przez
liczbę kroków.
A interesują nas liczby pierwsze, one podzielne są
jedynie na 1 i d. W żadnym wypadku na liczbę rzędu ln(d)



BTW. rozumeim dwa posty jeden za drugim. Ale taką serię?
Dwa razy pod rząd?

pzdr
bartekltg
o***@interia.pl
2013-03-03 16:38:55 UTC
Permalink
Na marginesie, zauważyłem, że liczby postaci a^n, gdzie "a" nie jest liczbą Mersenne'a mają czasy stopu a^n-a^(n-1).
o***@interia.pl
2013-03-03 16:40:55 UTC
Permalink
Na marginesie, zauważyłem, że liczby pierwsze postaci a^n, gdzie "a" nie jest liczbą Mersenne'a mają czasy stopu a^n-a^(n-1).
o***@interia.pl
2013-03-03 16:56:53 UTC
Permalink
Dodatkowo zauważyłem, że liczby a^n wykazują pewne zbieżności jeżeli chodzi o czasy stopów.

Niech a ma czas stopu k.

Czas stopu liczby a^n, przy n dążącym do nieskończoności wynosi a/k.
o***@interia.pl
2013-03-03 16:59:46 UTC
Permalink
Dodatkowo zauważyłem, że liczby a^n wykazują pewne zbieżności jeżeli chodzi o czasy stopów.

Niech a ma czas stopu k.

Niech a^n ma czas stopu k_n.

Iloczyn a^n/k_n, przy n dążącym do nieskończoności wynosi a/k.
o***@interia.pl
2013-03-03 17:01:49 UTC
Permalink
Dodatkowo zauważyłem, że liczby a^n, gdzie "a" jest liczbą pierwszą wykazują pewne zbieżności jeżeli chodzi o czasy stopów.

Niech a ma czas stopu k.

Niech a^n ma czas stopu k_n.

Iloczyn a^n/k_n, przy n dążącym do nieskończoności wynosi a/k.
o***@interia.pl
2013-03-03 17:07:48 UTC
Permalink
Dodatkowo zauważyłem, że liczby a^n, gdzie "a" jest liczbą pierwszą wykazują pewne zbieżności jeżeli chodzi o czasy stopów.

Niech a ma czas stopu k.

Niech a^n ma czas stopu k_n.

Iloczyn a^n/k_n, przy n dążącym do nieskończoności wynosi a/k
o***@interia.pl
2013-03-03 17:11:37 UTC
Permalink
Dodatkowo zauważyłem, że liczby a^n, gdzie "a" jest liczbą pierwszą wykazują pewne zbieżności jeżeli chodzi o czasy stopów.

Niech a ma czas stopu k.

Niech a^n ma czas stopu k_n.

Iloczyn a^n/k_n, przy n dążącym do nieskończoności wynosi a/k.
bartekltg
2013-03-03 17:23:29 UTC
Permalink
Post by o***@interia.pl
Dodatkowo zauważyłem, że liczby a^n, gdzie "a" jest liczbą pierwszą wykazują pewne zbieżności jeżeli chodzi o czasy stopów.
Niech a ma czas stopu k.
Niech a^n ma czas stopu k_n.
Iloczyn a^n/k_n, przy n dążącym do nieskończoności wynosi a/k.
Od kilkunastu minut wysyłasz tego samego posta.
Trafił tu już chyba 4 czy 5 raz. Ogarnij się i czytnik;>

pzdr
bartekltg
o***@interia.pl
2013-03-03 19:56:14 UTC
Permalink
Post by bartekltg
Post by o***@interia.pl
Właściwie nie bardzo rozumiem te oszacowania złożoności obliczeniowej
A co tu do rozumienia?
Napisałeś "Mianowicie, aby sprawdzić czy dana liczba d jest
pierwsza wystarczyłoby sprawdzić czy jest ona wielokrotnością
swojego czasu stopu, w powyższej funkcji."
Dokładnie czy d-1 jest wielokrotnością.
Post by bartekltg
To ile możę wynosić czas stopu? n*d.
A co to oznacza? że musisz sykonać n*d kroków.
Post by o***@interia.pl
(dlatego nie mogę sobie sam odpowiedzieć na pytanie czy mój algorytm
się do czegoś nadaje). Więc zakładając najgorszy wariant (konieczność
wykonania d-1 iteracji dla każdej testowanej liczby d), jaką ten mój
algortym ma złożoność?
Przecież napisałem. d*log(d)
d bo ilość kroków. W każym kroku dochodzi log(d) bo wykonmujesz
mnożęnie przez amłą liczbę i dodawanie liczb rzędu d.
A takie mają log(d) cyfr, czyli muszą zajmować tyle komórek
pamięci.
Aha.
Post by bartekltg
Post by o***@interia.pl
A gdyby okazało się, że dla dużych liczb d czasy stopów wynoszą
średnio np. ln(d), to jaką by miał złożoność?
Widzę tu niekonsekwencję. Napisałeś, że dowodem
pierwszości ma być podzielność liczby d przez
liczbę kroków.
A interesują nas liczby pierwsze, one podzielne są
jedynie na 1 i d. W żadnym wypadku na liczbę rzędu ln(d)
Tak, to był tylko przykład.
Post by bartekltg
BTW. rozumeim dwa posty jeden za drugim. Ale taką serię?
Dwa razy pod rząd?
To przez to, że ja lubię często edytować swoje posty, a tu nie można tego robić, więc gdy chcę coś edytować, a nikt jeszcze nie odpisał to usuwam i zamieszczam szybko jeszcze raz.
Andrzej P. Wozniak
2013-03-04 18:35:11 UTC
Permalink
Post by o***@interia.pl
Post by bartekltg
BTW. rozumeim dwa posty jeden za drugim. Ale taką serię?
Dwa razy pod rząd?
To przez to, że ja lubię często edytować swoje posty, a tu nie można
tego robić, więc gdy chcę coś edytować, a nikt jeszcze nie odpisał to
usuwam i zamieszczam szybko jeszcze raz.
To nie jest forum trzymane na jednym serwerze, tylko grupa dyskusyjna
dostępna na setkach różnych serwerów. Cokolwiek usuwasz, usuwasz tylko
u siebie, wszystkie Twoje śmieci idą na cały świat.
--
Andrzej P. Woźniak ***@pochta.onet.pl (zamień miejscami z<->h w adresie)
Grand Inquisitor pl.internet.pomoc Trust No.1 http://evil.pl/pip/
o***@interia.pl
2013-03-04 20:08:40 UTC
Permalink
Moja hipoteza:

"zwykłe liczby pierwsze d, mają czasy stopów t, takie, że t dzieli d-1 (oraz liczby złożone nie wykazują takiej własności)"

okazała się być fałszywa, choć nie do końca. Okazuje się, że zależność ta może zachodzić także dla liczb złożonych - ale pod warunkiem, że są pseudopierwsze (przy podstawie 2). Zatem wydaje się, że tą funkcją można by wykrywać także liczby pseudopierwsze.


Poza tym coś mi się nie zgadza w tych szacunkach złożoności algorytmu. Zauważyłem, że liczby d-1 są wielokrotnością czasów stopów liczb pierwszych d. Dodatkowo zauważyłem, że liczby złożone nie mają czasów stopów większych niż one same (ale nie wykazują własności mówiącej, że t dzieli d-1).

Zakładamy, że dana liczba d może się zapętlać po co najmniej log_2 (d) iteracjach (przypadek liczb Mersenne'a) i co najwyżej po d iteracjach (dokładnie po d-1 iteracjach zapętlają się np. niektóre liczby pierwsze - natomiast niemożliwe jest najprawdpdobniej, aby liczby złożone miały czasy stopów d-1 (i większe), to przeczyłoby hipotezie postawionej na samym początku wątku). Ponieważ niewiele wiemy o całej funkcji nie wiemy po ilu operacjach będzie się to działo.
Post by o***@interia.pl
Mianowicie, aby sprawdzić czy dana liczba d jest
pierwsza wystarczyłoby sprawdzić czy jest ona wielokrotnością swojego
czasu stopu, w powyższej funkcji.
Tu źle się wyraziłem. Wielokrotnością czasu stopu dla liczby pierwszej d jest dokładnie liczba d-1, a nie sama liczba d. Na przykład liczba pierwsza 89 ma czas stopu 11, i 11 dzieli 89-1. Z kolei liczba złożona 35 ma czas stopu 12, i 12 nie dzieli 34.
Post by o***@interia.pl
Jeśli d jest pierwsza i jest wielokrotnością
swojego czasu stopu, to czas stopu to albo d,
albo 1. 1 odpada dla liczb rozsądnego rozmiaru.
I to rozumowanie przez to także zawiera błąd.

Ogólnie podejrzewam, że czasy stopów kolejnych liczb w tej funkcji zmieniają się logarytmicznie (mniej więcej, ponieważ funkcja zachowuje się dosyć chaotycznie), ale nie napisałem jeszcze programu który sprawdziłby jakiś porzadny zakres liczb np. do miliona.
Post by o***@interia.pl
To nie jest forum trzymane na jednym serwerze, tylko grupa dyskusyjna
dostępna na setkach różnych serwerów. Cokolwiek usuwasz, usuwasz tylko
u siebie, wszystkie Twoje śmieci idą na cały świat.
Ok. Postaram się zamieszczać uwagi i sprostowania, zamiast usuwać posty z błędami.
Andrzej P. Wozniak
2013-03-05 12:58:47 UTC
Permalink
Post by o***@interia.pl
Post by Andrzej P. Wozniak
To nie jest forum trzymane na jednym serwerze, tylko grupa dyskusyjna
dostępna na setkach różnych serwerów. Cokolwiek usuwasz, usuwasz tylko
u siebie, wszystkie Twoje śmieci idą na cały świat.
Ok. Postaram się zamieszczać uwagi i sprostowania, zamiast usuwać posty z błędami.
Nie. Swój śmietnik trzymaj u siebie na dysku, a tu wysyłaj tylko przemyślane
wypowiedzi. To nie jest komunikator ani czat, nikt Cię nie pogania.
Jeśli chcesz coś robić szybko, to w pierwszym rzędzie powinna być to uważna
lektura netykiety i dostosowanie się do jej zaleceń. Oczywiście możesz to
zignorować, ale wtedy wszyscy zaczną ignorować Ciebie i będziej co najwyżej
mógł pogadać z lustrem.

W szczególności zwróć uwagę na następujące zalecenia, których
nieprzestrzeganie utrudnia czytanie dyskusji i zniechęca do odpowiadania:

1. Tocz dyskusję, czyli odpowiadaj bezpośrednio na wiadomość osoby
cytowanej, a nie swoją własną.
Dobre czytniki automatycznie umieszczają referencje do cytowanych
wiadomości, co pozwala wyświetlać całą dyskusję wielu osób jako drzewko
i zaznaczać do śledzenia właściwy fragment drzewka. Wiadomość, na którą
teraz odpowiadam, nie została jednak napisana jako odpowiedź na moją
wiadomość, przez co nie mogła zostać stosownie zaznaczona, więc mogła
zostać pominięta bądź nawet zignorowana w bardziej rozwiniętej dyskusji.

2. Wyraźnie zaznaczaj w tekście, komu i na co odpowiadasz i w jednej
wiadomości odpowiadaj w miarę możliwości tylko jednej osobie.
Inny sposób odpowiadania utrudnia zorientowanie się w dyskusji i osobom
postronnym, i samym dyskutantom. W tym przypadku wyciąłem część wiadomości,
która nie była skierowana do mnie, ale żeby zgadnąć, komu i na co właściwie
odpowiadasz, musiałbym przeczytać cały wątek. Wyobraź sobie teraz wątek
zawierający kilkanaście tysięcy wiadomości.

3. Cytuj poprawnie. Nie używaj narzędzi, które psują formatowanie tekstu
lub poprawiaj formatowanie ręcznie.
Podwójna interlinia, która się pojawia w Twoim cytowaniu, nie przydaje
się do wstawiania odręcznych uwag, za to uniemożliwia dalsze automatyczne
przeformatowanie tekstu tak, by zachować jego zalecaną szerokość przy
ponownym cytowaniu.

Podsumowując - Google Groups nie są najlepszym narzędziem do korzystania
z Usenetu, ale za prawie cały bałagan w tym wątku odpowiadasz Ty, a nie
ułomne narzędzie, z którego korzystasz.

W miarę aktualną wersję netykiety znajdziesz tu:
http://usenet.rox.pl/netykieta.html
Inne ciekawe materiały znajdziesz tu: http://evil.pl/pip/
--
Andrzej P. Woźniak ***@pochta.onet.pl (zamień miejscami z<->h w adresie)
Grand Inquisitor pl.internet.pomoc Trust No.1 http://evil.pl/pip/
o***@interia.pl
2013-03-05 22:18:14 UTC
Permalink
Post by Andrzej P. Wozniak
Post by o***@interia.pl
Post by Andrzej P. Wozniak
To nie jest forum trzymane na jednym serwerze, tylko grupa dyskusyjna
dostępna na setkach różnych serwerów. Cokolwiek usuwasz, usuwasz tylko
u siebie, wszystkie Twoje śmieci idą na cały świat.
Więc po co jest opcja "usuń"? I jaki ma sens w takim razie?
Post by Andrzej P. Wozniak
Post by o***@interia.pl
Ok. Postaram się zamieszczać uwagi i sprostowania, zamiast usuwać posty
z błędami.
Nie. Swój śmietnik trzymaj u siebie na dysku, a tu wysyłaj tylko przemyślane
wypowiedzi.
Staram się, ale nie potrafię unikać błędów.
Post by Andrzej P. Wozniak
1. Tocz dyskusję, czyli odpowiadaj bezpośrednio na wiadomość osoby
cytowanej, a nie swoją własną.
A co jeśli chcę się ustosunkować lub poprawić własną wypowiedź?
Post by Andrzej P. Wozniak
2. Wyraźnie zaznaczaj w tekście, komu i na co odpowiadasz i w jednej
wiadomości odpowiadaj w miarę możliwości tylko jednej osobie.
No tak, to słuszna uwaga. Jak do tej pory nie wiedziałem czy lepiej odpowiedzieć wszystkim w jednej wiadomości, czy każdemu z osobna w kilku wiadomościach.
Post by Andrzej P. Wozniak
Podsumowując - Google Groups nie są najlepszym narzędziem do korzystania
z Usenetu, ale za prawie cały bałagan w tym wątku odpowiadasz Ty, a nie
ułomne narzędzie, z którego korzystasz.
Dzięki za rady.
Post by Andrzej P. Wozniak
http://usenet.rox.pl/netykieta.html
Ta strona jest niedostępna.
Post by Andrzej P. Wozniak
Inne ciekawe materiały znajdziesz tu: http://evil.pl/pip/
Dobrze, poszukam tam czegoś ciekawego.
o***@interia.pl
2013-03-06 17:40:50 UTC
Permalink
Wracając do wątku, sprawdziłem jak zmieniają się czasy stopów dla kolejnych liczb parzystych od 3 do 10001. Tu znajduje się wykres:

Loading Image....html

Z tego co widzę, wydaje się, że jest to raczej zależność logarytmiczna. Gdyby była to jakaś zależność k*ln(d) (mam na myśli czasy stopów), to cały algorytm powinien mieć chyba złożoność nie większą niż s*log^2(d)?
bartekltg
2013-03-06 17:54:03 UTC
Permalink
Post by o***@interia.pl
Wracając do wątku, sprawdziłem jak zmieniają się czasy stopów dla
http://www.fotoszok.pl/show.php/1475743_obra.png.html
Z tego co widzę, wydaje się, że jest to raczej zależność
logarytmiczna. Gdyby była to jakaś zależność k*ln(d) (mam na myśli
czasy stopów), to cały algorytm powinien mieć chyba złożoność nie
większą niż s*log^2(d)?
A potwierdziła się hipoteza o związku czasu stopu z pierwszością,
pseudopierwszością?

BTW, mógłbyś tą hipotezę przypomnieć, w wersji ściśle zdefiniowanej.

pzdr
bartekltg
o***@interia.pl
2013-03-06 19:14:39 UTC
Permalink
Post by bartekltg
Post by o***@interia.pl
Wracając do wątku, sprawdziłem jak zmieniają się czasy stopów dla
http://www.fotoszok.pl/show.php/1475743_obra.png.html
Z tego co widzę, wydaje się, że jest to raczej zależność
logarytmiczna. Gdyby była to jakaś zależność k*ln(d) (mam na myśli
czasy stopów), to cały algorytm powinien mieć chyba złożoność nie
większą niż s*log^2(d)?
A potwierdziła się hipoteza o związku czasu stopu z pierwszością,
pseudopierwszością?
BTW, mógłbyś tą hipotezę przypomnieć, w wersji ściśle zdefiniowanej.
pzdr
bartekltg
Aby sprawdzić pierwszość lub pseudopierwszość (przy podstawie 2) jakiejś nieparzystej liczby "d" tworzymy funkcję:

f(x) = x/2 + d/2 gdy x nieparzyste
f(x) = x/2 - gdy x parzyste

i obliczamy ciąg dla x=1 dotąd aż się nie zapętli (tj. znów nie osiągnie liczby 1). Zapisujemy ilość iteracji "t" (inaczej czas stopu), po którym ciąg się zapętla. Hipoteza: jeżeli liczba "d" jest pierwsza lub pseudopierwsza, to "t" dzieli liczbę "d-1" (bez reszty) oraz jeżeli liczba "d" nie jest pierwsza, ani pseudopierwsza to "t" nie dzieli "d-1" bez reszty.

Potwierdziłem hipotezę jak na razie dla liczb do 10001.
bartekltg
2013-03-06 19:19:45 UTC
Permalink
Post by o***@interia.pl
Aby sprawdzić pierwszość lub pseudopierwszość (przy podstawie 2)
f(x) = x/2 + d/2 gdy x nieparzyste f(x) = x/2 - gdy x parzyste
i obliczamy ciąg dla x=1 dotąd aż się nie zapętli (tj. znów nie
osiągnie liczby 1). Zapisujemy ilość iteracji "t" (inaczej czas
stopu), po którym ciąg się zapętla.
No i to nie jest formalnie.
x=1 to krok pierwszy, czy zerowy?
d=15.

mamy ciąg
1
8
4
2
1

Ile wynosi t? 4 czy 5?
Post by o***@interia.pl
Hipoteza: jeżeli liczba "d" jest
pierwsza lub pseudopierwsza, to "t" dzieli liczbę "d-1" (bez reszty)
oraz jeżeli liczba "d" nie jest pierwsza, ani pseudopierwsza to "t"
nie dzieli "d-1" bez reszty.
Uwaga edycyjna, zapoznaj się z wyrażeniem
"wtedy i tylko wtedy".

BTW, jak liczba jest pierwsza, to jest też pseudopierwsza.

pzdr
bartekltg
o***@interia.pl
2013-03-06 19:27:16 UTC
Permalink
Post by bartekltg
Post by o***@interia.pl
Aby sprawdzić pierwszość lub pseudopierwszość (przy podstawie 2)
f(x) = x/2 + d/2 gdy x nieparzyste f(x) = x/2 - gdy x parzyste
i obliczamy ciąg dla x=1 dotąd aż się nie zapętli (tj. znów nie
osiągnie liczby 1). Zapisujemy ilość iteracji "t" (inaczej czas
stopu), po którym ciąg się zapętla.
No i to nie jest formalnie.
x=1 to krok pierwszy, czy zerowy?
d=15.
mamy ciąg
1
8
4
2
1
Ile wynosi t? 4 czy 5?
4. x=1 to zerowy krok.
Post by bartekltg
Post by o***@interia.pl
Hipoteza: jeżeli liczba "d" jest
pierwsza lub pseudopierwsza, to "t" dzieli liczbę "d-1" (bez reszty)
oraz jeżeli liczba "d" nie jest pierwsza, ani pseudopierwsza to "t"
nie dzieli "d-1" bez reszty.
Uwaga edycyjna, zapoznaj się z wyrażeniem
"wtedy i tylko wtedy".
No tak, można to napisać: "d" jest pierwsza lub pseudopierwsza, wtedy i tylko wtedy, gdy "t" dzieli liczbę "d-1" (bez reszty).
bartekltg
2013-03-06 21:55:34 UTC
Permalink
Post by o***@interia.pl
Post by bartekltg
Post by o***@interia.pl
Aby sprawdzić pierwszość lub pseudopierwszość (przy podstawie 2)
f(x) = x/2 + d/2 gdy x nieparzyste f(x) = x/2 - gdy x
parzyste
i obliczamy ciąg dla x=1 dotąd aż się nie zapętli (tj. znów nie
osiągnie liczby 1). Zapisujemy ilość iteracji "t" (inaczej czas
stopu), po którym ciąg się zapętla.
d=15.
mamy ciąg
1
8
4
2
1
Ile wynosi t? 4 czy 5?
4. x=1 to zerowy krok.
d=59. Jest pierwsza.

x0=1 /np
x1 = (1+59)/2=30 /p
x2 = 30/2=15 /np
x3 = (15+17)/2 = 16 /p
x4 = 16/2=8 /p
x5 = 8/2=4 /p
x6 = 4/2 = 2 /p
x7 = 2/2=1

t=7

a 7 nie dzieli 58=2*29

6,8 ani nic w okolicy też zresztą nie.
Post by o***@interia.pl
No tak, można to napisać: "d" jest pierwsza lub pseudopierwsza, wtedy
i tylko wtedy, gdy "t" dzieli liczbę "d-1" (bez reszty).
Coś nadal się nie zgadza. A pisałeś, że sprawdziłeś dla 10 tysięcy.

pzdr
bartekltg
bartekltg
2013-03-06 22:04:05 UTC
Permalink
Post by bartekltg
Post by o***@interia.pl
Post by bartekltg
Post by o***@interia.pl
Aby sprawdzić pierwszość lub pseudopierwszość (przy podstawie 2)
f(x) = x/2 + d/2 gdy x nieparzyste f(x) = x/2 - gdy x
parzyste
i obliczamy ciąg dla x=1 dotąd aż się nie zapętli (tj. znów nie
osiągnie liczby 1). Zapisujemy ilość iteracji "t" (inaczej czas
stopu), po którym ciąg się zapętla.
d=15.
mamy ciąg
1
8
4
2
1
Ile wynosi t? 4 czy 5?
4. x=1 to zerowy krok.
w sumie 4(jak i 3 oraz 5) też nie dzieli 14 = 15-1
:)
Post by bartekltg
d=59. Jest pierwsza.
x0=1 /np
x1 = (1+59)/2=30 /p
x2 = 30/2=15 /np
x3 = (15+17)/2 = 16 /p
x4 = 16/2=8 /p
x5 = 8/2=4 /p
x6 = 4/2 = 2 /p
x7 = 2/2=1
t=7
a 7 nie dzieli 58=2*29
6,8 ani nic w okolicy też zresztą nie.
Post by o***@interia.pl
No tak, można to napisać: "d" jest pierwsza lub pseudopierwsza, wtedy
i tylko wtedy, gdy "t" dzieli liczbę "d-1" (bez reszty).
Coś nadal się nie zgadza. A pisałeś, że sprawdziłeś dla 10 tysięcy.
pzdr
bartekltg
o***@interia.pl
2013-03-06 23:18:34 UTC
Permalink
Post by bartekltg
Post by bartekltg
W dniu środa, 6 marca 2013 20:19:45 UTC+1 użytkownik bartekltg
Post by bartekltg
Post by o***@interia.pl
Aby sprawdzić pierwszość lub pseudopierwszość (przy podstawie 2)
f(x) = x/2 + d/2 gdy x nieparzyste f(x) = x/2 - gdy x
parzyste
i obliczamy ciąg dla x=1 dotąd aż się nie zapętli (tj. znów nie
osiągnie liczby 1). Zapisujemy ilość iteracji "t" (inaczej czas
stopu), po którym ciąg się zapętla.
d=15.
mamy ciąg
1
8
4
2
1
Ile wynosi t? 4 czy 5?
4. x=1 to zerowy krok.
w sumie 4(jak i 3 oraz 5) też nie dzieli 14 = 15-1
:)
Post by bartekltg
d=59. Jest pierwsza.
x0=1 /np
x1 = (1+59)/2=30 /p
x2 = 30/2=15 /np
x3 = (15+17)/2 = 16 /p
x4 = 16/2=8 /p
x5 = 8/2=4 /p
x6 = 4/2 = 2 /p
x7 = 2/2=1
t=7
a 7 nie dzieli 58=2*29
To jest źle policzone. Już trzeci wyraz jest policzony niezgodnie z definicją funkcji. Mamy:

x0=1
x1=1/2+59/2=30
x2=30/2=15
x3=15/2+59/2=37
x4=37/2+59/2=48

i tak dalej. Ten ciąg wygląda tak:

1
30
15
37
48
24
12
6
3
31
45
52
26
13
36
18
9
34
17
38
19
39
49
54
27
43
51
55
57
58
29
44
22
11
35
47
53
56
28
14
7
33
46
23
41
50
25
42
21
40
20
10
5
32
16
8
4
2
1

Ciąg zapętla się po 58 krokach i 58 dzieli 59-1.
Post by bartekltg
Post by bartekltg
Coś nadal się nie zgadza. A pisałeś, że sprawdziłeś dla 10 tysięcy.
Gdy liczba jest nieparzysta f(x)=x/2+d/2, składnik d/2 nie zmienia się podczas obliczania kolejnych wyrazów ciągu, natomiast składnik x/2 zależy od poprzedniego wyrazu. Ty natomiast w x3 zamiast dodać 59/2, dodałeś 17/2.
bartekltg
2013-03-07 00:13:53 UTC
Permalink
Post by o***@interia.pl
Gdy liczba jest nieparzysta f(x)=x/2+d/2, składnik d/2 nie zmienia
się podczas obliczania kolejnych wyrazów ciągu, natomiast składnik
x/2 zależy od poprzedniego wyrazu. Ty natomiast w x3 zamiast dodać
59/2, dodałeś 17/2.
Aj, racja. 17 wzięła się z kartki z innego ciągu.


A przykład 15 zgadza się z tezą.


Chyba widzę głębszy związek i dowód. Ale to jutro.

pzdr
bartekltg
Oli
2013-03-07 00:27:30 UTC
Permalink
Widzę że jeszcze dalej walczysz z wiatrakami
Post by bartekltg
d=59. Jest pierwsza.
x0=1 /np
x1 = (1+59)/2=30 /p
x2 = 30/2=15 /np
x3 = (15+17)/2 = 16 /p
Tutaj to Ty popełniłeś błąd. Dlaczego +17 ??. Powinno być (15+59)/2 = 37
Post by bartekltg
x4 = 16/2=8 /p
x5 = 8/2=4 /p
x6 = 4/2 = 2 /p
x7 = 2/2=1
t=7
po poprawieniu x3 wychodzi t=58
i oczywiście (59-1) dzieli się przez 58

Dla największej liczby liczb pierwszych t=d-1, dla nieco mniejszej t =(d-1)/2
dl jeszcze mniejszej liczby liczb pierwszych t = (d-1)/3 itd

I teraz spróbuj tym 'rewelacyjnym' algorytmem udowodnić, że 1 000 003 jest liczbą pierwszą.
Ogólnie znanym algorytmem zajmuje to mniej niż 1 msec a tym algorytmem wymaga to 1 000 002 iteracji.
O większych liczbach zapomnijmy.

Przypomina mi to znany rysunek Mleczki z czasów PRLu z podpisem " co by tu jeszcze spieprzyć"
--
Oli
o***@interia.pl
2013-03-07 08:19:50 UTC
Permalink
Post by Oli
I teraz spróbuj tym 'rewelacyjnym' algorytmem udowodnić, że 1 000 003 jest liczbą pierwszą.
Ogólnie znanym algorytmem zajmuje to mniej niż 1 msec a tym algorytmem wymaga to 1 000 002 iteracji.
O większych liczbach zapomnijmy.
Fakt, funkcja wydaje się wymagać najwięcej iteracji do sprawdzenia właśnie liczb pierwszych. Ale nie wszystkie testowane liczby będą pierwsze, więc powinniśmy oszczędzać trochę iteracji przy liczbach złożonych.
bartekltg
2013-03-07 13:05:54 UTC
Permalink
Post by o***@interia.pl
Post by Oli
I teraz spróbuj tym 'rewelacyjnym' algorytmem udowodnić, że 1 000
003 jest liczbą pierwszą.
Ogólnie znanym algorytmem zajmuje to mniej niż 1 msec a tym
algorytmem wymaga to 1 000 002 iteracji.
O większych liczbach zapomnijmy.
Fakt, funkcja wydaje się wymagać najwięcej iteracji do sprawdzenia
właśnie liczb pierwszych. Ale nie wszystkie testowane liczby będą
pierwsze, więc powinniśmy oszczędzać trochę iteracji przy liczbach
złożonych.
Twoja procedura jest dokładnie tym, co sprawdzenie pseudopierwszości.
Obstawiam, że policzenie 2^(p-1) modulo p będzie szybsze.
Post by o***@interia.pl
Wracając do wątku, sprawdziłem jak zmieniają się czasy stopów dla
http://www.fotoszok.pl/show.php/1475743_obra.png.html
Z tego co widzę, wydaje się, że jest to raczej zależność
logarytmiczna.
Na moje oko to jest wyraźnie zestaw linii prostych,
a czerwona krzywa jest bez sensu:/

Widać nawet wyraźnie linię y=x!
Post by o***@interia.pl
Fakt, funkcja wydaje się wymagać najwięcej iteracji do sprawdzenia
właśnie liczb pierwszych. Ale nie wszystkie testowane liczby będą
pierwsze, więc powinniśmy oszczędzać trochę iteracji przy liczbach
złożonych.
No to sprawdźmy. Wszystkie liczby nieparzyste do miliona
i rysujemy wykres średniej kroczącej ze średnimi z 1000 punktów:
http://w207.wrzuta.pl/obraz/powieksz/9j6wvdfej8R
http://w207.wrzuta.pl/obraz/9j6wvdfej8R/srednia_kroczaca

Nie ma zmiłuj, średni koszt i tak jest liniowy, na oko ze
współczynnikiem 0.2. Regresja na nieuśrednionych danych
mówi 0.173. średnio jest ledwo 5 razy szybciej
niż pesymistycznie.


BTW, to nie jest poprawne oszacowanie, bo tylko przyłożyliśmy
linijkę do wykresu. A co się dzieje dalej?

Daje się to oszacować od góry. Liczba iteracji t to +-1
najmniejsza liczba k taka, że 2^k = 1 (mod d). Patrz rozwiązanie.

k <= lambda (d)
lambda - http://en.wikipedia.org/wiki/Carmichael_function
(definicja w pl.wiki trochę bełkotliwa:/)

W szczególności to:
http://en.wikipedia.org/wiki/Carmichael_function#Average_and_typical_value

Czyli w rzeczywistości jest trochę lepiej,
w dobrym przyliżeniu n/log[n]^niewielka_potega.

Niewiele to jednak zmienia, bo jest to
prawie liniowa, a jak dodamy bebechy algorytmu (log[n]
za operacja na liczbach) może wyjść i całkiem liniowe.


pzdr
bartekltg
bartekltg
2013-03-07 13:42:57 UTC
Permalink
BTW, to nie jest poprawne oszacowanie, bo tylko przyłożyliśmy linijkę
do wykresu. A co się dzieje dalej?
Daje się to oszacować od góry. Liczba iteracji t to +-1 najmniejsza
liczba k taka, że 2^k = 1 (mod d). Patrz rozwiązanie.
k <= lambda (d) lambda -
http://en.wikipedia.org/wiki/Carmichael_function (definicja w pl.wiki
trochę bełkotliwa:/)
http://en.wikipedia.org/wiki/Carmichael_function#Average_and_typical_value
Czyli w rzeczywistości jest trochę lepiej, w dobrym przyliżeniu
n/log[n]^niewielka_potega.
Okazuję się, że krążymy (w sporej odległości) wokoło
otwartego problemu matematyki/informatyki.

Najmniejsza liczba k, taka, że 2^k =1 mod (p) to logarytm dyskretny
z 2 w grupie (Z/dZ)*.
Twój algorytm na dobrą sprawę liczy ten logarytm
(co jest problemem trudniejszym niż sprawdzenie pseudopierwszości)
w sposób naiwny (tylko dzieli, nie mnoży przez 2)

Czy da się policzyć go sprawniej? Da. Czy da się go policzyć
w czasie wielomianowym względem długości liczby? Nie wiadomo!

http://en.wikipedia.org/wiki/Discrete_logarithm#Algorithms

Przejrzyj te algorytmy, zawierają wiele ciekawych pomysłów.


pzdr
bartekltg
o***@interia.pl
2013-03-07 19:38:02 UTC
Permalink
Post by bartekltg
BTW, to nie jest poprawne oszacowanie, bo tylko przyłożyliśmy linijkę
do wykresu. A co się dzieje dalej?
Daje się to oszacować od góry. Liczba iteracji t to +-1 najmniejsza
liczba k taka, że 2^k = 1 (mod d). Patrz rozwiązanie.
k <= lambda (d) lambda -
http://en.wikipedia.org/wiki/Carmichael_function (definicja w pl.wiki
trochę bełkotliwa:/)
http://en.wikipedia.org/wiki/Carmichael_function#Average_and_typical_value
Czyli w rzeczywistości jest trochę lepiej, w dobrym przyliżeniu
n/log[n]^niewielka_potega.
Okazuję się, że krążymy (w sporej odległości) wokoło
otwartego problemu matematyki/informatyki.
Najmniejsza liczba k, taka, że 2^k =1 mod (p) to logarytm dyskretny
z 2 w grupie (Z/dZ)*.
Twój algorytm na dobrą sprawę liczy ten logarytm
(co jest problemem trudniejszym niż sprawdzenie pseudopierwszości)
w sposób naiwny (tylko dzieli, nie mnoży przez 2)
Czy da się policzyć go sprawniej? Da. Czy da się go policzyć
w czasie wielomianowym względem długości liczby? Nie wiadomo!
Chodzi jak rozumiem o ustalenie najmniejszego wykładnika liczby 2^k-1, przy zadanym p, które ma dzielić tą liczbę? Faktycznie zaproponowana przeze mnie funkcja to liczy. Ogólnie można ją policzyć sprawniej dla niektórych przypadków. Na przykład jeżeli liczba p=d^n, przy czym d to liczba pierwsza o czasie stopu t. Wtedy k=d^(n-1)*t. Zatem, aby ustalić najmniejszą potęgę liczby 2^k-1 podzielnej przez d^n wystarczy policzyć tylko czas stopu liczby d (a nie całej liczby d^n). Przykład: znajdźmy liczbę 2^k-1 podzielną przez 13^13. Czas stopu liczby 13 to t=12. Zatem nasza liczba to 2^(12*13^12)-1.
o***@interia.pl
2013-03-08 05:16:14 UTC
Permalink
Post by bartekltg
Okazuję się, że krążymy (w sporej odległości) wokoło
otwartego problemu matematyki/informatyki.
Najmniejsza liczba k, taka, że 2^k =1 mod (p) to logarytm dyskretny
z 2 w grupie (Z/dZ)*.
Twój algorytm na dobrą sprawę liczy ten logarytm
(co jest problemem trudniejszym niż sprawdzenie pseudopierwszości)
w sposób naiwny (tylko dzieli, nie mnoży przez 2)
Czy da się policzyć go sprawniej? Da. Czy da się go policzyć
w czasie wielomianowym względem długości liczby? Nie wiadomo!
Jeszcze mam pytanie czy otwartym problemem jest to czy da się policzyć dowolny logarytm dyskretny w czasie wielomianowym, czy jakikolwiek? Czy do rozwiązania problemu wystarczy wykazać, że właśnie ten logarytm którym się zajmujemy można policzyć w czasie wielomianowym?
bartekltg
2013-03-08 10:04:33 UTC
Permalink
Post by o***@interia.pl
Post by bartekltg
Okazuję się, że krążymy (w sporej odległości) wokoło
otwartego problemu matematyki/informatyki.
Najmniejsza liczba k, taka, że 2^k =1 mod (p) to logarytm
dyskretny
z 2 w grupie (Z/dZ)*.
Twój algorytm na dobrą sprawę liczy ten logarytm
(co jest problemem trudniejszym niż sprawdzenie pseudopierwszości)
w sposób naiwny (tylko dzieli, nie mnoży przez 2)
Czy da się policzyć go sprawniej? Da. Czy da się go policzyć
w czasie wielomianowym względem długości liczby? Nie wiadomo!
Jeszcze mam pytanie czy otwartym problemem jest to czy da się
policzyć dowolny logarytm dyskretny w czasie wielomianowym, czy
jakikolwiek?
Każdy. Pytanie jest o uniwersalny algorytm i jego
pesymistyczną (nawet nie średnią) złożoność.
Post by o***@interia.pl
Czy do rozwiązania problemu wystarczy wykazać, że
właśnie ten logarytm którym się zajmujemy można policzyć w czasie
wielomianowym?
Wystarczyłoby, ale już dawno wiadomo, że ten algorytm
nie jest wielomianowy. Jest wykładniczy (istnieją dowolnie
duże liczby d, dla których musisz zrobić d-1 kroków)
w sensie pesymistycznym.

Czytaj linki:

http://en.wikipedia.org/wiki/Discrete_logarithm#Algorithms

Twój algorytm jest równoważny temu nazwanemu 'trywialnym'
'trial multiplication'. A on jest pesymistycznie po prostu
wykładniczy. Następnie masz całą listę
algorytmów _szybszych_, ale nadal niewielomianowych.

pzdr
bartekltg
o***@interia.pl
2013-03-08 12:43:46 UTC
Permalink
Post by bartekltg
Post by o***@interia.pl
Post by bartekltg
Okazuję się, że krążymy (w sporej odległości) wokoło
otwartego problemu matematyki/informatyki.
Najmniejsza liczba k, taka, że 2^k =1 mod (p) to logarytm
dyskretny
z 2 w grupie (Z/dZ)*.
Twój algorytm na dobrą sprawę liczy ten logarytm
(co jest problemem trudniejszym niż sprawdzenie pseudopierwszości)
w sposób naiwny (tylko dzieli, nie mnoży przez 2)
Czy da się policzyć go sprawniej? Da. Czy da się go policzyć
w czasie wielomianowym względem długości liczby? Nie wiadomo!
Jeszcze mam pytanie czy otwartym problemem jest to czy da się
policzyć dowolny logarytm dyskretny w czasie wielomianowym, czy
jakikolwiek?
Każdy. Pytanie jest o uniwersalny algorytm i jego
pesymistyczną (nawet nie średnią) złożoność.
Post by o***@interia.pl
Czy do rozwiązania problemu wystarczy wykazać, że
właśnie ten logarytm którym się zajmujemy można policzyć w czasie
wielomianowym?
Wystarczyłoby,
wydają się wykluczać. To w końcu pytanie jest o algorytm uniwersalny który rozwiąże problem g^x=h (mod n), gdzie g, h i n są dane (a np. niektóre szczególne przypadki potrafimy obliczać w czasie wielomianowym oraz wskazanie jednego szczególnego przypadku nie urządza nas), czy może o znalezienie chociaż jednego szczególnego zestawu, np. 2^k=1 (mod d) który będziemy potrafili obliczać wielomianowo?
Post by bartekltg
ale już dawno wiadomo, że ten algorytm
nie jest wielomianowy. Jest wykładniczy (istnieją dowolnie
duże liczby d, dla których musisz zrobić d-1 kroków)
w sensie pesymistycznym.
Ogólnie przypatrzyłem się czasom stopów i dochodzę do wniosku, że zachodzą następujące własności. Liczba a_1^(n_1)*a_2^(n_2)*...*a_n(^n_n) ma czas stopu (liczba jest zapisana w oparciu o czynniki pierwsze):

a_1^(n_1-1)*a_2^(n_2-1)*...*a_n^(n_n-1)*x

przy czym x to czas stopu liczby a_1*a_2*...*a_n pozbawiony czynników a_1^(n_1-1), a_2^(n_2-1), ..., a_n^(n_n-1) (o ile takie ma).

Natomiast dowolna złożona liczba a_1*a_2*...*a_n ma czas stopu będący iloczynem najwyższych potęg różnych liczb które występują w czasach stopów tych liczb. Np. liczba 13 ma t=12=4*3, a liczba 17 ma t=8. Najwyższa potęga dwójki w tych czasach to 8, a trójki 3, dla liczby 13*17 mamy zatem czas stopu 3*8=24.

3*5*7*11*13*17*19 ma czas stopu 360, ponieważ:

3 ma czas 2
5 ma czas 4
7 ma czas 3
11 ma czas 10 --> 5
13 ma czas 12
17 ma czas 8 --> 8
19 ma czas 18 --> 9

najwyższe potęgi jakie znaleźliśmy to 8,9,5, mamy zatem 8*9*5=360.

Z kolei liczba 3*5^2*7^3*11^4 ma czas stopu 3913140. Wstępnie mamy dla niej czas stopu 5*7^2*11^3*x. Wyznaczamy t dla kolejnych liczb:

3 -> t=2
5 -> t=4
7 -> t=3
11 -> t=10

Najwyższa potęga dwójki wśród tych czasów to 4, trójki to 3 oraz piątki to 5, innych nie ma. Wstępnie zatem mamy 4*3*5, jednak wyrzucamy piątkę ponieważ występuje we wcześniejszym wzorze. Ostatecznie mamy czas stopu równy 5*7^2*11^3*4*3=3913140. Ogólnie wykonaliśmy 19 iteracji, zamiast 3913140.

Inny przykład:

11^4*19^2

Wstępnie mamy: 11^3*19*t.

11 -> 10
19 -> 18

Najwyższe potęgi to 2,9,5. Żadna nie występuje we wzorze wyżej, mamy zatem czas stopu 11^3*19*2*9*5=2276010. Ogólnie wykonaliśmy 28 iteracji zamiast 2276010.

Generalnie, aby sprawdzić czas stopu dowolnej liczby a_1^(n_1)*a_2^(n_2)*...*a_n(^n_n), należy wykonać co najwyżej a_1+a_2+...+a_n iteracji (w praktyce mniej, bo liczby pierwsze mają także czasy stopów mniejsze niż one same) no i doliczyć do tego operacje na czasach stopów tych liczb (rozbicie na czynniki pierwsze, znalezienie najwyższych potęg oraz odrzucanie niektórych czynników). Ten algorytm pozwala drastycznie obniżyć złożoność podczas testowania liczb "d" o odpowiednio "dużej" złożoności. Natomiast będzie miał problem z testowaniem pojedynczych liczb pierwszych lub liczb w ogóle o niewielu dużych czynnikach pierwszych. Czy zasługuje na miano działającego w czasie wielomianowym?
bartekltg
2013-03-08 13:03:34 UTC
Permalink
Post by o***@interia.pl
Post by bartekltg
Post by o***@interia.pl
Czy do rozwiązania problemu wystarczy wykazać, że
właśnie ten logarytm którym się zajmujemy można policzyć w czasie
wielomianowym?
Wystarczyłoby,
wydają się wykluczać. To w końcu pytanie jest o algorytm uniwersalny
który rozwiąże problem g^x=h (mod n), gdzie g, h i n są dane (a np.
niektóre szczególne przypadki potrafimy obliczać w czasie
wielomianowym oraz wskazanie jednego szczególnego przypadku nie
urządza nas), czy może o znalezienie chociaż jednego szczególnego
zestawu, np. 2^k=1 (mod d) który będziemy potrafili obliczać
wielomianowo?
Twój algorytm to nic innego jak liczenie kolejnych potęg 2.
Ma taką samą złożoność. Bez trudu uogolniasz go na liczenie
potęg 3, 4 i 777;)
Jeśli działałyby w czasie logarytmicznym, to problemu by nie było.

Ale nie działają. To podobne stwierdzeni jak 'jeśli liczb pierwszych
byłoby logarytmicznie mało i istniał ciąg je generujący, czy dałoby
się szybko faktoryzować duże liczby?'
Tak, _wtedy_ by się dało. Ale tak nie jest!
Post by o***@interia.pl
Generalnie, aby sprawdzić czas stopu dowolnej liczby
a_1^(n_1)*a_2^(n_2)*...*a_n(^n_n), należy wykonać co najwyżej
a_1+a_2+...+a_n iteracji (w praktyce mniej, bo liczby pierwsze mają
także czasy stopów mniejsze niż one same) no i doliczyć do tego
operacje na czasach stopów tych liczb (rozbicie na czynniki pierwsze,
znalezienie najwyższych potęg oraz odrzucanie niektórych czynników).
Przejrzałeś te linki, które podsyłałem? Ja je nie wysyłam dlatego, że
ładnie wyglądają niebieskie literki w poście, ale dlatego, że tam są
opisane rzeczy powiązane z Twoimi problemami:)

Krążysz wokół jednego z opisanych algorytmów dla logarytmu dyskretnego.
http://pl.wikipedia.org/wiki/Redukcja_Pohliga-Hellmana

Metoda jest zła, poza pewną klasą liczb (liczbami gładkimi)
bo rozkład na czynniki pierwsze nie jest wielomianowy.
Post by o***@interia.pl
Ten algorytm pozwala drastycznie obniżyć złożoność podczas testowania
liczb "d" o odpowiednio "dużej" złożoności. Natomiast będzie miał
problem z testowaniem pojedynczych liczb pierwszych lub liczb w ogóle
o niewielu dużych czynnikach pierwszych. Czy zasługuje na miano
działającego w czasie wielomianowym?
Nie.

pzdr
bartekltg
o***@interia.pl
2013-03-09 08:27:11 UTC
Permalink
Post by bartekltg
W dniu piątek, 8 marca 2013 11:04:33 UTC+1 użytkownik bartekltg
Post by bartekltg
Post by o***@interia.pl
Czy do rozwiązania problemu wystarczy wykazać, że
właśnie ten logarytm którym się zajmujemy można policzyć w
czasie
wielomianowym?
Wystarczyłoby,
wydają się wykluczać. To w końcu pytanie jest o algorytm uniwersalny
który rozwiąże problem g^x=h (mod n), gdzie g, h i n są dane (a np.
niektóre szczególne przypadki potrafimy obliczać w czasie
wielomianowym oraz wskazanie jednego szczególnego przypadku nie
urządza nas), czy może o znalezienie chociaż jednego szczególnego
zestawu, np. 2^k=1 (mod d) który będziemy potrafili obliczać
wielomianowo?
Twój algorytm to nic innego jak liczenie kolejnych potęg 2.
Ma taką samą złożoność. Bez trudu uogolniasz go na liczenie
potęg 3, 4 i 777;)
Jeśli działałyby w czasie logarytmicznym, to problemu by nie było.
Ale nie działają. To podobne stwierdzeni jak 'jeśli liczb pierwszych
byłoby logarytmicznie mało i istniał ciąg je generujący, czy dałoby
się szybko faktoryzować duże liczby?'
Tak, _wtedy_ by się dało. Ale tak nie jest!
Generalnie, aby sprawdzić czas stopu dowolnej liczby
a_1^(n_1)*a_2^(n_2)*...*a_n(^n_n), należy wykonać co najwyżej
a_1+a_2+...+a_n iteracji (w praktyce mniej, bo liczby pierwsze mają
także czasy stopów mniejsze niż one same) no i doliczyć do tego
operacje na czasach stopów tych liczb (rozbicie na czynniki pierwsze,
znalezienie najwyższych potęg oraz odrzucanie niektórych czynników).
Przejrzałeś te linki, które podsyłałem? Ja je nie wysyłam dlatego, że
ładnie wyglądają niebieskie literki w poście, ale dlatego, że tam są
opisane rzeczy powiązane z Twoimi problemami:)
No tak przejrzałem niektóre algorytmy, jeszcze nie wszystkie.
Post by bartekltg
Krążysz wokół jednego z opisanych algorytmów dla logarytmu dyskretnego.
http://pl.wikipedia.org/wiki/Redukcja_Pohliga-Hellman
Ten algorytm działa właśnie dobrze dla liczb gładkich. Dla liczb B-gładkich ma złożoność O(b^0.5). Podobnie działa ten mój algorytm (pomijając, że dotyczy tylko liczb Mersenne'a). Nie jestem pewien który byłby szybszy.
Post by bartekltg
Metoda jest zła, poza pewną klasą liczb (liczbami gładkimi)
bo rozkład na czynniki pierwsze nie jest wielomianowy.
No tak, właśnie zauważyłem.
bartekltg
2013-03-09 15:02:25 UTC
Permalink
Post by o***@interia.pl
Post by bartekltg
Krążysz wokół jednego z opisanych algorytmów dla logarytmu dyskretnego.
http://pl.wikipedia.org/wiki/Redukcja_Pohliga-Hellman
Ten algorytm działa właśnie dobrze dla liczb gładkich. Dla liczb
B-gładkich ma złożoność O(b^0.5). Podobnie działa ten mój algorytm
(pomijając, że dotyczy tylko liczb Mersenne'a). Nie jestem pewien
który byłby szybszy.
Nie widzę żadnego związku miedzy tematami poruszanymi w tym wątku
a liczbami Mersenne'a.

pzdr
bartekltg
o***@interia.pl
2013-03-09 15:12:11 UTC
Permalink
Post by bartekltg
Post by o***@interia.pl
Post by bartekltg
Krążysz wokół jednego z opisanych algorytmów dla logarytmu
dyskretnego.
http://pl.wikipedia.org/wiki/Redukcja_Pohliga-Hellman
Ten algorytm działa właśnie dobrze dla liczb gładkich. Dla liczb
B-gładkich ma złożoność O(b^0.5). Podobnie działa ten mój algorytm
(pomijając, że dotyczy tylko liczb Mersenne'a). Nie jestem pewien
który byłby szybszy.
Nie widzę żadnego związku miedzy tematami poruszanymi w tym wątku
a liczbami Mersenne'a.
Czas stopu tej funkcji przy danym "d" to najmniejszy wykładnik liczby Mersenne'a podzielnej przez d. Np. liczba 13 ma czas stopu 12, więc najmniejsza liczba Mersenne'a podzielna przez 13 to 2^12-1.
o***@interia.pl
2013-03-07 19:10:46 UTC
Permalink
Post by bartekltg
Post by o***@interia.pl
Post by Oli
I teraz spróbuj tym 'rewelacyjnym' algorytmem udowodnić, że 1 000
003 jest liczbą pierwszą.
Ogólnie znanym algorytmem zajmuje to mniej niż 1 msec a tym
algorytmem wymaga to 1 000 002 iteracji.
O większych liczbach zapomnijmy.
Fakt, funkcja wydaje się wymagać najwięcej iteracji do sprawdzenia
właśnie liczb pierwszych. Ale nie wszystkie testowane liczby będą
pierwsze, więc powinniśmy oszczędzać trochę iteracji przy liczbach
złożonych.
Twoja procedura jest dokładnie tym, co sprawdzenie pseudopierwszości.
Obstawiam, że policzenie 2^(p-1) modulo p będzie szybsze.
Post by o***@interia.pl
Wracając do wątku, sprawdziłem jak zmieniają się czasy stopów dla
http://www.fotoszok.pl/show.php/1475743_obra.png.html
Z tego co widzę, wydaje się, że jest to raczej zależność
logarytmiczna.
Na moje oko to jest wyraźnie zestaw linii prostych,
Tak to wygląda, ale zagęszczenie tych linii jest większe na dole i coraz mniejsze wyżej. Usiłuję skonstruować szacunkowy heurystyczny wzór opisujący regresję tych czasów stopów. Prawie na pewno można udowodnić (będę musiał poświęcić temu kiedyś przy okazji chwilę czasu, bo już kiedyś udowadniałem podobną rzecz), że ciągi zadane naszą funkcją dla kolejnych liczb nieparzystych zachowują się jak quasi-losowe. To znaczy, że gdy wypiszemy sobie kolejne 2^n dwuwartościowych wektorów przekształceń o długościach "n" (mnożenie z dodawaniem - 1 lub dzielenie - 0) dla kolejnych ciągów (przy okazji ucinając zerową i pierwszą iterację - bo zawsze są takie same), to dostaniemy wszystkie możliwe kombinacje takich wektorów. Inaczej pisząc każda liczba nieparzysta wśród kolejnych liczb od 1 do 2^2n-1 zadaje inną n-elementową kombinację przekształceń. Można by zatem przyjąć, że średnio każda liczba jest raz mnożona (z dodawaniem) i raz dzielona przez 2. Tworząc na tej podstawie odpowiednie równanie i logarytmując względem ilości iteracji można szacować po jakim czasie dana liczba zbiegnie do 1. Niestety po obliczeniu wzoru wychodzą mi wartości urojone.

Kolejne iteracje zakładając ich właśnie taką trywialną strukturę można opisać jako na przemian mnożenie z dodawaniem i dzielenie. Ponieważ pomijamy dwie pierwsze iteracje, iterację pierwszą traktujemy jako zerową. Oznacza to, że badając ciąg liczby y zaczynamy iteracje od (y+1)/2. Lub inaczej badając ciąg jakiejś liczby x, w rzeczywistości odnosimy się do ciągu liczby 2x-1 (ta liczba też definiuje nam funkcję którą bierzemy do obliczenia ciągu począwszy od x). Kolejne 2 i 4 iteracje wyglądają zatem następująco:

x/2+(2x-1)/2

((x/2+(2x-1)/2)/2+(2x-1)/2)/2

itd.

ogólnie dla 2i iteracji mamy:

x/4^i + (2x-1)*sum_(k=1)^(i) 1/4^k

przy okazji:

sum_(k=1)^(i) 1/4^k = 1/3*(1-1/4^i)

dalej zapisujemy równanie, przyrównując uzyskany wynik po 2i iteracjach do jedynki (bo ciąg ma zbiegać do 1):

x/4^i + (2x-1)*1/3*(1-1/4^i) = 1

obliczamy i:

i=ln((-x-1)/(2*(x-2)))/ln(4)

mnożymy wzór jeszcze tylko razy 2, ponieważ jeden krok, to u nas dwa kroki (mnożenie i dzielenie):

i=2*ln((-x-1)/(2*(x-2)))/ln(4)

niestety wzór jak widać przyjmuje dla dużych x wartości urojone, czyli jest bezużyteczny. Wydaje się sugerować, że kolejne x nie zbiegają, kiedy zbiegają. Nie wiem gdzie popełniam błąd (jeżeli popełniam). A może w ogóle nie da się tego oszacować w taki trywialny sposób
Post by bartekltg
a czerwona krzywa jest bez sensu:/
To krzywa logarytmicznej regresji.
Post by bartekltg
Widać nawet wyraźnie linię y=x!
No tak, ale mimo wszystko większość czasów stopów znajduje się poniżej.
Post by bartekltg
Post by o***@interia.pl
Fakt, funkcja wydaje się wymagać najwięcej iteracji do sprawdzenia
właśnie liczb pierwszych. Ale nie wszystkie testowane liczby będą
pierwsze, więc powinniśmy oszczędzać trochę iteracji przy liczbach
złożonych.
No to sprawdźmy. Wszystkie liczby nieparzyste do miliona
http://w207.wrzuta.pl/obraz/powieksz/9j6wvdfej8R
http://w207.wrzuta.pl/obraz/9j6wvdfej8R/srednia_kroczaca
Nie ma zmiłuj, średni koszt i tak jest liniowy, na oko ze
współczynnikiem 0.2. Regresja na nieuśrednionych danych
mówi 0.173. średnio jest ledwo 5 razy szybciej
niż pesymistycznie.
To jest średnia krocząca czasów stopów kolejnych liczb?

Ja mam tu:

Loading Image....html

kolejne średnie czasy stopów liczb do 10001 z liniową krzywą regresji. Z wykresu wynika, że średnio czas stopu liczby n, to 0,25*n.


Odnośnie rozwiązania, to za jakiś czas to przeanalizuję i może będę miał kilka pytań. Wygląda raczej poprawnie, ale z tego co zauważyłem nie mówi ono nic o czasach stopów.
bartekltg
2013-03-07 19:58:52 UTC
Permalink
Post by o***@interia.pl
Post by bartekltg
Post by o***@interia.pl
Post by Oli
I teraz spróbuj tym 'rewelacyjnym' algorytmem udowodnić, że 1 000
003 jest liczbą pierwszą.
Ogólnie znanym algorytmem zajmuje to mniej niż 1 msec a tym
algorytmem wymaga to 1 000 002 iteracji.
O większych liczbach zapomnijmy.
Fakt, funkcja wydaje się wymagać najwięcej iteracji do
sprawdzenia
właśnie liczb pierwszych. Ale nie wszystkie testowane liczby będą
pierwsze, więc powinniśmy oszczędzać trochę iteracji przy liczbach
złożonych.
Twoja procedura jest dokładnie tym, co sprawdzenie
pseudopierwszości.
Obstawiam, że policzenie 2^(p-1) modulo p będzie szybsze.
Post by o***@interia.pl
Wracając do wątku, sprawdziłem jak zmieniają się czasy stopów dla
kolejnych liczb parzystych od 3 do 10001. Tu znajduje się
http://www.fotoszok.pl/show.php/1475743_obra.png.html
Z tego co widzę, wydaje się, że jest to raczej zależność
logarytmiczna.
Na moje oko to jest wyraźnie zestaw linii prostych,
Tak to wygląda, ale zagęszczenie tych linii jest większe na dole i
coraz mniejsze wyżej.
Nie, nie jest! Przecież dostałeś wykres średniej kroczącej.
Post by o***@interia.pl
Usiłuję skonstruować szacunkowy heurystyczny
wzór opisujący regresję tych czasów stopów. Prawie na pewno można
A co nie podoba Ci się w oszacowaniu d/log(d)^k ?
Post by o***@interia.pl
udowodnić (będę musiał poświęcić temu kiedyś przy okazji chwilę
czasu, bo już kiedyś udowadniałem podobną rzecz), że ciągi zadane
naszą funkcją dla kolejnych liczb nieparzystych zachowują się jak
quasi-losowe. To znaczy, że gdy wypiszemy sobie kolejne 2^n
dwuwartościowych wektorów przekształceń o długościach "n" (mnożenie z
dodawaniem - 1 lub dzielenie - 0) dla kolejnych ciągów (przy okazji
ucinając zerową i pierwszą iterację - bo zawsze są takie same), to
dostaniemy wszystkie możliwe kombinacje takich wektorów. Inaczej
pisząc każda liczba nieparzysta wśród kolejnych liczb od 1 do 2^2n-1
zadaje inną n-elementową kombinację przekształceń. Można by zatem
przyjąć, że średnio każda liczba jest raz mnożona (z dodawaniem) i
raz dzielona przez 2. Tworząc na tej podstawie odpowiednie równanie i
logarytmując względem ilości iteracji można szacować po jakim czasie
dana liczba zbiegnie do 1. Niestety po obliczeniu wzoru wychodzą mi
wartości urojone.
Nie łapię tego rozumowania.

Eksperyment zapuszczony dla 100 000 000 pokazał przyzwoitą zgodność
średniej kroczącej*) momentu stopu ze wzorek n/log[n].

*) dokładniej to były podprzedziały po 1000 liczb brane równomiernie
z przedziału do 100 000 000.

http://pastebin.com/dxK8PeXJ [wykres wychodzi podobny jak poprzednio]
Post by o***@interia.pl
Kolejne iteracje zakładając ich właśnie taką trywialną strukturę
można opisać jako na przemian mnożenie z dodawaniem i dzielenie.
A czemu nie skorzystasz z jak sie okazało równoważnego sformułowania,
czyli mnożenia przez 2 modulo d? Okres jest ten sam. To nawet
ten sam ciąg, tylko od tyłu.
Post by o***@interia.pl
Nie wiem gdzie popełniam błąd (jeżeli
popełniam). A może w ogóle nie da się tego oszacować w taki trywialny
sposób
Popełniłeś, siły nie ma.
Jak to szacować od góry już napisałem.
Post by o***@interia.pl
Post by bartekltg
a czerwona krzywa jest bez sensu:/
To krzywa logarytmicznej regresji.
Tak, i jest bez sensu! Wystarczy wygładzić dane i to widać.

Zresztą, mozesz sprawdzić. Dopasuj krzywą logarytmiczną
i dopasuj prostą. Następnie porównaj sumy kwadratów błędów.
Która krzywa lepiej pasuje do danych?
Post by o***@interia.pl
Post by bartekltg
No to sprawdźmy. Wszystkie liczby nieparzyste do miliona
http://w207.wrzuta.pl/obraz/powieksz/9j6wvdfej8R
http://w207.wrzuta.pl/obraz/9j6wvdfej8R/srednia_kroczaca
Nie ma zmiłuj, średni koszt i tak jest liniowy, na oko ze
współczynnikiem 0.2. Regresja na nieuśrednionych danych
mówi 0.173. średnio jest ledwo 5 razy szybciej
niż pesymistycznie.
To jest średnia krocząca czasów stopów kolejnych liczb?
Z grubsza. Tak naprawdę to była tabelka wyników i uśredniłem
każdą kolejną n-kę (już nie pemiętam, czy 100, czy 1000).
Post by o***@interia.pl
http://www.fotoszok.pl/show.php/1477823_obr1.png.html
kolejne średnie czasy stopów liczb do 10001 z liniową krzywą
regresji. Z wykresu wynika, że średnio czas stopu liczby n, to
0,25*n.
Co to znaczy średnie czasy stopów liczb?
Nie jestem pewien, po czym uśredniałeś. Miałeś uśredniać
po kolejnych liczbach, wygłazając wykres.
Post by o***@interia.pl
Odnośnie rozwiązania, to za jakiś czas to przeanalizuję i może będę
miał kilka pytań. Wygląda raczej poprawnie, ale z tego co zauważyłem
nie mówi ono nic o czasach stopów.
Udowadnia Twoją hipotezę. Bez tego właściwie nie było co dyskutować;)

pzdr
bartekltg
o***@interia.pl
2013-03-07 20:32:19 UTC
Permalink
Post by bartekltg
W dniu czwartek, 7 marca 2013 14:05:54 UTC+1 użytkownik bartekltg
Post by bartekltg
Post by o***@interia.pl
Post by Oli
I teraz spróbuj tym 'rewelacyjnym' algorytmem udowodnić, że 1
000
003 jest liczbą pierwszą.
Ogólnie znanym algorytmem zajmuje to mniej niż 1 msec a tym
algorytmem wymaga to 1 000 002 iteracji.
O większych liczbach zapomnijmy.
Fakt, funkcja wydaje się wymagać najwięcej iteracji do
sprawdzenia
właśnie liczb pierwszych. Ale nie wszystkie testowane liczby
będą
pierwsze, więc powinniśmy oszczędzać trochę iteracji przy
liczbach
złożonych.
Twoja procedura jest dokładnie tym, co sprawdzenie
pseudopierwszości.
Obstawiam, że policzenie 2^(p-1) modulo p będzie szybsze.
Post by o***@interia.pl
Wracając do wątku, sprawdziłem jak zmieniają się czasy stopów
dla
kolejnych liczb parzystych od 3 do 10001. Tu znajduje się
http://www.fotoszok.pl/show.php/1475743_obra.png.html
Z tego co widzę, wydaje się, że jest to raczej zależność
logarytmiczna.
Na moje oko to jest wyraźnie zestaw linii prostych,
Tak to wygląda, ale zagęszczenie tych linii jest większe na dole i
coraz mniejsze wyżej.
Nie, nie jest! Przecież dostałeś wykres średniej kroczącej.
Usiłuję skonstruować szacunkowy heurystyczny
wzór opisujący regresję tych czasów stopów. Prawie na pewno można
A co nie podoba Ci się w oszacowaniu d/log(d)^k ?
udowodnić (będę musiał poświęcić temu kiedyś przy okazji chwilę
czasu, bo już kiedyś udowadniałem podobną rzecz), że ciągi zadane
naszą funkcją dla kolejnych liczb nieparzystych zachowują się jak
quasi-losowe. To znaczy, że gdy wypiszemy sobie kolejne 2^n
dwuwartościowych wektorów przekształceń o długościach "n" (mnożenie z
dodawaniem - 1 lub dzielenie - 0) dla kolejnych ciągów (przy okazji
ucinając zerową i pierwszą iterację - bo zawsze są takie same), to
dostaniemy wszystkie możliwe kombinacje takich wektorów. Inaczej
pisząc każda liczba nieparzysta wśród kolejnych liczb od 1 do 2^2n-1
zadaje inną n-elementową kombinację przekształceń. Można by zatem
przyjąć, że średnio każda liczba jest raz mnożona (z dodawaniem) i
raz dzielona przez 2. Tworząc na tej podstawie odpowiednie równanie i
logarytmując względem ilości iteracji można szacować po jakim czasie
dana liczba zbiegnie do 1. Niestety po obliczeniu wzoru wychodzą mi
wartości urojone.
Nie łapię tego rozumowania.
Eksperyment zapuszczony dla 100 000 000 pokazał przyzwoitą zgodność
średniej kroczącej*) momentu stopu ze wzorek n/log[n].
*) dokładniej to były podprzedziały po 1000 liczb brane równomiernie
z przedziału do 100 000 000.
http://pastebin.com/dxK8PeXJ [wykres wychodzi podobny jak poprzednio]
Kolejne iteracje zakładając ich właśnie taką trywialną strukturę
można opisać jako na przemian mnożenie z dodawaniem i dzielenie.
A czemu nie skorzystasz z jak sie okazało równoważnego sformułowania,
czyli mnożenia przez 2 modulo d? Okres jest ten sam. To nawet
ten sam ciąg, tylko od tyłu.
Nie wiem gdzie popełniam błąd (jeżeli
popełniam). A może w ogóle nie da się tego oszacować w taki trywialny
sposób
Popełniłeś, siły nie ma.
Jak to szacować od góry już napisałem.
Post by bartekltg
a czerwona krzywa jest bez sensu:/
To krzywa logarytmicznej regresji.
Tak, i jest bez sensu! Wystarczy wygładzić dane i to widać.
Zresztą, mozesz sprawdzić. Dopasuj krzywą logarytmiczną
i dopasuj prostą. Następnie porównaj sumy kwadratów błędów.
Która krzywa lepiej pasuje do danych?
Post by bartekltg
No to sprawdźmy. Wszystkie liczby nieparzyste do miliona
http://w207.wrzuta.pl/obraz/powieksz/9j6wvdfej8R
http://w207.wrzuta.pl/obraz/9j6wvdfej8R/srednia_kroczaca
Nie ma zmiłuj, średni koszt i tak jest liniowy, na oko ze
współczynnikiem 0.2. Regresja na nieuśrednionych danych
mówi 0.173. średnio jest ledwo 5 razy szybciej
niż pesymistycznie.
To jest średnia krocząca czasów stopów kolejnych liczb?
Z grubsza. Tak naprawdę to była tabelka wyników i uśredniłem
każdą kolejną n-kę (już nie pemiętam, czy 100, czy 1000).
http://www.fotoszok.pl/show.php/1477823_obr1.png.html
kolejne średnie czasy stopów liczb do 10001 z liniową krzywą
regresji. Z wykresu wynika, że średnio czas stopu liczby n, to
0,25*n.
Co to znaczy średnie czasy stopów liczb?
Nie jestem pewien, po czym uśredniałeś. Miałeś uśredniać
po kolejnych liczbach, wygłazając wykres.
Są to sumy czasów stopów dzielone przez ilość składników sumy. Ogólnie jednak te i inne argumenty wskazują, że faktycznie, że czasy stopów nie zmieniają logarytmiczne (czym jestem raczej zdziwiony, bo spodziewałem się czegoś innego), co także dyskwalifikuje potencjał algorytmu pod względem poszukiwania dużych liczb pierwszych. Ale będę nadal badał tą funkcję w celu znajdowania różnych własności, które mogą pozwolić np. na szybkie znajdowanie wykładników liczb Mersenne'a podzielnych przez zadaną liczbę.
Miroslaw Kwasniak
2013-03-08 08:06:17 UTC
Permalink
Post by bartekltg
Post by o***@interia.pl
Fakt, funkcja wydaje się wymagać najwięcej iteracji do sprawdzenia
właśnie liczb pierwszych. Ale nie wszystkie testowane liczby będą
pierwsze, więc powinniśmy oszczędzać trochę iteracji przy liczbach
złożonych.
Twoja procedura jest dokładnie tym, co sprawdzenie pseudopierwszości.
Obstawiam, że policzenie 2^(p-1) modulo p będzie szybsze.
Potwierdzam, dla d<=200001 w pari 20 minut vs. 0,153 sekundy
Miroslaw Kwasniak
2013-03-08 08:01:35 UTC
Permalink
Post by o***@interia.pl
Post by Oli
I teraz spróbuj tym 'rewelacyjnym' algorytmem udowodnić, że 1 000 003 jest liczbą pierwszą.
Ogólnie znanym algorytmem zajmuje to mniej niż 1 msec a tym algorytmem wymaga to 1 000 002 iteracji.
O większych liczbach zapomnijmy.
Fakt, funkcja wydaje się wymagać najwięcej iteracji do sprawdzenia właśnie
liczb pierwszych. Ale nie wszystkie testowane liczby będą pierwsze, więc
powinniśmy oszczędzać trochę iteracji przy liczbach złożonych.
Trochę to jest eufemizm, przy ilości kroków O(d) :(

Twoja metoda do d<=2000001 zajmuje mi w pari 20 minut, a funkcja nextprime
generuje liczby pierwsze w zakresie 1000x większym krócej niż 1 minutę:

n=1;p=3;while(p<200000000,p=nextprime(p+1);n+=1);n
time = 47,294 ms.
%70 = 11078937
o***@interia.pl
2013-03-08 08:27:37 UTC
Permalink
Post by Miroslaw Kwasniak
Post by o***@interia.pl
Post by Oli
I teraz spróbuj tym 'rewelacyjnym' algorytmem udowodnić, że 1 000 003 jest liczbą pierwszą.
Ogólnie znanym algorytmem zajmuje to mniej niż 1 msec a tym algorytmem wymaga to 1 000 002 iteracji.
O większych liczbach zapomnijmy.
Fakt, funkcja wydaje się wymagać najwięcej iteracji do sprawdzenia właśnie
liczb pierwszych. Ale nie wszystkie testowane liczby będą pierwsze, więc
powinniśmy oszczędzać trochę iteracji przy liczbach złożonych.
Trochę to jest eufemizm, przy ilości kroków O(d) :(
Twoja metoda do d<=2000001 zajmuje mi w pari 20 minut, a funkcja nextprime
n=1;p=3;while(p<200000000,p=nextprime(p+1);n+=1);n
time = 47,294 ms.
%70 = 11078937
Ogólnie kilka postów wyżej wobec oszacowania Bartka i licznych wykresów - wyraźnie pokazujących regresję liniową czasów stopów przyznałem, że przekonują mnie te argumenty. I jeszcze raz oficjalnie to przyznaję. Algorytm (w postaci od której zaczęliśmy rozmowę) miał jakiekolwiek szanse bronić się pod względem znajdowania dużych liczb pierwszych tylko pod warunkiem np. logarytmicznej regresji czasów stopów - w co wierzyłem. Niestety tak nie jest, dlatego można zamknąć temat znajdowania dużych liczb pierwszych za pomocą tej funkcji.

Jakkolwiek można ją badać pod innym kątem, np. szukania najmniejszego k, przy zadanym d, takiego, że d dzieli liczbę 2^k-1 (była o tym też mowa tu: https://groups.google.com/forum/?fromgroups=#!topic/pl.sci.matematyka/z0D8_q9czgs, choć sama funkcja pojawiła się dopiero pod koniec wątku). Pomyślę też nad kolejnymi modyfikacjami funkcji pod kątem znajdowania liczb pierwszych w jakiś inny sposób (choć raczej nie uda się już pod tyn kątem nic z tej funkcji wykrzesać), bo w zastosowaniu do algorytmu o którym jak dotąd rozmawialiśmy funkcja może być tylko ciekawostką.
bartekltg
2013-03-07 13:06:02 UTC
Permalink
Post by Oli
Widzę że jeszcze dalej walczysz z wiatrakami
Ojtam. Przecież nie traktuję tego jako propozycji algorytmu,
że się nie nadaje napisałem zaraz na początku, ale jako
teoretyczny problem. Okazał się zresztą całkiem ciekawym
zadankiem z okolic algebry.
Post by Oli
Dla największej liczby liczb pierwszych t=d-1, dla nieco mniejszej t =(d-1)/2
dl jeszcze mniejszej liczby liczb pierwszych t = (d-1)/3 itd
I teraz spróbuj tym 'rewelacyjnym' algorytmem udowodnić, że 1 000 003
jest liczbą pierwszą.
Pseudopierwszą. Te iteracje to takie samo bieganie po grupie
multiplikatywnej modulo d poprzez potęgowanie dwójki, tyle,
że my biegamy w drugą stronę.
Post by Oli
Ogólnie znanym algorytmem zajmuje to mniej niż 1 msec a tym algorytmem
wymaga to 1 000 002 iteracji.
O większych liczbach zapomnijmy.
Pisałem o tym, algorytm potęgowania binarnego modulo d ma
koszt wielomianowy względem log(d).
Ten algorytm jest więcej niż liniowy względem d, czyli patrząc
z punktu widzenia ilośći bitów jest wykładniczy i to go dyskwalifikuje
do zastosowań. Pisaliśmy o tym już w poprzednim wątku.

Ale dlaczgo działa? ;>
Post by Oli
Przypomina mi to znany rysunek Mleczki z czasów PRLu z podpisem " co by
tu jeszcze spieprzyć"
Marudzisz dla marudzenia;>

pzdr
bartekltg
osobliwy nick
2020-01-25 05:13:51 UTC
Permalink
Tak mi się przypomniało, że kiedyś w tym wątku zastanawialiśmy się nad funkcją:

f(x) = x/2 + a/2 - gdy x jest nieparzyste
f(x) = x/2 - gdy x jest parzyste

Z tego co pamiętam uparłem się wtedy na skonstruowanie na jej podstawie algorytmu do znajdowania liczb pierwszych i pseudopierwszych. Był też poszukiwany dowód, że funkcja zapętla się dla dowolnego "d" iterowana dla x=1.
Post by bartekltg
Te iteracje to takie samo bieganie po grupie
multiplikatywnej modulo d poprzez potęgowanie dwójki, tyle,
że my biegamy w drugą stronę.
Co ciekawe dowód na to 3 lata później ukazał się też w tej pracy:

https://arxiv.org/pdf/1611.03919.pdf

"Additive Collatz Trajectories" - Aalok Thakkar, Mrunmay Jagadale. W Proposition 3 udowodnili oni, że te ciągi będą się zapętlać dla wszystkich x mniejszych lub równych a. O ile a jest względnie pierwsze z 2. A jako, że ja rozpatrywałem tylko "a" nieparzyste, to będzie tak zawsze.

Ot tak przypomniał mi się temat, bo akurat czytałem tę pracę. Co ciekawe autorzy sugerują możliwość stworzenia kryptografii klucza publicznego w oparciu o tego rodzaju funkcje, choć na tę chwilę nie rozumiem jeszcze jak miałoby to działać.
Miroslaw Kwasniak
2013-03-08 07:40:12 UTC
Permalink
Post by Oli
I teraz spróbuj tym 'rewelacyjnym' algorytmem udowodnić, że 1 000 003 jest liczbą pierwszą.
Ogólnie znanym algorytmem zajmuje to mniej niż 1 msec a tym algorytmem wymaga to 1 000 002 iteracji.
O większych liczbach zapomnijmy.
Masz rację, efektywnośc jest kiepska (czasy uyskane w pari_gp):

? f(1000003)
time = 641 ms.
%57 = 1000002

? isprime(1000003)
time = 0 ms.
%58 = 1
Oli
2013-03-08 19:10:26 UTC
Permalink
Post by Miroslaw Kwasniak
? f(1000003)
time = 641 ms.
%57 = 1000002
jaką wersję pari 2.?.? uzywałeś i na jakiej maszynie to robiłeś bo czas jest rewelacyjny

Ja pari nie używam, alem mam na stanie. Wykorzystałem twój kod z twojego innego postu
Z pari-gp 2.3.3 i na P4 3.0 MHz uzyskałem czas 3,297 ms

PS to jest wersja pod windows. Może ty masz pod linuxa?

--
Oli
Miroslaw Kwasniak
2013-03-08 22:59:54 UTC
Permalink
Post by Oli
Post by Miroslaw Kwasniak
? f(1000003)
time = 641 ms.
%57 = 1000002
jaką wersję pari 2.?.? uzywałeś i na jakiej maszynie to robiłeś bo czas jest rewelacyjny
Ja pari nie używam, alem mam na stanie. Wykorzystałem twój kod z twojego innego postu
Z pari-gp 2.3.3 i na P4 3.0 MHz uzyskałem czas 3,297 ms
PS to jest wersja pod windows. Może ty masz pod linuxa?
pari-gp 2.5.1 C2D ***@3.00GHz pod linuksem 64bit.

A w dodatku kompilator gp2c daje jeszcze szybszy kod:
172 ms lub po małej optymalizacji tylko 88 ms
Oli
2013-03-09 14:39:35 UTC
Permalink
Post by Miroslaw Kwasniak
Post by Oli
Post by Miroslaw Kwasniak
? f(1000003)
time = 641 ms.
%57 = 1000002
jaką wersję pari 2.?.? uzywałeś i na jakiej maszynie to robiłeś bo czas jest rewelacyjny
No tak, tak myślałem pod linuksem, nowsza wersja pari i dobra maszyna dają dobre rezultaty
Post by Miroslaw Kwasniak
172 ms lub po małej optymalizacji tylko 88 ms
bo zamieniasz kod interpretera na kod C, ale trzeba jeszcze dodać czas na uruchomienie kompilatora i kompilację.

Kiedyś zniechęciłem się do pari bo przy 'nieco' większych liczbach czasy obliczeń gwałtownie rosły.
Teraz zrobiłem taki mały teścik

isprime(10^500+961)

na mojej maszynie z gp 2.3.3 było 5'35''. Fatalnie
na innej maszynie (Q6700 2.66GHz 64B) i najnowszej wersji gp 2.6.0 było 1'43''. Ponad 3 razy lepiej ale i tak
marny wynik.
Ciekawy jestem jak u ciebie ten teścik by wypadł
--
Oli
Miroslaw Kwasniak
2013-03-11 21:09:51 UTC
Permalink
Post by Oli
Kiedyś zniechęciłem się do pari bo przy 'nieco' większych liczbach czasy obliczeń gwałtownie rosły.
Teraz zrobiłem taki mały teścik
Pari może nie jest optymalne, ale złożoność istniejących algorytmów to nie
jego wina ;)
Post by Oli
isprime(10^500+961)
na mojej maszynie z gp 2.3.3 było 5'35''. Fatalnie
na innej maszynie (Q6700 2.66GHz 64B) i najnowszej wersji gp 2.6.0 było 1'43''. Ponad 3 razy lepiej ale i tak
marny wynik.
Ciekawy jestem jak u ciebie ten teścik by wypadł
46 sekund
Miroslaw Kwasniak
2013-03-08 07:36:37 UTC
Permalink
Post by bartekltg
Post by o***@interia.pl
No tak, można to napisać: "d" jest pierwsza lub pseudopierwsza, wtedy
i tylko wtedy, gdy "t" dzieli liczbę "d-1" (bez reszty).
Coś nadal się nie zgadza. A pisałeś, że sprawdziłeś dla 10 tysięcy.
Sprawdziłem w 20 minut do 200001, kod w pari-gp:

ispseudoprimeF(n)=Mod(2,n)^(n-1)==1
f(d)=local(n=0,x=1+d);while(x>1,n+=1;x=if(x%2,x+d,x)/2);n

for(i=1,100000, d=2*i+1;t=f(d);p=isprime(d);pp=ispseudoprimeF(d);r=(d-1)%t; if(bitxor(bitor(p,pp),!r),print([d,t,p,pp,r])) )
bartekltg
2013-03-07 13:05:32 UTC
Permalink
W dniu 2013-03-03 09:42, ***@interia.pl pisze:


Omnia_vanitas zaproponował dla każdego d następujący ciąg
zdefiniowany rekurencyjnie

x_0 = 1.

x_{n+1} = f(x) = x_n/2 dla x_n parzystego
= (x_n+d)/2 dla nieparzystego.

Szukamy okresu tego ciągu, inaczej w wątku zwanemu
punktem stopu,

Najmniejsze t>0, takie, że x_t = 1.


Oraz hipotezę: d jest pseudopierwsza, <=> w powiązanym
z nią ciągu t jest dzielnikiem (d-1)


Poszlaki:

Pierwszoplanowość i wyrażenie d-1 od razu nasuwa małe
twierdzenie Fermata

2^(d-1) = 1 (mod d)

jeśli d jest pseudopierwsze dla 2.


Rozpatrujemy więc kolejne potęgi 2 modulo d.
Chwila przypomnienia ze szkoły, okaże się, że
biegamy w kółko po grupie multiplikatywnej
modulo p. Definiujemy ją jako zbiór liczb
naturalnych (bez zera) względnie pierwszych z d,
z działaniem mnożenia.
Jeśli d jest pierwsze, wszystkie liczby <d sa z nią
względnie pierwsze, stąd rząd (liczba elementów)
grupy wynosi (d-1).
Skądinąd dla danego elementu g w grupie skończonej
zawsze istneije takie k, że g^k =1, a twierdzenia
Lagrange'a mówi nam, że k musi być dzielnikiem rzędu
grupy. czyli k dzieli d-1. I tak z grubsza idzie
dowód MTF.


Prześledźmy naszą iterację dla d=11 i d=15.

x {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
f(x) {6, 1, 7, 2, 8, 3, 9, 4, 10, 5}

x {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}
f(x){8, 1, 9, 2, 10, 3, 11, 4, 12, 5, 13, 6, 14, 7}

Dla pierwszego przypadku idąc po tej permutacji
przebiegamy wszystkie elementy (ale nie musi tak być!,
patrz 7)

W drugiem, liczby podzielne na 3 i 5 mają własne cykle.
Jeśli je usuniemy, zostaną tylko elementy względnie
pierwsze z 15. Znajome...



******************************************
Koniec zabawy, dowody;)

Badając pseudopierwszosć liczby d bierzemy liczbę 2
i podnosimy ją do kolejnych potęg.

Czyli budujemy ciąg w grupie multiplikatywnej mod d
postaci
x_0=1;
x_1 =2;
x_{n+1} = 2 * x_{n} (mod p)

teraz, przez t>0 to najmniejsza liczba t.że x_t = 1
Znów znajome.
Liczba jest pseudopierwsza, gdy t dzieli (d-1). Patrz dowód MTF.
Znajome:)


Ciąg wątkodawcy to nic innego niż ten sam ciąg,
ale w _odwrotnej_ kolejności (teraz wydaje się trywialne)

f(x) to to samo co x/2 w (Z/dZ)*.

Jak działa y = 2*x.
Liczby x < d/2 zostają zamienione na y=2x, zawsze parzyste.
Liczby x > d/2 (u nas d jest nieparzyste, wiec równości nigdy nie ma)
zostaje zamieniona na y = 2x - d. (bo 2x in [d, 2d)),
wynik zawsze nieparzysty


Iteracja wątkodawcy.

x = (y)/2 dla y parzystego., x w wyniku zawsze <d/2.
Odwracając y = 2x. Zgadza się.
x = (y+d)/2 dla y nieparzystego. wynik zawsze > d/2!
Odwracając y = 2x - d. Zgadza się.

A więc jeśli w ciągu wątkodawcy x_t =1,
to oznacza, że również 2^t =1 (mod d)
Jeśli t dzieli (d-1) to (d-1)=m*t

2^(d-1) = 2^(t*m) = (2^t)^m = 1^m = 1 (mod p)

czyli d jest pseudopierwsza przy podstawie 2.
Co kończy nasz zamachany dowód.



Te ciągi można uogólniać dla innych podstaw.
Np dla 3:
x = x/3
= (x+d)/3
= (x+2d)/2 //dla odpowiednich podzielności x przez 3.



Algorytmicznie porównywalne jest to do liczenia tego samego ciągu
w przód, czyli ciągle mnożąc przez 2.
Oczywiście, potęgowanie binarne będzie znacznie wydajniejsze
dla dużych liczb.


pzdr
bartekltg
Oli
2013-03-07 18:53:56 UTC
Permalink
Post by bartekltg
Te ciągi można uogólniać dla innych podstaw.
x = x/3
= (x+d)/3
= (x+2d)/2 //dla odpowiednich podzielności x przez 3.
Tutaj poniosła cię fantazja.
x = (x+d)/3
"dla odpowiednich podzielności x przez 3" czyli x mod 3 == 1 a co z d ??
to samo z x = (x+2d)/2 <-- i jeszcze to
--
Oli
bartekltg
2013-03-07 19:37:25 UTC
Permalink
Post by Oli
Post by bartekltg
Te ciągi można uogólniać dla innych podstaw.
x = x/3
= (x+d)/3
= (x+2d)/2 //dla odpowiednich podzielności x przez 3.
literówka, (x+2d)/3
Post by Oli
Tutaj poniosła cię fantazja.
Bo?
Post by Oli
x = (x+d)/3
"dla odpowiednich podzielności x przez 3" czyli x mod 3 == 1 a co z d ??
to samo z x = (x+2d)/2 <-- i jeszcze to
Jak nie rozumiesz, to się pytaj, nie oceniaj;>

d musi być względnie pierwsze z 3. Czyli to samo założenie co
przy iteracjach w przód (po (Z/dZ)* - siedzą tam tylko elementy
względnie pierwsze z d)

Gałązkę dopasowujemy tak, aby wybrać liczbę z x, x+d, x+2d
podzielną przez 3. Zawsze będzie dokładnie jedna.

Rozpisując

x_{n+1} = x_n/3 dla x mod 3 =0
= (x+d)/3 dla x mod 3 = 1
= (x+2d)/3 dla x mod 3 = 2
gdy d mod 3 = 2
lub
x_{n+1} = x_n/3 dla x mod 3 =0
= (x+d)/3 dla x mod 3 = 2
= (x+2d)/3 dla x mod 3 = 1
gdy d mod 3 = 1


że to jest równoważne działaniu
x_{n+1} = x_n * (3^-1)
w (Z/dZ)* można sprawdzić na palcach jak dla 2.
(3^-1) to element odwrotny do 3.

pzdr
bartekltg
osobliwy nick
2016-04-25 20:45:04 UTC
Permalink
A więc jeśli w ciągu wątkodawcy x_t =1.
Skąd pewność, że nastąpi takie x_n, które będzie równe 1, po skończonej liczbie kroków (w Twojej odwróconej funkcji lub w mojej pierwotnej)? Skąd pewność, że iteracje nie wpadną w jakąś pętlę bez 1 i nigdy nie osiągną 1? Albo, że nie będą rozbieżne do nieskończoności?

Po drugie skąd pewność, że t (liczba iteracji), dla jakiejś liczby p (w ciągu zdefiniowanym 0,5x+p/2) będzie równe akurat ord_p(2) lub wielokrotność ord_p(2)?
bartekltg
2016-04-26 14:33:06 UTC
Permalink
Bartekltg, po czasie analizowana zagadnień poruszanych w tym wątku
mam pytania do Twojego dowodu, który podczas naszej ostatniej rozmowy
przeanalizowałem za mało dokładnie. Wydaje się, że wszystko się zgada
A więc jeśli w ciągu wątkodawcy x_t =1.
Skąd pewność, że nastąpi takie x_n, które będzie równe 1, po
skończonej liczbie kroków (w Twojej odwróconej funkcji lub w mojej
pierwotnej)? Skąd pewność, że iteracje nie wpadną w jakąś pętlę bez 1
i nigdy nie osiągną 1? Albo, że nie będą rozbieżne do
nieskończoności?
Wyciągasz wątek sprzed 3 lat (!) i nie cytujesz fragmentów?
Jak ktokolwiem ma się połapać:)


Nie piszę tam 'w ciagu wątkodawcy wystąpi to a to'.
Jest tam napisana "Jeśli w ciągu wątkodawcy [wystąpi] x_t =1,
to będzie to a to".
Po drugie skąd pewność, że t (liczba iteracji), dla jakiejś liczby p
(w ciągu zdefiniowanym 0,5x+p/2) będzie równe akurat ord_p(2) lub
wielokrotność ord_p(2)?
Z równoważności obu ciągów.

Tak mi się wydaje. Nie wiem nawet czy napewno pytasz o to, o co myślę
że pytasz, bo nie cytujesz ani fragmentu;-)

pzdr
bartekltg
osobliwy nick
2016-04-26 19:55:32 UTC
Permalink
Poniżej cały cytat tamtego dowodu.
Post by bartekltg
Omnia_vanitas zaproponował dla każdego d następujący ciąg
zdefiniowany rekurencyjnie
x_0 = 1.
x_{n+1} = f(x) = x_n/2 dla x_n parzystego
= (x_n+d)/2 dla nieparzystego.
Szukamy okresu tego ciągu, inaczej w wątku zwanemu
punktem stopu,
Najmniejsze t>0, takie, że x_t = 1.
Oraz hipotezę: d jest pseudopierwsza, <=> w powiązanym
z nią ciągu t jest dzielnikiem (d-1)
Pierwszoplanowość i wyrażenie d-1 od razu nasuwa małe
twierdzenie Fermata
2^(d-1) = 1 (mod d)
jeśli d jest pseudopierwsze dla 2.
Rozpatrujemy więc kolejne potęgi 2 modulo d.
Chwila przypomnienia ze szkoły, okaże się, że
biegamy w kółko po grupie multiplikatywnej
modulo p. Definiujemy ją jako zbiór liczb
naturalnych (bez zera) względnie pierwszych z d,
z działaniem mnożenia.
Jeśli d jest pierwsze, wszystkie liczby <d sa z nią
względnie pierwsze, stąd rząd (liczba elementów)
grupy wynosi (d-1).
Skądinąd dla danego elementu g w grupie skończonej
zawsze istneije takie k, że g^k =1, a twierdzenia
Lagrange'a mówi nam, że k musi być dzielnikiem rzędu
grupy. czyli k dzieli d-1. I tak z grubsza idzie
dowód MTF.
Prześledźmy naszą iterację dla d=11 i d=15.
x {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
f(x) {6, 1, 7, 2, 8, 3, 9, 4, 10, 5}
x {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}
f(x){8, 1, 9, 2, 10, 3, 11, 4, 12, 5, 13, 6, 14, 7}
Dla pierwszego przypadku idąc po tej permutacji
przebiegamy wszystkie elementy (ale nie musi tak być!,
patrz 7)
W drugiem, liczby podzielne na 3 i 5 mają własne cykle.
Jeśli je usuniemy, zostaną tylko elementy względnie
pierwsze z 15. Znajome...
******************************************
Koniec zabawy, dowody;)
Badając pseudopierwszosć liczby d bierzemy liczbę 2
i podnosimy ją do kolejnych potęg.
Czyli budujemy ciąg w grupie multiplikatywnej mod d
postaci
x_0=1;
x_1 =2;
x_{n+1} = 2 * x_{n} (mod p)
teraz, przez t>0 to najmniejsza liczba t.że x_t = 1
Znów znajome.
Liczba jest pseudopierwsza, gdy t dzieli (d-1). Patrz dowód MTF.
Znajome:)
Ciąg wątkodawcy to nic innego niż ten sam ciąg,
ale w _odwrotnej_ kolejności (teraz wydaje się trywialne)
f(x) to to samo co x/2 w (Z/dZ)*.
Jak działa y = 2*x.
Liczby x < d/2 zostają zamienione na y=2x, zawsze parzyste.
Liczby x > d/2 (u nas d jest nieparzyste, wiec równości nigdy nie ma)
zostaje zamieniona na y = 2x - d. (bo 2x in [d, 2d)),
wynik zawsze nieparzysty
Iteracja wątkodawcy.
x = (y)/2 dla y parzystego., x w wyniku zawsze <d/2.
Odwracając y = 2x. Zgadza się.
x = (y+d)/2 dla y nieparzystego. wynik zawsze > d/2!
Odwracając y = 2x - d. Zgadza się.
A więc jeśli w ciągu wątkodawcy x_t =1,
to oznacza, że również 2^t =1 (mod d)
Jeśli t dzieli (d-1) to (d-1)=m*t
2^(d-1) = 2^(t*m) = (2^t)^m = 1^m = 1 (mod p)
czyli d jest pseudopierwsza przy podstawie 2.
Co kończy nasz zamachany dowód.
Te ciągi można uogólniać dla innych podstaw.
x = x/3
= (x+d)/3
= (x+2d)/2 //dla odpowiednich podzielności x przez 3.
Algorytmicznie porównywalne jest to do liczenia tego samego ciągu
w przód, czyli ciągle mnożąc przez 2.
Oczywiście, potęgowanie binarne będzie znacznie wydajniejsze
dla dużych liczb.
pzdr
bartekltg
Dowód, którego wtedy szukałem to dowód, testu pierwszości liczby p za pomocą ciągu zdefiniowanego rekurencyjnie:

0,5x+p/2 - gdy x nieparzyste
0,5x - gdy x parzyste

test ten mówi, że gdy ciąg zapętla się dla wybranego p i x=1 po (p-1)/c iteracjach, to p jest liczbą pierwszą lub pseudopierwszą. Dodatkowo miałem przeświadczenie, że ciąg zapętla się dla każdej liczby pierwszej p.
Post by bartekltg
Nie piszę tam 'w ciagu wątkodawcy wystąpi to a to'.
Jest tam napisana "Jeśli w ciągu wątkodawcy [wystąpi] x_t =1,
to będzie to a to".
Fakt. Zatem na tym etapie z tego wynika, że mamy dowód dla liczb pierwszych i pseudopierwszych p, które się zapętlają, ale nie wiemy, czy algorytm zadziała dla dowolnych liczb pierwszych i pseudopierwszych p (czy dla niektórych p ciąg nie będzie rozbieżny do nieskończoności lub nie wpadnie w inną pętlę taka, która nie osiąga liczby 1). Przy czym przypadek rozbieżności do nieskończoności można łatwo wykluczyć, gdyż w tym odwróconym ciągu nie może istnieć liczba większa niż p. Dowód:

rozważmy najmniejszy wyraz x_n w ciągu:

2x, gdy x < p/2
2x - p, gdy x > p/2

iterowanym dla x=1, taki, że jest on liczbą większą niż p. Wówczas na pewno poprzedni wyraz tego ciągu nie mógł powstać w wyniku operacji "2x, gdy x < p/2", bo x_n > p/2. Jednak wyraz ten nie mógł także powstać w wyniku operacji 2x-p, bo jeśli 2x-p=x_n, to x=(x_n+p)/2, z tego wynika, że wyraz poprzedzający x_n jest także większy od p - a to sprzeczne z założeniem, że x_n jest najmniejszym wyrazem w ciągu większym od p.
Post by bartekltg
Post by osobliwy nick
Po drugie skąd pewność, że t (liczba iteracji), dla jakiejś liczby p
(w ciągu zdefiniowanym 0,5x+p/2) będzie równe akurat ord_p(2) lub
wielokrotność ord_p(2)?
Z równoważności obu ciągów.
No tak, ale skąd pewność, że ten odwrócony ciąg zwróci x=1 po dokładnie ord_p(2) iteracji?
bartekltg
2016-04-27 14:16:57 UTC
Permalink
Post by osobliwy nick
Poniżej cały cytat tamtego dowodu.
Post by bartekltg
Omnia_vanitas zaproponował dla każdego d następujący ciąg
zdefiniowany rekurencyjnie
x_0 = 1.
x_{n+1} = f(x) = x_n/2 dla x_n parzystego = (x_n+d)/2
dla nieparzystego.
Szukamy okresu tego ciągu, inaczej w wątku zwanemu punktem stopu,
Najmniejsze t>0, takie, że x_t = 1.
Oraz hipotezę: d jest pseudopierwsza, <=> w powiązanym z nią ciągu
t jest dzielnikiem (d-1)
Pierwszoplanowość i wyrażenie d-1 od razu nasuwa małe twierdzenie
Fermata
2^(d-1) = 1 (mod d)
jeśli d jest pseudopierwsze dla 2.
Rozpatrujemy więc kolejne potęgi 2 modulo d. Chwila przypomnienia
ze szkoły, okaże się, że biegamy w kółko po grupie
multiplikatywnej modulo p. Definiujemy ją jako zbiór liczb
naturalnych (bez zera) względnie pierwszych z d, z działaniem
mnożenia. Jeśli d jest pierwsze, wszystkie liczby <d sa z nią
względnie pierwsze, stąd rząd (liczba elementów) grupy wynosi
(d-1). Skądinąd dla danego elementu g w grupie skończonej zawsze
istneije takie k, że g^k =1, a twierdzenia Lagrange'a mówi nam, że
k musi być dzielnikiem rzędu grupy. czyli k dzieli d-1. I tak z
grubsza idzie dowód MTF.
Prześledźmy naszą iterację dla d=11 i d=15.
x {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} f(x) {6, 1, 7, 2, 8, 3, 9, 4,
10, 5}
x {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14} f(x){8, 1,
9, 2, 10, 3, 11, 4, 12, 5, 13, 6, 14, 7}
Dla pierwszego przypadku idąc po tej permutacji przebiegamy
wszystkie elementy (ale nie musi tak być!, patrz 7)
W drugiem, liczby podzielne na 3 i 5 mają własne cykle. Jeśli je
usuniemy, zostaną tylko elementy względnie pierwsze z 15.
Znajome...
****************************************** Koniec zabawy, dowody;)
Badając pseudopierwszosć liczby d bierzemy liczbę 2 i podnosimy ją
do kolejnych potęg.
Czyli budujemy ciąg w grupie multiplikatywnej mod d postaci x_0=1;
x_1 =2; x_{n+1} = 2 * x_{n} (mod p)
teraz, przez t>0 to najmniejsza liczba t.że x_t = 1 Znów znajome.
Liczba jest pseudopierwsza, gdy t dzieli (d-1). Patrz dowód MTF.
Znajome:)
Ciąg wątkodawcy to nic innego niż ten sam ciąg, ale w _odwrotnej_
kolejności (teraz wydaje się trywialne)
f(x) to to samo co x/2 w (Z/dZ)*.
Jak działa y = 2*x. Liczby x < d/2 zostają zamienione na y=2x,
zawsze parzyste. Liczby x > d/2 (u nas d jest nieparzyste, wiec
równości nigdy nie ma) zostaje zamieniona na y = 2x - d. (bo 2x in
[d, 2d)), wynik zawsze nieparzysty
Iteracja wątkodawcy.
x = (y)/2 dla y parzystego., x w wyniku zawsze <d/2. Odwracając y =
2x. Zgadza się. x = (y+d)/2 dla y nieparzystego. wynik zawsze >
d/2! Odwracając y = 2x - d. Zgadza się.
A więc jeśli w ciągu wątkodawcy x_t =1, to oznacza, że również 2^t
=1 (mod d) Jeśli t dzieli (d-1) to (d-1)=m*t
2^(d-1) = 2^(t*m) = (2^t)^m = 1^m = 1 (mod p)
czyli d jest pseudopierwsza przy podstawie 2. Co kończy nasz
zamachany dowód.
Te ciągi można uogólniać dla innych podstaw. Np dla 3: x = x/3 =
(x+d)/3 = (x+2d)/2 //dla odpowiednich podzielności x przez 3.
Algorytmicznie porównywalne jest to do liczenia tego samego ciągu w
przód, czyli ciągle mnożąc przez 2. Oczywiście, potęgowanie binarne
będzie znacznie wydajniejsze dla dużych liczb.
pzdr bartekltg
Dowód, którego wtedy szukałem to dowód, testu pierwszości liczby p za
0,5x+p/2 - gdy x nieparzyste 0,5x - gdy x parzyste
test ten mówi, że gdy ciąg zapętla się dla wybranego p i x=1 po
(p-1)/c iteracjach, to p jest liczbą pierwszą lub pseudopierwszą.
Dodatkowo miałem przeświadczenie, że ciąg zapętla się dla każdej
liczby pierwszej p.
Już pisałem o tym, nie używaj sformułowania "pierwsza lub
pseudopierwsza". To tak jakbyś mówił owoce i jakbłka.
Każda pierwsza jest pseudopierwsza.

A co do meritum, to przecież o tym jest ten dowód sprzed 3 lat.
[Od razu zakładam, że p jest nieparzyste. ]

Zaczynamy od 1 i iterujemy Twoim wzorkiem.
To jest to samo, jakbyśmy 'od tyłu' iterowali moim wzorkiem.

Warunke który podałęś jest definicją pseudopierwszosci.
Post by osobliwy nick
Post by bartekltg
Nie piszę tam 'w ciagu wątkodawcy wystąpi to a to'. Jest tam
napisana "Jeśli w ciągu wątkodawcy [wystąpi] x_t =1, to będzie to
a to".
Fakt. Zatem na tym etapie z tego wynika, że mamy dowód dla liczb
pierwszych i pseudopierwszych p, które się zapętlają, ale nie wiemy,
czy algorytm zadziała dla dowolnych liczb pierwszych i
pseudopierwszych p (czy dla niektórych p ciąg nie będzie rozbieżny do
nieskończoności lub nie wpadnie w inną pętlę taka, która nie osiąga
liczby 1).
Czytałeś tamtego posta? Teraz, nie 3 lata temu?

Każda liczba p się zapętli, tylko okres może być inny (nie bedacy
dzielnikiem p-1).
Post by osobliwy nick
Post by bartekltg
Z równoważności obu ciągów.
No tak, ale skąd pewność, że ten odwrócony ciąg zwróci x=1 po
dokładnie ord_p(2) iteracji?
Bo to jest definicja ord_p(2).
;-)

pzdr
bartekltg
osobliwy nick
2016-04-27 16:19:41 UTC
Permalink
Post by bartekltg
Już pisałem o tym, nie używaj sformułowania "pierwsza lub
pseudopierwsza". To tak jakbyś mówił owoce i jakbłka.
Każda pierwsza jest pseudopierwsza.
Zgadza się.
Post by bartekltg
A co do meritum, to przecież o tym jest ten dowód sprzed 3 lat.
[Od razu zakładam, że p jest nieparzyste. ]
Zaczynamy od 1 i iterujemy Twoim wzorkiem.
To jest to samo, jakbyśmy 'od tyłu' iterowali moim wzorkiem.
Zgadza się, ale bez dowodu, że odwrócona funkcja nie może być rozbieżna oraz, że żadna z funkcji nie wpadnie w jakąś inną pętlę, nie zwierającą liczby 1, nie można stwierdzić czy uzyskamy "od przodu" i "od tyłu" te same ciągi. Tak mi się wydaje. Iterując dla jakiegoś "w przód" możemy dostać na przykład:

1,...,3,8,3,8,...

a iterując "w tył"

1,...,5,9,12,5,9,12,...

Jeżeli udowodnimy, że nie będzie innych pętli, to dołożenie do tego dowodu, że funkcja w tył nie może być rozbieżna (który przedstawiłem) prowadzi do wniosku, że funkcja w tył musi znów osiągać liczbę 1 (i wtedy odwzorowanie funkcji jest 1:1). Ale wciąż brakuje mi dowodu, że nie może być innych pętli.
Post by bartekltg
Warunke który podałęś jest definicją pseudopierwszosci.
Warunek: "gdy ciąg zapętla się dla wybranego p i x=1 po (p-1)/c iteracjach, to p jest liczbą pseudopierwszą" jest definicją pseudopierwszości pod warunkiem (p-1)/c jest wielokrotnością ord_p(2).
Post by bartekltg
Post by osobliwy nick
Post by bartekltg
Nie piszę tam 'w ciagu wątkodawcy wystąpi to a to'. Jest tam
napisana "Jeśli w ciągu wątkodawcy [wystąpi] x_t =1, to będzie to
a to".
Fakt. Zatem na tym etapie z tego wynika, że mamy dowód dla liczb
pierwszych i pseudopierwszych p, które się zapętlają, ale nie wiemy,
czy algorytm zadziała dla dowolnych liczb pierwszych i
pseudopierwszych p (czy dla niektórych p ciąg nie będzie rozbieżny do
nieskończoności lub nie wpadnie w inną pętlę taka, która nie osiąga
liczby 1).
Czytałeś tamtego posta? Teraz, nie 3 lata temu?
Tak.
Post by bartekltg
Każda liczba p się zapętli, tylko okres może być inny (nie bedacy
dzielnikiem p-1).
A skąd wiemy, że każda liczba p się zapętli (a dokładnie ,że każda liczba x=1 osiągnie znów 1 w ciągu 0,5x+p/2)?
Post by bartekltg
Post by osobliwy nick
Post by bartekltg
Z równoważności obu ciągów.
No tak, ale skąd pewność, że ten odwrócony ciąg zwróci x=1 po
dokładnie ord_p(2) iteracji?
Bo to jest definicja ord_p(2).
Definicja ord_p(2) to najmniejsza liczba k taka, że 2^k=1 (mod p). Jak odwrócona funkcja ma się do tej definicji? Nie widzę związku (poza tym, że oczywiście długość pętli daje zawsze ord_p(2) - ale dlaczego?) Np. dla p=43 następuje to po 14 iteracjach. Skąd wiadomo, że nie nastąpi po 13?
bartekltg
2016-04-27 17:16:30 UTC
Permalink
Post by bartekltg
Post by bartekltg
Już pisałem o tym, nie używaj sformułowania "pierwsza lub
pseudopierwsza". To tak jakbyś mówił owoce i jakbłka. Każda
pierwsza jest pseudopierwsza.
Zgadza się.
Post by bartekltg
A co do meritum, to przecież o tym jest ten dowód sprzed 3 lat. [Od
razu zakładam, że p jest nieparzyste. ]
Zaczynamy od 1 i iterujemy Twoim wzorkiem. To jest to samo,
jakbyśmy 'od tyłu' iterowali moim wzorkiem.
Zgadza się, ale bez dowodu, że odwrócona funkcja nie może być
rozbieżna
Oj, proste rzeczy zostawia się czytylnikowi;p

Obie funkcje przeoprowadzają zbiór
P = {0,1,2... p-1}
na samego siebie.

g(x) = 2*x mod p
w sposób oczywisty.

f(x) = x/2 dla x parzystego
= (x+p)/2 dla nieparzystego.
też prosto
parzysty przypadek:
0 <= x/2 <p/2 <= p
nieparzysty:
0<= (x+p)/2 < (p+p)/2 = p
Post by bartekltg
oraz, że żadna z funkcji nie wpadnie w jakąś inną pętlę,
To jest objęte przez dowód.
Post by bartekltg
nie zwierającą liczby 1, nie można stwierdzić czy uzyskamy "od
przodu" i "od tyłu" te same ciągi. Tak mi się wydaje. Iterując dla
1,...,3,8,3,8,...
a iterując "w tył"
1,...,5,9,12,5,9,12,...
Nie, nie można. Twoja operacja to mnożenie przez element odwrotny
do 2.

Pomyśl o tym w ten sposób.
Iterując 'do tyłu' dostaje ciąg
1 a,b,... y, z, 1.
^ |
Doszedłem do jedynki. Zawsze dojdę.

To teraz iteruję od "1". Ale nie tej pierwszej, tylko tej,
do której doszedłem, zonaczonej |.

Iteracja w przód będą oczywiscie
1, z,y,... b,a,1
| ^

Zgadzasz się?

To teraz zauważ tylko, żę iteracja zależy tylko od liczby. Więc
jak zaczniesz od 'prawidzwej' jedynki wszytko musi isc tak samo.
Post by bartekltg
Post by bartekltg
Warunke który podałęś jest definicją pseudopierwszosci.
Warunek: "gdy ciąg zapętla się dla wybranego p i x=1 po (p-1)/c
iteracjach, to p jest liczbą pseudopierwszą" jest definicją
pseudopierwszości pod warunkiem (p-1)/c jest wielokrotnością
ord_p(2).
Oczywisćie, ze jest. Prosiłem, abyś przeczytał dowód raz jeszcze.

Twierdzenie Lagrange'a:
Rząd dowolnego elementu grupy jest dzielnikiem rzędu grupy
(jej wielkośći).
Grupa multiplikatywna modulo liczba pierwsza p jest rzędu p-1.
Post by bartekltg
Post by bartekltg
Post by osobliwy nick
Post by bartekltg
Nie piszę tam 'w ciagu wątkodawcy wystąpi to a to'. Jest tam
napisana "Jeśli w ciągu wątkodawcy [wystąpi] x_t =1, to będzie
to a to".
Fakt. Zatem na tym etapie z tego wynika, że mamy dowód dla liczb
pierwszych i pseudopierwszych p, które się zapętlają, ale nie
wiemy, czy algorytm zadziała dla dowolnych liczb pierwszych i
pseudopierwszych p (czy dla niektórych p ciąg nie będzie
rozbieżny do nieskończoności lub nie wpadnie w inną pętlę taka,
która nie osiąga liczby 1).
Czytałeś tamtego posta? Teraz, nie 3 lata temu?
Tak.
Ale przecież dopiero co...
Może źle się wyraziłem. Przeczytać dowód to znaczy go przestudiuować,
zpróbowac odtworzyć. To masa pracy, ale z drugiej storny, alternatyywą
jest wypytywanie na grupie co konczy się tym, zę opisuje to samo
tylko innymi słowami. Może szybko mi się znudzić;>
Post by bartekltg
Post by bartekltg
Każda liczba p się zapętli, tylko okres może być inny (nie bedacy
dzielnikiem p-1).
A skąd wiemy, że każda liczba p się zapętli (a dokładnie ,że każda
liczba x=1 osiągnie znów 1 w ciągu 0,5x+p/2)?
-W ciągu *2 mod p osiagnie 1.
-Twoj ciag to odwrotnosc mojego


pzdr
bartekltg
osobliwy nick
2016-04-27 20:28:22 UTC
Permalink
Post by bartekltg
Post by bartekltg
Post by bartekltg
Już pisałem o tym, nie używaj sformułowania "pierwsza lub
pseudopierwsza". To tak jakbyś mówił owoce i jakbłka. Każda
pierwsza jest pseudopierwsza.
Zgadza się.
Post by bartekltg
A co do meritum, to przecież o tym jest ten dowód sprzed 3 lat. [Od
razu zakładam, że p jest nieparzyste. ]
Zaczynamy od 1 i iterujemy Twoim wzorkiem. To jest to samo,
jakbyśmy 'od tyłu' iterowali moim wzorkiem.
Zgadza się, ale bez dowodu, że odwrócona funkcja nie może być
rozbieżna
Oj, proste rzeczy zostawia się czytylnikowi;p
Prosty okazał się tylko przypadek rozbieżności (dla mnie).
Post by bartekltg
Obie funkcje przeoprowadzają zbiór
P = {0,1,2... p-1}
na samego siebie.
Zgadza się.
Post by bartekltg
Post by bartekltg
oraz, że żadna z funkcji nie wpadnie w jakąś inną pętlę,
To jest objęte przez dowód.
Post by bartekltg
nie zwierającą liczby 1, nie można stwierdzić czy uzyskamy "od
przodu" i "od tyłu" te same ciągi. Tak mi się wydaje. Iterując dla
1,...,3,8,3,8,...
a iterując "w tył"
1,...,5,9,12,5,9,12,...
Nie, nie można. Twoja operacja to mnożenie przez element odwrotny
do 2.
Pomyśl o tym w ten sposób.
Iterując 'do tyłu' dostaje ciąg
1 a,b,... y, z, 1.
^ |
Doszedłem do jedynki. Zawsze dojdę.
Tu nie wiem, czy się zgodzić, czy nie - bo dowodu na "zawsze dojdę do 1" mi wciąż brakuje.
Post by bartekltg
To teraz iteruję od "1". Ale nie tej pierwszej, tylko tej,
do której doszedłem, zonaczonej |.
Iteracja w przód będą oczywiscie
1, z,y,... b,a,1
| ^
Zgadzasz się?
Tu się zgadzam, o ile to wcześniejsze twierdzenie "zawsze dojdę do 1" iterując do tyłu jest prawdziwe.
Post by bartekltg
Post by bartekltg
Post by bartekltg
Warunke który podałęś jest definicją pseudopierwszosci.
Warunek: "gdy ciąg zapętla się dla wybranego p i x=1 po (p-1)/c
iteracjach, to p jest liczbą pseudopierwszą" jest definicją
pseudopierwszości pod warunkiem (p-1)/c jest wielokrotnością
ord_p(2).
Oczywisćie, ze jest. Prosiłem, abyś przeczytał dowód raz jeszcze.
Rząd dowolnego elementu grupy jest dzielnikiem rzędu grupy
(jej wielkośći).
Grupa multiplikatywna modulo liczba pierwsza p jest rzędu p-1.
To jest jasne, tylko doprecyzowałem, to co napisałeś wcześniej.
Post by bartekltg
Post by bartekltg
Post by bartekltg
Post by osobliwy nick
Post by bartekltg
Nie piszę tam 'w ciagu wątkodawcy wystąpi to a to'. Jest tam
napisana "Jeśli w ciągu wątkodawcy [wystąpi] x_t =1, to będzie
to a to".
Fakt. Zatem na tym etapie z tego wynika, że mamy dowód dla liczb
pierwszych i pseudopierwszych p, które się zapętlają, ale nie
wiemy, czy algorytm zadziała dla dowolnych liczb pierwszych i
pseudopierwszych p (czy dla niektórych p ciąg nie będzie
rozbieżny do nieskończoności lub nie wpadnie w inną pętlę taka,
która nie osiąga liczby 1).
Czytałeś tamtego posta? Teraz, nie 3 lata temu?
Tak.
Ale przecież dopiero co...
Może źle się wyraziłem. Przeczytać dowód to znaczy go przestudiuować,
zpróbowac odtworzyć. To masa pracy, ale z drugiej storny, alternatyywą
jest wypytywanie na grupie co konczy się tym, zę opisuje to samo
tylko innymi słowami. Może szybko mi się znudzić;>
Post by bartekltg
Post by bartekltg
Każda liczba p się zapętli, tylko okres może być inny (nie bedacy
dzielnikiem p-1).
A skąd wiemy, że każda liczba p się zapętli (a dokładnie ,że każda
liczba x=1 osiągnie znów 1 w ciągu 0,5x+p/2)?
-W ciągu *2 mod p osiagnie 1.
-Twoj ciag to odwrotnosc mojego
Podsumowując - ze wszystkimi etapami dowodu się zgadzam, brakuje mi w tym tylko dowodu, że iteracje rozpoczęte od x=1 (w tył lub w przód) nie wpadną w jakąś pętlę, w której nie wystąpi 1. Weźmy liczbę 43, mamy 0,5x+43 (nieważne, czy iterujemy w przód, czy w tył):

1
22
11
27
35
39
41
42
21
32
16
8
4
2
1

Czyli oczekiwany ciąg, ale dla x=3 mamy:

3
23
33
38
19
31
37
40
20
10
5
24
12
6
3

Pytanie skąd pewność, że iteracje dla x=1 nie wpadną w pętlę liczby 3? Czyli, że na pewnym etapie ciąg nie będzie wyglądał tak (i podobnie dla iteracji w tył):

1
22
11
.
.
.
3
23
33
38
19
31
37
40
20
10
5
24
12
6
3

Oczywiście tu widzimy, że iteracje x=1 nie wpadły w tę, czy w inną pętlę. Ale chodzi mi o dowód dla dowolnych p.

I jeszcze jedno - gdy już ustalimy, że x=1 zawsze osiągnie znów 1, to skąd wiadomo, że po ord_p(2) krokach? Ogólnie ze zbioru 1, ..., p-1 wybieranych jest t liczb. W przypadku p=43 było to t=14 liczb. Mamy tu dwie niezależne pętle o ilości iteracji też wynoszącej t, są to 3,...,3 wypisana przeze mnie oraz 7,...7, które skracają nam t do 14 (zamiast 42, obie zabierają po 14 liczb). Ale skąd pewność, że zawsze wystąpią takie dodatkowe pętle o takiej długości, że długość ciągu 1,...1 wyniesie ord_p(2)? Znów nie widzę, żeby to zostało napisane w dowodzie i moim zdaniem te dodatkowe pętle są kluczem do ostatecznego dowodu. Jakkolwiek to dla jakich liczb i w jakiej ilości występują nie wydaje się być trywialne.
bartekltg
2016-04-27 22:02:45 UTC
Permalink
Post by osobliwy nick
Post by bartekltg
Post by bartekltg
Post by bartekltg
Już pisałem o tym, nie używaj sformułowania "pierwsza lub
pseudopierwsza". To tak jakbyś mówił owoce i jakbłka. Każda
pierwsza jest pseudopierwsza.
Zgadza się.
Post by bartekltg
A co do meritum, to przecież o tym jest ten dowód sprzed 3 lat. [Od
razu zakładam, że p jest nieparzyste. ]
Zaczynamy od 1 i iterujemy Twoim wzorkiem. To jest to samo,
jakbyśmy 'od tyłu' iterowali moim wzorkiem.
Zgadza się, ale bez dowodu, że odwrócona funkcja nie może być
rozbieżna
Oj, proste rzeczy zostawia się czytylnikowi;p
Prosty okazał się tylko przypadek rozbieżności (dla mnie).
Post by bartekltg
Obie funkcje przeoprowadzają zbiór
P = {0,1,2... p-1}
na samego siebie.
Zgadza się.
Post by bartekltg
Post by bartekltg
oraz, że żadna z funkcji nie wpadnie w jakąś inną pętlę,
To jest objęte przez dowód.
Post by bartekltg
nie zwierającą liczby 1, nie można stwierdzić czy uzyskamy "od
przodu" i "od tyłu" te same ciągi. Tak mi się wydaje. Iterując dla
1,...,3,8,3,8,...
a iterując "w tył"
1,...,5,9,12,5,9,12,...
Nie, nie można. Twoja operacja to mnożenie przez element odwrotny
do 2.
Pomyśl o tym w ten sposób.
Iterując 'do tyłu' dostaje ciąg
1 a,b,... y, z, 1.
^ |
Doszedłem do jedynki. Zawsze dojdę.
Tu nie wiem, czy się zgodzić, czy nie - bo dowodu na "zawsze dojdę do 1" mi wciąż brakuje.
Dowód na to, że istnieje takie k, że
2^k =1 (mod p)

[p nieparzyste]


Był, jest na wiki i gdziekolwiek nie zerkniesz.
Myślałem, zę to oczywiste, skoro no godzisz się na nazywanie naszych
działń w tył grupą (a więc przez to i w przód:), w końcu w każdej
grupie skonczonej jesli będziesz potęgować jakiś element, w koncu
dostaniesz element neutralny (u nas jedynkę).


Ale ok, oto dowód:

Rozpatrzmy kolejne potęgi 2 (czyli kolejne wyrazy z rekuerencji
x_{n+1} == 2*x_n ; x_0==1 )

2^n =1 (mod p)

Oczywiście są to liczby naturalne < p.

Jest więc ich co najwyżęj p. Jeśli popatrzysz na pierwsze
p+1 elementów, na pewno znajdą się tam dwie takie same liczby.
Niech bądą to liczby o indeksach i oraz j. j>i

2^i = 2^j (mod p)

2^i = 2^i * 2^(j-i) (mod p)

Skracamy co trzeba (możemy to zrobić modulo p, jesli p jest
nieparzyste).

1 = 2^(j-i) (mod p)

Znaleźliśmy!
k = j-i jest (nie koniecznie jedynym) rozwiązaniem.



pzdr
bartekltg
osobliwy nick
2016-04-28 14:41:41 UTC
Permalink
Post by bartekltg
Post by osobliwy nick
Post by bartekltg
Post by bartekltg
Post by bartekltg
Już pisałem o tym, nie używaj sformułowania "pierwsza lub
pseudopierwsza". To tak jakbyś mówił owoce i jakbłka. Każda
pierwsza jest pseudopierwsza.
Zgadza się.
Post by bartekltg
A co do meritum, to przecież o tym jest ten dowód sprzed 3 lat. [Od
razu zakładam, że p jest nieparzyste. ]
Zaczynamy od 1 i iterujemy Twoim wzorkiem. To jest to samo,
jakbyśmy 'od tyłu' iterowali moim wzorkiem.
Zgadza się, ale bez dowodu, że odwrócona funkcja nie może być
rozbieżna
Oj, proste rzeczy zostawia się czytylnikowi;p
Prosty okazał się tylko przypadek rozbieżności (dla mnie).
Post by bartekltg
Obie funkcje przeoprowadzają zbiór
P = {0,1,2... p-1}
na samego siebie.
Zgadza się.
Post by bartekltg
Post by bartekltg
oraz, że żadna z funkcji nie wpadnie w jakąś inną pętlę,
To jest objęte przez dowód.
Post by bartekltg
nie zwierającą liczby 1, nie można stwierdzić czy uzyskamy "od
przodu" i "od tyłu" te same ciągi. Tak mi się wydaje. Iterując dla
1,...,3,8,3,8,...
a iterując "w tył"
1,...,5,9,12,5,9,12,...
Nie, nie można. Twoja operacja to mnożenie przez element odwrotny
do 2.
Pomyśl o tym w ten sposób.
Iterując 'do tyłu' dostaje ciąg
1 a,b,... y, z, 1.
^ |
Doszedłem do jedynki. Zawsze dojdę.
Tu nie wiem, czy się zgodzić, czy nie - bo dowodu na "zawsze dojdę do 1" mi wciąż brakuje.
Dowód na to, że istnieje takie k, że
2^k =1 (mod p)
[p nieparzyste]
Był, jest na wiki i gdziekolwiek nie zerkniesz.
Myślałem, zę to oczywiste, skoro no godzisz się na nazywanie naszych
działń w tył grupą (a więc przez to i w przód:), w końcu w każdej
grupie skonczonej jesli będziesz potęgować jakiś element, w koncu
dostaniesz element neutralny (u nas jedynkę).
Rozpatrzmy kolejne potęgi 2 (czyli kolejne wyrazy z rekuerencji
x_{n+1} == 2*x_n ; x_0==1 )
2^n =1 (mod p)
Oczywiście są to liczby naturalne < p.
Jest więc ich co najwyżęj p. Jeśli popatrzysz na pierwsze
p+1 elementów, na pewno znajdą się tam dwie takie same liczby.
Niech bądą to liczby o indeksach i oraz j. j>i
2^i = 2^j (mod p)
2^i = 2^i * 2^(j-i) (mod p)
Skracamy co trzeba (możemy to zrobić modulo p, jesli p jest
nieparzyste).
1 = 2^(j-i) (mod p)
Znaleźliśmy!
k = j-i jest (nie koniecznie jedynym) rozwiązaniem.
Post by osobliwy nick
Post by bartekltg
Pomyśl o tym w ten sposób.
Iterując 'do tyłu' dostaje ciąg
1 a,b,... y, z, 1.
^ |
Doszedłem do jedynki. Zawsze dojdę.
Tu nie wiem, czy się zgodzić, czy nie - bo dowodu na "zawsze dojdę do 1" mi wciąż brakuje.
Udowodniłeś, że zawsze istnieje takie k, że 2^k=1 (mod p), a nie, że zawsze dojdziesz do jedynki. Co z tego, że będzie istniało takie k, że 2^k=1 (mod p), jeśli nasz ciąg wpadnie w pętlę (to tylko przykład):

1
22
11
.
.
.
3
23
33
38
19
31
37
40
20
10
5
24
12
6
3

i nigdy nie dojdzie do 1. I pewnie odpiszesz, że nie wpadnie, bo zawsze istnieje takie k? Ale mamy udowodnić, że ciąg osiągnie jedynkę po tych k iteracjach, a nie, że istnieje takie k.

Ogólnie pytam o ten Twój dowód, bo jest szybki i dosyć prosty. Ja natomiast znalazłem zupełnie inny dowód, że czas stopu t=ord_p(2), ale odwołuje się on do trochę bardziej skomplikowanych twierdzeń związanych z ciągiem collatza oraz z ciągami typu px+q. Fajnie by było gdyby dało się to udowodnić prościej i szybciej, ale na razie mi się to ciągle nie zgadza.
bartekltg
2016-04-28 15:02:16 UTC
Permalink
W dniu środa, 27 kwietnia 2016 19:16:32 UTC+2 użytkownik
Post by bartekltg
Post by bartekltg
Post by bartekltg
Już pisałem o tym, nie używaj sformułowania "pierwsza lub
pseudopierwsza". To tak jakbyś mówił owoce i jakbłka.
Każda pierwsza jest pseudopierwsza.
Zgadza się.
Post by bartekltg
A co do meritum, to przecież o tym jest ten dowód sprzed 3
lat. [Od razu zakładam, że p jest nieparzyste. ]
Zaczynamy od 1 i iterujemy Twoim wzorkiem. To jest to
samo, jakbyśmy 'od tyłu' iterowali moim wzorkiem.
Zgadza się, ale bez dowodu, że odwrócona funkcja nie może
być rozbieżna
Oj, proste rzeczy zostawia się czytylnikowi;p
Prosty okazał się tylko przypadek rozbieżności (dla mnie).
Post by bartekltg
Obie funkcje przeoprowadzają zbiór P = {0,1,2... p-1} na samego
siebie.
Zgadza się.
Post by bartekltg
Post by bartekltg
oraz, że żadna z funkcji nie wpadnie w jakąś inną pętlę,
To jest objęte przez dowód.
Post by bartekltg
nie zwierającą liczby 1, nie można stwierdzić czy uzyskamy
"od przodu" i "od tyłu" te same ciągi. Tak mi się wydaje.
1,...,3,8,3,8,...
a iterując "w tył"
1,...,5,9,12,5,9,12,...
Nie, nie można. Twoja operacja to mnożenie przez element
odwrotny do 2.
Pomyśl o tym w ten sposób. Iterując 'do tyłu' dostaje ciąg 1
a,b,... y, z, 1. ^ | Doszedłem do jedynki. Zawsze
dojdę.
Tu nie wiem, czy się zgodzić, czy nie - bo dowodu na "zawsze
dojdę do 1" mi wciąż brakuje.
Dowód na to, że istnieje takie k, że 2^k =1 (mod p)
[p nieparzyste]
Był, jest na wiki i gdziekolwiek nie zerkniesz. Myślałem, zę to
oczywiste, skoro no godzisz się na nazywanie naszych działń w tył
grupą (a więc przez to i w przód:), w końcu w każdej grupie
skonczonej jesli będziesz potęgować jakiś element, w koncu
dostaniesz element neutralny (u nas jedynkę).
Rozpatrzmy kolejne potęgi 2 (czyli kolejne wyrazy z rekuerencji
x_{n+1} == 2*x_n ; x_0==1 )
2^n =1 (mod p)
Oczywiście są to liczby naturalne < p.
Jest więc ich co najwyżęj p. Jeśli popatrzysz na pierwsze p+1
elementów, na pewno znajdą się tam dwie takie same liczby. Niech
bądą to liczby o indeksach i oraz j. j>i
2^i = 2^j (mod p)
2^i = 2^i * 2^(j-i) (mod p)
Skracamy co trzeba (możemy to zrobić modulo p, jesli p jest
nieparzyste).
1 = 2^(j-i) (mod p)
Znaleźliśmy! k = j-i jest (nie koniecznie jedynym) rozwiązaniem.
Nie o to mi chodziło, ten dowód rzeczywiście jest już dawno znany i
Post by bartekltg
Pomyśl o tym w ten sposób. Iterując 'do tyłu' dostaje ciąg 1
a,b,... y, z, 1. ^ | Doszedłem do jedynki. Zawsze
dojdę.
Tu nie wiem, czy się zgodzić, czy nie - bo dowodu na "zawsze
dojdę do 1" mi wciąż brakuje.
Udowodniłeś, że zawsze istnieje takie k, że 2^k=1 (mod p), a nie, że
zawsze dojdziesz do jedynki.
Przecież to to samo.
Wyrazy ciągu wstecz to
1, 2 (mod p), 2^1 (mod p), 2^2 (mod p), 2^3 (mod p), 2^4 (mod p), ...
Ale mamy udowodnić, że ciąg osiągnie jedynkę
po tych k iteracjach, a nie, że istnieje takie k.
A jaka to różnica. Jeśli istenije takie k, że osiagnie
po nich '1', to osiagfnie 1 po k ruchach.

Może chodziło Ci, że osiagnie 1 po dokłądnie (p-1) ruchach
(byc może wcześniej).
To jest w dalszej części dowodu.
Ogólnie pytam o ten Twój dowód, bo jest szybki i dosyć prosty. Ja
natomiast znalazłem zupełnie inny dowód, że czas stopu t=ord_p(2),
ale odwołuje się on do trochę bardziej skomplikowanych twierdzeń
związanych z ciągiem collatza oraz z ciągami typu px+q. Fajnie by
było gdyby dało się to udowodnić prościej i szybciej, ale na razie mi
się to ciągle nie zgadza.
To przejrzyj ten dowód powoli na spokojnie.

Obok podrzuciłem jeszcze prostszy. Można nie bawić się w ciągi
odwrotne, tylko od razu zauważyć, że Twoja operacja to mnożenie
przez (p+1)/2 (mod p).

pzdr
bartekltg
osobliwy nick
2016-05-05 20:12:54 UTC
Permalink
Post by bartekltg
W dniu środa, 27 kwietnia 2016 19:16:32 UTC+2 użytkownik
Post by bartekltg
Post by bartekltg
Post by bartekltg
Już pisałem o tym, nie używaj sformułowania "pierwsza lub
pseudopierwsza". To tak jakbyś mówił owoce i jakbłka.
Każda pierwsza jest pseudopierwsza.
Zgadza się.
Post by bartekltg
A co do meritum, to przecież o tym jest ten dowód sprzed 3
lat. [Od razu zakładam, że p jest nieparzyste. ]
Zaczynamy od 1 i iterujemy Twoim wzorkiem. To jest to
samo, jakbyśmy 'od tyłu' iterowali moim wzorkiem.
Zgadza się, ale bez dowodu, że odwrócona funkcja nie może
być rozbieżna
Oj, proste rzeczy zostawia się czytylnikowi;p
Prosty okazał się tylko przypadek rozbieżności (dla mnie).
Post by bartekltg
Obie funkcje przeoprowadzają zbiór P = {0,1,2... p-1} na samego
siebie.
Zgadza się.
Post by bartekltg
Post by bartekltg
oraz, że żadna z funkcji nie wpadnie w jakąś inną pętlę,
To jest objęte przez dowód.
Post by bartekltg
nie zwierającą liczby 1, nie można stwierdzić czy uzyskamy
"od przodu" i "od tyłu" te same ciągi. Tak mi się wydaje.
1,...,3,8,3,8,...
a iterując "w tył"
1,...,5,9,12,5,9,12,...
Nie, nie można. Twoja operacja to mnożenie przez element
odwrotny do 2.
Pomyśl o tym w ten sposób. Iterując 'do tyłu' dostaje ciąg 1
a,b,... y, z, 1. ^ | Doszedłem do jedynki. Zawsze
dojdę.
Tu nie wiem, czy się zgodzić, czy nie - bo dowodu na "zawsze
dojdę do 1" mi wciąż brakuje.
Dowód na to, że istnieje takie k, że 2^k =1 (mod p)
[p nieparzyste]
Był, jest na wiki i gdziekolwiek nie zerkniesz. Myślałem, zę to
oczywiste, skoro no godzisz się na nazywanie naszych działń w tył
grupą (a więc przez to i w przód:), w końcu w każdej grupie
skonczonej jesli będziesz potęgować jakiś element, w koncu
dostaniesz element neutralny (u nas jedynkę).
Rozpatrzmy kolejne potęgi 2 (czyli kolejne wyrazy z rekuerencji
x_{n+1} == 2*x_n ; x_0==1 )
2^n =1 (mod p)
Oczywiście są to liczby naturalne < p.
Jest więc ich co najwyżęj p. Jeśli popatrzysz na pierwsze p+1
elementów, na pewno znajdą się tam dwie takie same liczby. Niech
bądą to liczby o indeksach i oraz j. j>i
2^i = 2^j (mod p)
2^i = 2^i * 2^(j-i) (mod p)
Skracamy co trzeba (możemy to zrobić modulo p, jesli p jest
nieparzyste).
1 = 2^(j-i) (mod p)
Znaleźliśmy! k = j-i jest (nie koniecznie jedynym) rozwiązaniem.
Nie o to mi chodziło, ten dowód rzeczywiście jest już dawno znany i
Post by bartekltg
Pomyśl o tym w ten sposób. Iterując 'do tyłu' dostaje ciąg 1
a,b,... y, z, 1. ^ | Doszedłem do jedynki. Zawsze
dojdę.
Tu nie wiem, czy się zgodzić, czy nie - bo dowodu na "zawsze
dojdę do 1" mi wciąż brakuje.
Udowodniłeś, że zawsze istnieje takie k, że 2^k=1 (mod p), a nie, że
zawsze dojdziesz do jedynki.
Przecież to to samo.
Wyrazy ciągu wstecz to
1, 2 (mod p), 2^1 (mod p), 2^2 (mod p), 2^3 (mod p), 2^4 (mod p), ...
Ale mamy udowodnić, że ciąg osiągnie jedynkę
po tych k iteracjach, a nie, że istnieje takie k.
A jaka to różnica. Jeśli istenije takie k, że osiagnie
po nich '1', to osiagfnie 1 po k ruchach.
Może chodziło Ci, że osiagnie 1 po dokłądnie (p-1) ruchach
(byc może wcześniej).
To jest w dalszej części dowodu.
Ogólnie pytam o ten Twój dowód, bo jest szybki i dosyć prosty. Ja
natomiast znalazłem zupełnie inny dowód, że czas stopu t=ord_p(2),
ale odwołuje się on do trochę bardziej skomplikowanych twierdzeń
związanych z ciągiem collatza oraz z ciągami typu px+q. Fajnie by
było gdyby dało się to udowodnić prościej i szybciej, ale na razie mi
się to ciągle nie zgadza.
To przejrzyj ten dowód powoli na spokojnie.
Obok podrzuciłem jeszcze prostszy. Można nie bawić się w ciągi
odwrotne, tylko od razu zauważyć, że Twoja operacja to mnożenie
przez (p+1)/2 (mod p).
pzdr
bartekltg
Ok. Mam jeszcze pewne uwagi, ale nie chcę ich ciągnąć w nieskończoność.

Podsumowując okazało się, że obliczanie najmniejszego n, takiego, że liczba p dzieli 2^n-1 okazało się dosyć łatwe. Tym łatwiej to zrobić gdy liczba p jest gładka, stosując redukcję Pohliga-Hellmana.

Ale to dopiero pierwszy przypadek z całego zbioru problemów i funkcji.

A jak znaleźć najmniejszą liczbę Pierponta postaci 2^a*3^b-1, taką, że p dzieli tę liczbę? Pomijając przypadki p=2^a*3^b-1 oraz p=3^n, bo pierwszy przypadek jest trywialny, a drugi jest równoważny znalezieniu ord_p(2).

Wydaje się, że dla dowolnej liczby p musimy przetestować wszystkie kombinacje liczb 2^a*3^b-1 mniejszych od p (i sprawdzać podzielność przez p), których jest wiele dla dużych p. Podobnie problem staje się skomplikowany dla liczb Pierponta postaci p1^n1 * p2^n2 * ... * pk^nk-1. Ilość kombinacji szybko rośnie. Redukcja Pohliga-Hellmana chyba się tu nie sprawdzi, metoda brute force może trwać latami już dla liczb postaci p1^n1*p2^n2*...*p15^nk oraz dla zadanego (nietrywialnego) p rzędu powiedzmy 2^50.

Problem można rozwiązać iterując analogiczną funkcję dla x=1:

0,5x+p - gdy x nie dzieli się przez p1,p2,...,pk
(0,5x+p)/p1 - gdy x jest podzielne przez p1
(0,5x+p)/p2 - gdy x jest podzielne przez p2
.
.
.
(0,5x+p)/pk - gdy x jest podzielne przez pk

w ciągu n1+n2+...+nk iteracji. To na razie hipoteza z mojej strony, ale poszukam dowodu. No chyba, że da się go przeprowadzić tak samo łatwo jak w przypadku tej podstawowej funkcji do obliczania ord_p(2), ale chyba się nie da, bo test Fermata nie ma tu zastosowania.
osobliwy nick
2016-05-10 22:39:04 UTC
Permalink
Ok. Mam jeszcze pewne uwagi, ale nie chcę ich ciągnąć w nieskończoność.

Podsumowując okazało się, że obliczanie najmniejszego n, takiego, że liczba p dzieli 2^n-1 okazało się dosyć łatwe. Tym łatwiej to zrobić gdy liczba p jest gładka, stosując redukcję Pohliga-Hellmana.

Ale to dopiero pierwszy przypadek z całego zbioru problemów tego rodzaju i funkcji. Szczególnie ciekawy wydaje się przypadek liczb Pierponta. Jak znaleźć na przykład najmniejszą liczbę Pierponta postaci 2^a*3^b-1, taką, że p dzieli tę liczbę? Pomijając przypadki p=2^a*3^b-1 oraz p=3^n, bo pierwszy przypadek jest trywialny, a drugi jest równoważny znalezieniu ord_p(2). Wydaje się, że dla dowolnej liczby p musimy przetestować wszystkie kombinacje liczb 2^a*3^b-1 mniejszych od 2^ord_p(2) (i sprawdzać podzielność przez p), a jeżeli nie znajdziemy takiej liczby uznać za rozwiązanie 2^ord_p(2)-1. Dla dużych p pojawia się wiele kombinacji do przetestowania. Problem zwykle można rozwiązać iterując analogiczną funkcję dla x=1:

0,5x+p/2 - gdy x nie dzieli się przez 2 i 3
(0,5x+p)/3 - gdy x jest podzielne przez 3
(0,5x+p)/2 - gdy x jest podzielne przez 2

w ciągu a+b iteracji (przy czym "b" to ilość dzieleń przez 3 oraz "a" to ilość mnożeń z dodawaniem + dzieleń przez 2). Funkcja jednak nie zapętli się dla x=1 dla dowolnego p (np. dla p=83 wpada w pętlę liczby 3). Dowód, że funkcja faktycznie oblicza "ord" (a raczej uogólnienie ord) oparty na teście Fermata raczej się tu nie sprawdzi, podobnie redukcja Pohliga-Hellmana wydaje się nie mieć tu zastosowania. Z tego co widzę można udowodnić, że pętle tego rodzaju występują w ciągach dla p=2^a*3^b-1 dla dowolnej nieparzystej liczby m, gdy spełnione są któreś z "a-1" równań:

m = 2^a1*3^b1

lub

m = 2^a1*3^b1 + 2^a2*3^b2

lub

...

m = 2^a1*3^b1 + 2^a2*3^b2 + ... + 2^ak*3^bk

oraz a1,a2,...,ak należą do [0,a], b1,b2,...,bk należą do [0,b] i a1>=a2>=...>=ak, b1>=b2>=...>=bk

Oraz, że dla dowolnego p=(2^a*3^b-1)/c rozwiązania wystąpią, tylko gdy znajdziemy takie całkowite m, że:

m = 2^a1*3^b1 * 1/c

lub

m = 2^a1*3^b1 + 2^a2*3^b2 * 1/c

lub

...

m = 2^a1*3^b1 + 2^a2*3^b2 + ... + 2^ak*3^bk * 1/c

Trudno stwierdzić dla których p zawsze znajdziemy rozwiązanie takie, że m=1 oraz ile iteracji trzeba ostatecznie wykonać, by uzyskać wynik.

Dygresja:
----------------------------------------------------------------------------
Problem jest bardzo podobny do problemu Collatza, gdyż pętle dla liczb nieparzystych w ciągach typu 3n+(2^(x+y)-3^y) występują, gdy istnieją rozwiązania:

n = 2^x1*3^0 + 2^x2*3^1 + ... + 2^xk*3^yk

x1,...xk należą do [0,x] oraz x1>=...>=xk - jeżeli jednak będziemy rozpatrywać także pętle liczb parzystych warunek z nierównościami nie musi być uwzględniony.

Dla dowolnego q=(2^(x+y)-3^y)/c rozwiązania wystąpią, tylko gdy znajdziemy całkowite n, takie, że:

n = 2^x1*3^1 + 2^x2*3^2 + ... + 2^xk*3^yk * 1/c

Jeżeli chcemy udowodnić słabą hipotezę Collatza trzeba udowodnić, że istnieje tylko jedno rozwiązanie całkowite powyższego równania dla c=2^(x+y)-3^y (problem pozostaje otwarty, a równanie w powyższej postaci pierwszy raz opublikowali Böhm i Sontacchi (1978) w pracy "On the existence of cycles of given length in integer sequences like x_{n+1} =x_n/2 if x_n even, and x_{n+1} =3x_n +1 otherwise").
----------------------------------------------------------------------------

Podobnie problem staje się skomplikowany dla liczb Pierponta postaci p1^n1 * p2^n2 * ... * pk^nk-1. Ilość kombinacji szybko rośnie. Redukcja Pohliga-Hellmana chyba się tu nie sprawdzi, metoda brute force może trwać latami już dla liczb postaci p1^n1*p2^n2*...*p15^nk oraz dla zadanego (nietrywialnego) p rzędu powiedzmy 2^50.

Problem można rozwiązać iterując analogiczną funkcję dla x=1:

0,5x+p - gdy x nie dzieli się przez p1,p2,...,pk
(0,5x+p)/p1 - gdy x jest podzielne przez p1
(0,5x+p)/p2 - gdy x jest podzielne przez p2
.
.
.
(0,5x+p)/pk - gdy x jest podzielne przez pk

prawdopodobnie zwykle w ciągu n1+n2+...+nk iteracji. Jednak, jeżeli okaże się, że x=1 się nie zapętla będzie należało wykonać więcej iteracji, dotąd, aż dowolna inna liczba się zapętli.

Ogólnie powyższe funkcje są częścią jeszcze szerszego zagadnienia związanego z obliczaniem logarytmów dyskretnych. Być może istnieje metoda pozwalająca użyć ich w jakiś sposób, aby obliczyć powiedzmy 6^n=1 mod p (czyli 2^a*3^b-1). Funkcja dla p1=2 i p2=3 prawdopoodbnie nigdy nie zwróci a=b. Ale gdyby rozważać liczby 2^a*3^b*5^c*...-1, być może niektóre rozwiązania byłyby postaci 6^n-1. Trudno powiedzieć.

Te funkcje są jednak częścią jeszcze ogólniejszego problemu znajdowania rozwiązań:

p1^n1*p2^n2*...*pk^nk - t^y = r mod p

dla funkcji postaci:

t/2*x + p/2 gdy x nie dzieli się przez p1,p2,...,pk
(t/2*x+p)/p2 - gdy x jest podzielne przez p2
.
.
.
(t/2*x+p)/pk - gdy x jest podzielne przez pk

Podobnie można rozważać rozwiązania:

t^y - p1^n1*p2^n2*...*pk^nk = r mod p

dla ujemnych x w powyższej funkcji.

Funkcje będą słabo nadawały się do obliczeń jeżeli będą zwracały ciągi rozbieżne do nieskończoności. Tak jest na przykład dla funkcji 2^n-t^y = r mod p, gdy t jest większe od 3 (na to przynajmniej wygląda, bo rozbieżność tych ciągów pozostaje hipotezą, ponadto dowód, że wszystkie ciągi tej postaci dla t=3 są zbieżne byłby dowodem, że w ciągu Collatza nie ma ciągów rozbieżnych do nieskończoności). Wygląda na to, że wszystkie funkcje:

t/2*x + p/2 gdy x nie dzieli się przez p1,p2,...,pk
(t/2*x+p)/p2 - gdy x jest podzielne przez p2
.
.
.
(t/2*x+p)/pk - gdy x jest podzielne przez pk

takie, że p1,p2,...,pk to kolejne liczby pierwsze mniejsze od t będą zawierały tylko zbieżne ciągi (ciąg Collatza zalicza się do tych ciągów), przy czym zbiór p1,...,pk może być także większy niż zbiór liczb pierwszych mniejszych od t, ważne by zawierał wszystkie te liczby. Dla tych ciągów możemy całkiem skutecznie wyznaczać najmniejsze n1,n2,...,nk. Oczywiście to, że będą to akurat najmniejsze n1,n2,...,nk to tylko hipoteza jak na razie. Wydaje się, że ciągi, które dla wszystkich x dają ciągi wyglądające na rozbieżne do nieskończoności (i prawdopodobnie rzeczywiście rozbieżne - co już trudniej udowodnić) spełniają równanie:

t^y/(p1^n1*p2^n2*...*pk^nk) + t^(y-1)/(p1^n1*p2^n2*...*pk^nk) < 1

dla najmniejszych możliwych parametrów, przy wybranym p.
bartekltg
2016-04-28 14:55:10 UTC
Permalink
On 28.04.2016 00:02, bartekltg wrote:


Gdzieś o tym napomknąłem, ale chyba warto to napisać wyraźniej.

Iteracja

f(x) = (x+p)/2 dla x nieparzystych
= x/2 dla parzystych


Jest równoznaczna z dziłaniem

f2 (x) = x * 2^-1 (mod p)

Co więcej, możemy napisać 2^-1 bezpośrednio:

f2 (x) = x * ((1+p)/2) (mod p)


((1+p)/2) jest liczbą naturalną (bo p nieparzyste)
mniejszą niż p (z grubsza o połowę).

Wypadało by tpo udowodnić.

Dla parzystego:

x = 2k
f2(x) = 2k* ((1+p)/2) = k (1+p) = k + k*p = k = x/2 (mod p)

Dla nieparzystego:

x = 2k +1
f2(x) = (2k +1)* ((1+p)/2) = 2k* ((1+p)/2) + (1+p)/2 =
= k (1+p) + (1+p)/2 = k + k*p + ((1+p)/2) = k + (1+p)/2=
(x-1)/2 + (1+p)/2 = (x-1 + 1 - p)/2 = (x + p)/2 (mod p)

Więc f(.) == f2(.) na zbiorze {0,1...p}
[Pisaliśmy o tym poprzednio, f przeprowadza x<p na f(x)<p,
Oznacza to, że modulo nam nie przeszkadza i wzorki są tożsame].


Za darmo mamy więc cykliczność (i ejdnoznaczność cyklu) oraz
wystąpienie w nim jedynki.

Twoja hipoteza tłumaczy się na 'p jest pseudopierwsze przy podstawie
(p+1)/2'. Poprzedni doiwód z ciagami wstecz można wykorzystać by
pokazać, że jest to równoznaczne pseudopierwszosći przy podstawie 2.

pzdr
bartekltg
osobliwy nick
2020-01-26 03:22:48 UTC
Permalink
Ok, o ile dobrze rozumiem tę pracę, to oni rozważają klasy równoważności ciągów zdefiniowanych funkcjami:

f(x) = m*x+a - gdy x jest nieparzyste
f(x) = x/d - gdy x jest nieparzyste

Dla m=1 (te przypadki interesują ich przez prawie całą pracę). Ja zaś rozważałem te same funkcje, tyle, że dla d=2 i z dodatkowym dzieleniem, które możemy wprowadzić, gdy d=2:


f(x) = x/2+a/2 - gdy x jest nieparzyste
f(x) = x/2 - gdy x jest nieparzyste

Przez te klasy równoważności oni rozumieją unikalne pętle dla różnych początkowych x. Ja rozważałem zawsze x startowe wynoszące 1. Ale możemy też iterować dla innych x. I czasami otrzymamy dokładnie te same pętle (np. dla x=1 ciąg zawsze powraca po pewnej liczbie iteracji do 1), a czasami inne (np. dla x=3 ciąg może przebiegać po różnych liczbach i nigdy nie osiągnąć 1, ani żadnej liczby z pętli dla x=1).

Ogólnie z tego co widzę liczba unikalnych pętli dla danego "a" zależy od najmniejszej potęgi e, takiej, że 2^e-1 jest podzielne przez a. Mianowicie liczba tych pętli wynosi (a-1)/t, gdzie "t" to czas stopu, który był zdefiniowany już w tym wątku. Oni podają wzór na tę liczbę tych pętli w oparciu o tocjent eulera (też zauważyłem, że te funkcje mają związek z tą funkcją) i właśnie liczbę e. Nie do końca rozumiem te ich wzory. Zwłaszcza nie jest pewien czy dobrze mi się wydaje czym jest ksi(a,d). Ale już te kilka lat temu odkryłem zasadę obliczania:

ksi(a,d)=(a-1)/t
Post by o***@interia.pl
a_1^(n_1-1)*a_2^(n_2-1)*...*a_n^(n_n-1)*x
przy czym x to czas stopu liczby a_1*a_2*...*a_n pozbawiony czynników a_1^(n_1-1), a_2^(n_2-1), ..., a_n^(n_n-1) (o ile takie ma).
Natomiast dowolna złożona liczba a_1*a_2*...*a_n ma czas stopu będący iloczynem najwyższych potęg różnych liczb które występują w czasach stopów tych liczb. Np. liczba 13 ma t=12=4*3, a liczba 17 ma t=8. Najwyższa potęga dwójki w tych czasach to 8, a trójki 3, dla liczby 13*17 mamy zatem czas stopu 3*8=24.
3 ma czas 2
5 ma czas 4
7 ma czas 3
11 ma czas 10 --> 5
13 ma czas 12
17 ma czas 8 --> 8
19 ma czas 18 --> 9
najwyższe potęgi jakie znaleźliśmy to 8,9,5, mamy zatem 8*9*5=360.
3 -> t=2
5 -> t=4
7 -> t=3
11 -> t=10
Najwyższa potęga dwójki wśród tych czasów to 4, trójki to 3 oraz piątki to 5, innych nie ma. Wstępnie zatem mamy 4*3*5, jednak wyrzucamy piątkę ponieważ występuje we wcześniejszym wzorze. Ostatecznie mamy czas stopu równy 5*7^2*11^3*4*3=3913140. Ogólnie wykonaliśmy 19 iteracji, zamiast 3913140.
11^4*19^2
Wstępnie mamy: 11^3*19*t.
11 -> 10
19 -> 18
Najwyższe potęgi to 2,9,5. Żadna nie występuje we wzorze wyżej, mamy zatem czas stopu 11^3*19*2*9*5=2276010. Ogólnie wykonaliśmy 28 iteracji zamiast 2276010.
Generalnie, aby sprawdzić czas stopu dowolnej liczby a_1^(n_1)*a_2^(n_2)*...*a_n(^n_n), należy wykonać co najwyżej a_1+a_2+...+a_n iteracji (w praktyce mniej, bo liczby pierwsze mają także czasy stopów mniejsze niż one same) no i doliczyć do tego operacje na czasach stopów tych liczb (rozbicie na czynniki pierwsze, znalezienie najwyższych potęg oraz odrzucanie niektórych czynników). Ten algorytm pozwala drastycznie obniżyć złożoność podczas testowania liczb "d" o odpowiednio "dużej" złożoności. Natomiast będzie miał problem z testowaniem pojedynczych liczb pierwszych lub liczb w ogóle o niewielu dużych czynnikach pierwszych.
Już wtedy zauważyłem, że, jeżeli dostaniemy do obliczenia t, czy definiowane przez autorów ksi(a,d) dla liczb, które nie są gładkie, to nie da się tego szybko policzyć (względem rozmiaru liczby). Autorzy zauważają, że ten fakt może posłużyć do stworzenia kryptografii klucza publicznego. Jeśli mamy liczbę n=p*q, to możemy policzyć t dla p i q, choćby według mojego algorytmu albo tego co oni zapisali jawnie we wzorach na ksi(a,d) (o ile dobrze ich rozumiem i chodzi o to samo), natomiast bez znajomości faktoryzacji liczby n obliczenie t będzie trudniejsze. Dowolna złożona liczba a_1*a_2*...*a_n ma czas stopu będący iloczynem najwyższych potęg różnych liczb które występują w czasach stopów tych liczb. Np. liczba 13 ma t=12=4*3, a liczba 17 ma t=8. Najwyższa potęga dwójki w tych czasach to 8, a trójki 3, dla liczby 13*17 mamy zatem czas stopu 3*8=24. Normalnie musielibyśmy zamiast rozwiązać ten problem - policzyć, czy ustalić metodą brute force, za pomocą szybkiego potęgowania z działaniem modulo wartość dla liczby 13*17, która wynosi 24, a tak możemy ustalić, że dla 13 mamy t=12, zaś dla 17 t=8. W najgorszym przypadku dla liczby p*q musimy sprawdzić p-1 potęg oraz q-1 potęg. Zaś, jeśli nie znamy faktoryzacji liczby musimy sprawdzić p*q-1 potęg. Czyli sprawdzać po kolei czy liczba 2^e-1 dla e=1,2,3,..., 220 jest podzielna przez a=13*17. To jest niewielka oszczędność. Jeśli liczby są podobnej wielkości, a powinny być, to zamiast n=p*q operacji możemy wykonać około 2*n^0,5 operacji. Niewielka to przewaga nad atakującym, nawet, gdyby dało się to jakoś wykorzystać w kryptografii klucza publicznego. Atakujący musi sprawdzić n potęg, a my, żeby ustalić interesujący nasz parametr około 2*n^0,5. Skoro 2*n^0,5 liczb można przetestować w rozsądnym czasie, to można też przetestować i n liczb. Oczywiście autorzy rozważają szerszy zbiór funkcji, dla których d nie jest równe wyłącznie 2. Być może dla tych funkcji jest jakaś nadzieja? Dla funkcji rozważanych przeze mnie w tym wątku nie widzę na to perspektyw.
Loading...