(nowy) algorytm poszukiwania liczb pierwszych

[omnia_...@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)?

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]

W dniu 2013-03-03 09:42, omnia_...@interia.pl pisze:

> 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

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.

> 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

d to badana liczba?

> 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ś?

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

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

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

W dniu 2013-03-03 16:17, Marcin pisze:

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

[omnia_...@interia.pl]

> d to badana liczba?

Tak.

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

> 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ść?

[omnia_...@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.

[bartekltg]

W dniu 2013-03-03 17:09, omnia_...@interia.pl pisze:

>> d to badana liczba?
>
> Tak.
>
>> 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.
>
>> 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.

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

> 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

[bartekltg]

W dniu 2013-03-03 18:11, omnia_...@interia.pl pisze:

Od kilkunastu minut wysyłasz tego samego posta.
Trafił tu już chyba 4 czy 5 raz. Ogarnij się i czytnik;>

pzdr
bartekltg

[omnia_...@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ą.

>
>
>
> To ile możę wynosić czas stopu? n*d.
>
> A co to oznacza? że musisz sykonać n*d kroków.
>
>
>
> > (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.

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

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

Osoba podpisana jako <omnia_...@interia.pl> w artykule
<news:645914d1-cdad-4542...@googlegroups.com> pisze:

>> 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 us...@pochta.onet.pl (zamień miejscami z<->h w adresie)
Grand Inquisitor pl.internet.pomoc Trust No.1 http://evil.pl/pip/

[omnia_...@interia.pl]

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.

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

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

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

Osoba podpisana jako <omnia_...@interia.pl> w artykule

<news:05c5e0b1-88dd-49eb...@googlegroups.com> pisze:

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

[omnia_...@interia.pl]

W dniu wtorek, 5 marca 2013 13:58:47 UTC+1 użytkownik Andrzej P. Wozniak napisał:
> Osoba podpisana jako <omnia_...@interia.pl> w artykule
>
> <news:05c5e0b1-88dd-49eb...@googlegroups.com> pisze:
>
>
>
> >> 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?

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

> 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ź?

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

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

> W miarę aktualną wersję netykiety znajdziesz tu:
>
> http://usenet.rox.pl/netykieta.html

Ta strona jest niedostępna.

> Inne ciekawe materiały znajdziesz tu: http://evil.pl/pip/

Dobrze, poszukam tam czegoś ciekawego.

[omnia_...@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ę wykres:

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

[bartekltg]

W dniu 2013-03-06 18:40, omnia_...@interia.pl pisze:

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

[omnia_...@interia.pl]

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]

W dniu 2013-03-06 20:14, omnia_...@interia.pl pisze:

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

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?

> 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

[omnia_...@interia.pl]

W dniu środa, 6 marca 2013 20:19:45 UTC+1 użytkownik bartekltg napisał:
> W dniu 2013-03-06 20:14, omnia_...@interia.pl pisze:
>
>
>
> >
>
> > 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.
>
>
>
>
>
> 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.

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

W dniu 2013-03-06 20:27, omnia_...@interia.pl pisze:

> W dniu środa, 6 marca 2013 20:19:45 UTC+1 użytkownik bartekltg
> napisał:
>> W dniu 2013-03-06 20:14, omnia_...@interia.pl pisze:
>>
>>
>>
>>>
>>
>>> 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.

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

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

W dniu 2013-03-06 22:55, bartekltg pisze:

> W dniu 2013-03-06 20:27, omnia_...@interia.pl pisze:
>> W dniu środa, 6 marca 2013 20:19:45 UTC+1 użytkownik bartekltg
>> napisał:
>>> W dniu 2013-03-06 20:14, omnia_...@interia.pl pisze:
>>>
>>>
>>>
>>>>
>>>
>>>> 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.
>
>>> 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
:)

[omnia_...@interia.pl]

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.

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

W dniu 2013-03-07 00:18, omnia_...@interia.pl pisze:

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

Widzę że jeszcze dalej walczysz z wiatrakami

bartekltg napisał:

> 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

> 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

[omnia_...@interia.pl]

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

W dniu 2013-03-03 09:42, omnia_...@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

[bartekltg]

W dniu 2013-03-07 09:19, omnia_...@interia.pl pisze:

Twoja procedura jest dokładnie tym, co sprawdzenie pseudopierwszości.
Obstawiam, że policzenie 2^(p-1) modulo p będzie szybsze.

> 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:
>
> 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!

Zaraz obok piszesz:

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

W dniu 2013-03-07 01:27, Oli pisze:

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

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

> 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? ;>

> Przypomina mi to znany rysunek Mleczki z czasów PRLu z podpisem " co by
> tu jeszcze spieprzyć"

Marudzisz dla marudzenia;>

pzdr
bartekltg

[bartekltg]

W dniu 2013-03-07 14:05, bartekltg pisze:

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

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

[Oli]

bartekltg napisał:

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

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

[omnia_...@interia.pl]

W dniu czwartek, 7 marca 2013 14:05:54 UTC+1 użytkownik bartekltg napisał:
> W dniu 2013-03-07 09:19, omnia_...@interia.pl pisze:
>
> >> 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.
>
>
>
>
>
> > 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:
>
> >
>
> > 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

> a czerwona krzywa jest bez sensu:/

To krzywa logarytmicznej regresji.

> Widać nawet wyraźnie linię y=x!

No tak, ale mimo wszystko większość czasów stopów znajduje się poniżej.

> Zaraz obok piszesz:
>
>
>
> > 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.

To jest średnia krocząca czasów stopów kolejnych liczb?

Ja mam tu:

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.


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]

W dniu 2013-03-07 19:53, Oli pisze:

> bartekltg napisał:
>
>> 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.

literówka, (x+2d)/3

>>
> Tutaj poniosła cię fantazja.

Bo?

> 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

[omnia_...@interia.pl]

W dniu czwartek, 7 marca 2013 14:42:57 UTC+1 użytkownik bartekltg napisał:
> W dniu 2013-03-07 14:05, bartekltg pisze:
>
> > 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.
>
>
>
>
>
> 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.

[bartekltg]

W dniu 2013-03-07 20:10, omnia_...@interia.pl pisze:

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.

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

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

>
> Ja mam tu:
>
> 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.

> 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

[omnia_...@interia.pl]

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

[omnia_...@interia.pl]

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

[Miroslaw Kwasniak]

bartekltg <bart...@gmail.com> wrote:
>> 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])) )

