18 października 2011

faktoryzacja

W kontakcie z wroclawskim portalem informatycznym uzyskalem informacje, jak liczy sie zlozonosc algorytmow rozkladajacych liczbe na czynniki pierwsze.
Liczy sie je wedlug licznosci bitow (znakow), za pomoca ktorych mozna te liczbe przedstawic.

Moje wczesniejsze wyniki dotyczace zmian systemow liczbowych pozwalaja latwo faktoryzowac liczby. Sprawdzam, czy liczba jest podzielna przez 2, 3. Konwertuje na system trojkowy a nastepnie zwiekszam podstawe systemu. Algorytm jest liniowy wzgledem dlugosci liczby, kwadratowy wzgledem przeksztalcen.
Najmniej znaczaca cyfra rowna 0 wskazuje dzielnik. Kryterium stopu jest osiagniecie pierwiastka z liczby, co rozpoznaje po krotnosci 'cyfr'. Liczba 'dwucyfrowa' bez dzielnikow uzyskana w tym algorytmie jest pierwsza.

Oznacza to, ze dysponuje liniowym algorytmem faktoryzacji liczb!

19 komentarzy:

Anonimowy pisze...

Jaką największą liczbę można tym algorytmem rozłożyć na domowym komputerze?

jaNusz pisze...

Algorytm zmiany systemów liczbowych będący podstawą obliczeń jest podany w poście z 8 kwietnia 2011 roku
http://matformac.blogspot.com/2011/04/zmiany-systemow-liczbowych.html
oraz w poście z 28 stycznia 2012
http://matformac.blogspot.com/2012/01/dodatek-do-podzielnosci-w-systemach.html
Jeden z algorytmów faktoryzacji jest opisany 26 października 2012 roku
http://matformac.blogspot.com/2012/10/faktoryzacja-spradzajaca-duze-i-mae.html
Wszystkie z przykładami.

Ponieważ uzyskiwane wartości są rzędu podwojonej cyfry, możemy bez pomocy dodatkowych bibliotek rozkładać liczby mające nieco mniej niż dwa słowa maszynowe procesora, tzn. liczby 62-bitowe na procesorach 32-bitowych, 126-bitowe na procesorach 64-bitowych.
Mając dedykowane biblioteki wysokiej precyzji, np. gmp, można faktoryzować dowolne liczby mieszczące się w pamięci.

Anonimowy pisze...

GMP używałem.W języku python można operować bez dodatkowych bibliotek na dowolnych liczbach (ogranicza nas praktycznie tylko RAM). Ciekaw jestem co jest wydajniejsze.
Natomiast pytałem w sensie jak "daje radę" w stosunku do GNFS(bodajże obecnie najlepszego znanego algorytmu do rozkładu dużych liczb)?

Anonimowy pisze...

Jeszcze co do pytania o podanie przykładu.Zmianę systemu to ja rozumiem.
"Sprawdzam, czy liczba jest podzielna przez 2, 3"
Biorę liczbę 77 nie jest podzielna.
"Konwertuje na system trojkowy a..."
Konwertujemy liczbę 77 czy 2 i 3?
2 to 2, 3 to 10, 77 to 2212
"następnie zwiększam podstawę systemu"
Z tego co wiem zmiana podstawy systemu to to samo co zmiana systemu liczbowego.
"Najmniej znaczaca cyfra rowna 0 wskazuje dzielnik."
Czyli ta skrajnie na prawo.

Naprawdę prosiłbym o przykład bo algorytm jest bardzo ciekawy.

jaNusz pisze...

Jak algorytm sprawuje się w porównaniu z GNFS nie jestem w stanie sprawdzić, gdyż nie jestem w stanie napisać tak szybkich bibliotek, jakie są stosowane w tym sicie. Wiem tylko, że tamten algorytm zawiera dzielenie ogromnych liczb, które mocno spowalniają.
Algorytm bez dzielenia albo z dzieleniem mającym stosunkowo mały dzielnik/iloraz może być szybszy, z kolei sprawdzam wszystkie nieparzyste wartości.

