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
dla rozmiaru pamieci przy tych dzialaniach. Czy te wyniki mozna potwierdzic?