Dział zablokowany Ten wątek jest zablokowany. Nie możesz w nim pisać ani edytować postów.  [ Posty: 2 ] 
algorytm do rozpoznania zlozonosci 
Autor Wiadomość

Dołączył(a): 13 paź 2011, o 09:39
Posty: 3
Post algorytm do rozpoznania zlozonosci
Opracowalem algorytm mogacy sluzyc pomoca w rozkladzie na liczby pierwsze. Szokuje mnie swoim dzialaniem. Dlatego chce skonsultowac jego zlozonosc. Dzialania arytmetyczne dzialaja liniowo.

Algorytm przejscia z systemu o podstawie n-2 na system o podstawie n liczby majacej r cyfr. Zwraca znalezione dzielniki, modyfikujac przeksztalcana liczbe.
Dane
Liczba a[r]; //tablica 'cyfr' calkowitoliczbowych (system dowolny), w praktyce sa to liczby -1 < a[i] < n-2, dla -1 < i < r

Algorytm:
Wejscie: n=3, dlugosc r, tablica a[i], -1 < a[i] < 3, dla -1 < i r powstale z zapisu trojkowego liczby a w odwrotnej kolejnosci
[code=cpp]
while(r>2) {
n = n+2;
j=0;
while( j<r ) {
j++;
t=0;
for( k=r-j-1; r-1>k; k++) {
a[k] = a[k] = a[k+1] - a[k+1] - t;
t=0;
while( 0>a[k] ) { a[k] += n; t++; }
}
a[r-1] -= t;
}
while( !a[0] ) { erase(a[0]); r--; dzielnik.push(n); }
}
dzielnik.push(a[0]*n+a[1]);
[\code]

Przykład rozkladu: 143 = 1000 1111 binarnie, 12022 trojkowo, pojawiaja się wartosci tablicy wyswietlane od a[0]:
2 2 0 2 1
3 3 0 1
3 6 2
8 6 1
0 2 1
wyjscie z wartoscia kolejnego dzielnika '2 1' przy podstawie 11, czyli 1*11+2=13.

Algorytm zachowuje sie bardzo ciekawie w okolicy dzielnikow uwazanych za 'dobre' w RSA. Swoja moc pokazuje dopiero dla większych liczb, testowalem np. dla 169 747 007 (30 bitow).
Uzyskuje zlozonosc wielomianowa dla dzialan, zas liniowa :shock: dla rozmiaru pamieci przy tych dzialaniach. Czy te wyniki mozna potwierdzic?


13 paź 2011, o 11:04
Zobacz profil

Dołączył(a): 13 paź 2011, o 09:39
Posty: 3
Post Re: algorytm do rozpoznania zlozonosci
Uzyskałem informacje dodatkowe. To pozwala podać złożoność.
Załóżmy, że działamy na bardzo dużej liczbie n.
Po przygotowaniu liczby dysponuję tablicą wartości mającej k = log_3 n pozycji. Pętle główne wykonują się k(k-1) razy, zatem mam złożoność O( k^2 ). Operacje wewnątrz pętli to głównie odejmowanie o złożoności liniowej względem długości, która nie przekracza pierwiastka kwadratowego z n.
Kiedy przechodzę dla r równego 2, pozostałe pętle można łatwo zlikwidować.
Zatem złożonośc tego kawałka jest równa
O( n^(1/2) k^2 ) = O( n^(1/2) log^2 n )

Algorytm służy do faktoryzacji, i wystarczy pierwiastek z n przekształceń, by sprawdzić między innymi wszystkie liczby pierwsze podejrzane o bycie dzielnikami.
Ostatecznie można rozkładać liczby ze złożonością podsześcienną, dokładniej:
O( n log^2 n )
W innych podejściach złożoność ta jest wykładnicza.


30 kwi 2012, o 12:55
Zobacz profil
Wyświetl posty nie starsze niż:  Sortuj wg  
Dział zablokowany Ten wątek jest zablokowany. Nie możesz w nim pisać ani edytować postów.  [ Posty: 2 ] 


Kto przegląda forum

Użytkownicy przeglądający ten dział: Brak zidentyfikowanych użytkowników i 1 gość


Nie możesz rozpoczynać nowych wątków
Nie możesz odpowiadać w wątkach
Nie możesz edytować swoich postów
Nie możesz usuwać swoich postów
Nie możesz dodawać załączników

Szukaj:
Skocz do:  
cron


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group. Forum style based on STSoftware Hestia.
Przyjazne użytkownikom polskie wsparcie phpBB3 - phpBB3.PL