Oczywiście przy rozkładzie konwertujemy liczbę rozkładaną.
Jeśli pragniesz rozkładu 77, proszę bardzo:
77 w trójkowym wygląda następująco:
2 2 1 2
konwersja z systemu p-r na system o podstawie p wg algorytmu:
na wejściu ciąg cyfr a[m], ..., a[1], a[0] systemu o podstawie p-r
for k=m-1 downto -1 step -1
foreach a[i] = a[i] - r*a[i+1], i>k
while not (-1<a[i]<p) { a[i] = a[i] +(-) p; a[i+1] = a[i+1]-(+)1; }
endfor

W ten sposób konwersja z systemu trójkowego na piątkowy wygląda następująco - separuję przez '|' cyfry używane od oczekujących:
2 2 | 1 2
2 2-2*2 | 1 2
2-1 -2+5 | 1 2
1 3 | 1 2
1 3-2*1 1-2*3 | 2
1 0 0 | 2
1 0-2*1 0-2*0 2-2*0
0 3 0 2
Oraz w piątkowym 77 wygląda jako 302.

Konwersja na siódemkowy 302: (r=2)
3 0 | 2
3 -6 | 2
2 1 | 2
2 -3 0
1 4 0
Jest dzielnik 7 oraz drugi równy (1*7+4) = 11.

Przy konwersjach o -3<r<3 mnożenie jest niepotrzebne.

Anonimowy pisze...

Chyba jestem tępy bo dalej nie rozumiem.
Czemu konwertujemy tylko na piątkowy i potem siódemkowy?
"Jest dzielnik 7 oraz drugi równy (1*7+4) = 11."
Skąd wychodzi 7? 140 jest podzielne przez 7 ale jest podzielne także przez 5.
Jak mi się uda zrozumieć to spróbuje zaimplementować w pytonie.

jaNusz pisze...

Konwertujemy na kolejne systemy o nieparzystej podstawie: 3, 5, 7, 9, 11, itd. sprawdzając, czy cyfra najmniej znacząca jest zerem.
Uzyskiwane ciągi 'cyfr' są liczbami dziesiątkowymi tylko w obrębie 'cyfry' danego systemu. Tak liczba '2212' systemu trójkowego ma 4 cyfry, lecz nie jest większa niż setka w dziesiątkowym, gdyż dziesiętną setką w trójkowym jest '10201'. Jest to kłopot nawet dla najlepszych.
Algorytm po prostu błyskawicznie przechodzi z jednego systemu na inny bez pośrednictwa systemu dziesiątkowego.

Zapis '3 0 2' w piątkowym nie oznacza dziesiętnej liczby "302", ale liczbę: 3*5^2 + 0*5 + 2.
Podobnie uzyskane '1 4 0' w siódemkowym to
1*7^2 + 4*7 + 0.
Ta wartość nie jest podzielna przez 5 mimo zera na końcu. Rachujemy w dziesiątkowym, ale uzyskane współczynniki są cyframi w innych systemach. Dlatego właśnie jest pętla 'while not', aby sprowadzić liczby stojące na miejscu cyfr do zwykłych 'cyfr' danego systemu.

W systemie o podstawie p mnożenie przez p wygląda jak mnożenie przez '10'. Jeśli znamy dzielnik (ciąg cyfr systemu p kończy się zerem), dzielimy przez p (co wygląda jak dzielenie przez '10'), uzyskując nową wartość, mniejszą p razy.
Uzyskaliśmy '140_7' w siódemkowym, dzielimy przez '10_7' czyli 7 uzyskując '14_7' w siódemkowym. Dla wartości 'dwucyfrowej' w tej wersji algorytmu sprawdzone są już wszystkie dzielniki między 2 a pierwiastek z liczby, czyli można zakończyć.