[Miroslaw Kwasniak]

Oli <Olisa...@aol.com> wrote:
> 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

[Miroslaw Kwasniak]

omnia_...@interia.pl wrote:
>> 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

[Miroslaw Kwasniak]

bartekltg <bart...@gmail.com> wrote:
> W dniu 2013-03-07 09:19, omnia_...@interia.pl pisze:

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

[omnia_...@interia.pl]

W dniu piątek, 8 marca 2013 09:01:35 UTC+1 użytkownik Miroslaw Kwasniak napisał:

> 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

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]

W dniu 2013-03-08 06:16, omnia_...@interia.pl pisze:

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

> 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

[omnia_...@interia.pl]

W dniu piątek, 8 marca 2013 11:04:33 UTC+1 użytkownik bartekltg napisał:
> W dniu 2013-03-08 06:16, omnia_...@interia.pl pisze:
>
> >> 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ść.

Ta wypowiedź i ta:

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

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

W dniu 2013-03-08 13:43, omnia_...@interia.pl pisze:

> W dniu piątek, 8 marca 2013 11:04:33 UTC+1 użytkownik bartekltg
> napisał:


>

> Ta wypowiedź i ta:
>
>>> 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:)

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.

> 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

[Oli]

Miroslaw Kwasniak napisał:

> Masz rację, efektywnośc jest kiepska (czasy uyskane w pari_gp):
>
> ? 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

[omnia_...@interia.pl]

No tak przejrzałem niektóre algorytmy, jeszcze nie wszystkie.

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

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

[Miroslaw Kwasniak]

pari-gp 2.5.1 C2D E8...@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]

Miroslaw Kwasniak napisał:

>>> ? f(1000003)
>>> time = 641 ms.
>>> %57 = 1000002
>>
>> jaką wersję pari 2.?.? uzywałeś i na jakiej maszynie to robiłeś bo czas jest rewelacyjny
>

> pari-gp 2.5.1 C2D E8...@3.00GHz pod linuksem 64bit.
>

No tak, tak myślałem pod linuksem, nowsza wersja pari i dobra maszyna dają dobre rezultaty

> A w dodatku kompilator gp2c daje jeszcze szybszy kod:
> 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

[bartekltg]

W dniu 2013-03-09 09:27, omnia_...@interia.pl pisze:

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

[omnia_...@interia.pl]

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.

[Miroslaw Kwasniak]

Oli <Olisa...@aol.com> wrote:
> 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 ;)

> 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

[osobliwy nick]

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 do momentu:

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

On 25.04.2016 22:45, osobliwy nick wrote:
> 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
> do momentu:
>
>> 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]

Poniżej cały cytat tamtego dowodu.

W dniu czwartek, 7 marca 2013 14:05:32 UTC+1 użytkownik bartekltg napisał:
> W dniu 2013-03-03 09:42, omnia_...@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

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.

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

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

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.

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

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

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

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

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

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

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

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

On 27.04.2016 18:19, osobliwy nick wrote:
>> 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ę.
>
>> 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

> oraz, że żadna z funkcji nie wpadnie w jakąś inną pętlę,

To jest objęte przez dowód.

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

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.

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

>>>> 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ć;>

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

W dniu środa, 27 kwietnia 2016 19:16:32 UTC+2 użytkownik bartekltg napisał:
> On 27.04.2016 18:19, osobliwy nick wrote:
> >> 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ę.
> >
> >> 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).

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

Zgadza się.

> > oraz, że żadna z funkcji nie wpadnie w jakąś inną pętlę,
>
> To jest objęte przez dowód.
>
> > 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,...
>
> 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.

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

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

To jest jasne, tylko doprecyzowałem, to co napisałeś wcześniej.

> >>>> 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ć;>
>
> >
> >> 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]

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]

Nie o to mi chodziło, ten dowód rzeczywiście jest już dawno znany i tu nie mam wątpliwości. Chodzi mi o to:

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

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










>

[bartekltg]

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]

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.

[osobliwy nick]

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.

Bartekltg znalazł na to dowód:

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