W rozkładzie liczby dziesiątkowej 8934053 kończymy przy liczbie 'dwucyfrowej' '7 610' (a[1]=7; a[0]=610), ale do znalezienia dzielników potrzebujemy informację o podstawie systemu p=1087, by móc je wskazać.

jaNusz pisze...

Na wejściu konwersji mamy zawsze TĘ SAMA LICZBĘ, tylko różnie zapisaną:
'2212_3' = '302_5' = '140_7' = '85_9' = '7 0_{11}' = '5 12_{13}' = '5 2_{15}' = ... = '1 0_{77}' = '77_{79}'
Spacja tu jest separatorem cyfr.

Anonimowy pisze...

"Zapis '3 0 2' w piątkowym nie oznacza dziesiętnej liczby "302", ale liczbę: 3*5^2 + 0*5 + 2. "
Wiem ale myślałem że taka logika jest tu przyjęta.

Hmm...Czyli po prostu przy konwersji liczby rozkładanej na system liczbowy o podstawie dzielnika najmniej znaczący bit jest równy zero.
Czyli tu zamiast dzielenia jest wykonywana po prostu konwersja.
Ciekawy sposób.

jaNusz pisze...

Najmniej znaczący bit równy 0 tylko w implementacjach, w ktorych poszczególne cyfry są sąsiadującymi ciągami bitów. Może być wolniejsze - rozdzielanie cyfr.

Dodatkowo, dla bardzo, bardzo dużych liczb, z przedziału pierwiastka sześciennego do pierwiastka kwadratowego rozkładanej liczby, konwersje się upraszczają, dla zmiany podstawy systemu o 1 czy 2 można je policzyć ręcznie.
Są tak skomplikowane, jak przejście z systemu piątkowego na siódemkowy przykładu. A to w sitach wydaje się najgorszy obszar do obliczeń.

Anonimowy pisze...

"Dodatkowo, dla bardzo, bardzo dużych liczb, z przedziału pierwiastka sześciennego do pierwiastka kwadratowego rozkładanej liczby, konwersje się upraszczają, dla zmiany podstawy systemu o 1 czy 2 można je policzyć ręcznie."
Żeby coś takiego zaimplementować trzeba by wiedzie jakie to liczby lub z jakiego przedziału.
Jeśli rozkładamy liczbę 1024 bitową, która pochodzi z klucza RSA to dzielniki będą miały gdzieś po 155 znaków(chyba po tyle zawsze mają). Ciekawe ile zajęło by konwertowanie od 1x10^155 do 9x10^155.Będzie czas to przyjże się bliżej: http://matformac.blogspot.com/2012/12/wielomianowy-algorytm-faktoryzacji.html
Przyznam że też podobnie kombinowałem:
35 to 2^5-3 lub 2^6-29 .
Gdy czynniki są blisko siebie to łatwo dość do jednego z nich bo im bliżej tym mniejsze reszty.

jaNusz pisze...

Jeżeli program umie obsługiwać duże wartości trzymane dynamicznie, nie trzeba się przejmować ich rozmiarem. I tak algorytm opisany w tym poście działa na liczbach nie większych niż połowa długości rozkładanej liczby, tzn. jeśli długość liczby n jest 2b, to rachujemy na wartościach nie większych niż 3b/2. Mogą być znacznie mniejsze.
Algorytm z grudnia jest inny, uważam że gorszy niż ten opisany tutaj. Jest bardzo prosty, lecz wartości zmniejszają się od liczby rozkładanej n do pierwiastka z n. Nie nadaje się do RSA.

Przelicznik: 3 bity to około 10, zatem dzielniki 1024-bitowego RSA mają około 170 cyfr dziesiętnych. W prezentowanym algorytmie na 4 wartości zaledwie 2-3 będą tak długie.

Współczynnik 'cyfry' najbardziej znaczącej liczby przy konwersjach zwiększających podstawę systemu maleje wykładniczo. Liczby dobre dla RSA są w 'ogonie'. Przy zwiększaniu liczb ogon się wydłuża, ale dla dwu z moich algorytmów względny czas poszukiwań się skraca poniżej kilkudziesięciu procent czasu sprawdzenia wszystkich możliwości.

Anonimowy pisze...

"Przelicznik: 3 bity to około 10, zatem dzielniki 1024-bitowego RSA mają około 170 cyfr dziesiętnych."
Liczba 1024 bitowa w RSA ma 309 cyfr.Jeśli czynniki mają po tyle samo znaków to zasadniczo po 155.
Tu przy 1024 bitowej n czynniki(p i q) mają po 155 :
http://www-cs-students.stanford.edu/~tjw/jsbn/rsa2.html
Tutaj długości czynników są różna:
http://www.hanewin.net/encrypt/rsa/rsa-test.htm
Nie wiem która wersja jest używana przy prawdziwych kluczach.

Anonimowy pisze...

A właściwie jak przekonwertować na system powyżej dziesiętnego?
Przecież np. w systemie szesnastkowym używamy liter od A do F.To jak użyjemy jeszcze liczb do Z włącznie to wydaje mi się, że maksymalny system(przy użyciu alfabetu angielskiego) będzie miał podstawę 36. Czy się mylę?

jaNusz pisze...

Konwersja działa bez zarzutu. Kłopot jest właśnie z zapisem 'cyfr'.
Używając symboli graficznych wzorowanych na np. zegarku elektronowym, można uzyskać kilkaset rozróżnialnych cyfr, ale jest to trudne do zapamiętania.

Rozwiązaniem jest wprowadzenie nowego separatora cyfr. Cyfry są wtedy zapisywane np. jako zwykłe 'liczby dziesiętne'.
Dla bardzo dużych wartości przydatne są dwa separatory.
- separator oddzielający paczki / grupy w obrębie cyfry (w dziesiątkowym w Polsce to kropka, na zachodzie Europy przecinek), używany także w niektórych błyskawicznych konwersjach między podstawami p^i na p^j, i<>j np. 756.975.573.678;
- właściwy separator cyfr, spacja albo ampersand, np. 47.547 ' 85.573 ' 3 przy podstawie p=100.000 oznacza liczbę dziesiętną 47547.85573.00003.

Anonimowy pisze...

Jak będzie wyglądała konwersja 77 na system o podstawie kolejno: 11,12,13,14 z użyciem separacji bo "jakoś tego nie czuje"?

jaNusz pisze...

Dziesiątkowe 77 w systemach (może użyję apostrofu jako separatora):
11: 7 ' 0
12: 6 ' 5
13: 5 '12
14: 5 ' 7
15: 5 ' 2
16: 4 '13
17: 4 ' 9
18: 4 ' 5
19: 4 ' 1
20: 3 '17
21: 3 '14
22: 3 '11
23: 3 ' 8
...
76: 1 ' 1
77: 1 ' 0
78: 77
79: 77

Anonimowy pisze...

http://matformac.blogspot.com/2011/04/zmiany-systemow-liczbowych.html
tylko tym sposobem czy da się jakoś "ładniej" to zrobić(też bez dzielenia)?

jaNusz pisze...

Czytając żródła matematyków poruszających się blisko systemów niedziesiątkowych, konwertowali oni tylko z pomocą dziesiątkowego za pomocą mnożeń lub dzieleń.

Najbliżej zaprezentowanemu w poście z kwietnia 2011 roku algorytmowi jest do przekształcenia W. Sodena (1953) oraz C. Roziera (1962) konwersji między liczbami ósemkowymi i dziesiętnymi (wspomnienie: Knuth, Sztuka programowania, t.2 Algorytmy seminumeryczne 4.4.C). Tamte algorytmy operują jednak dużymi liczbami, nawet długości wartości konwertowanej.

Wykryłem jeszcze kilka konwersji, lecz służą one do zmiany podstaw szczególnej postaci. Tak więc, na razie jest to najlepszy znany mi algorytm.