Pollard rho czynniki pierwsze.

0

Chcialbym sie dowiedziec jaki algorytm bedzie wstanie jak najszybciej rozlozyc liczbe typu "long long" na czynniki pierwsze.Troche poczytalem na necie i chyba jest to algorytm Pollard rho. Czy to prawda??

Poniżej pseudokod. Czy ktos pomoze mi go napisac w c++?

function pollardRho(N)
# Initial values x(i) and x(2*i) for i = 0.
xi := 2
x2i := 2
do
# Find x(i+1) and x(2*(i+1))
xiPrime := xi ^ 2 + 1
x2iPrime := (x2i ^ 2 + 1) ^ 2 + 1
# Increment i: change our running values for x(i), x(2*i).
xi := xiPrime % N
x2i := x2iPrime % N
s := gcd(xi - x2i, N)
if s <> 1 and s <> N then
return s, N/s
end if
end do
end function

 
0

Naszła mnie teraz taka myśl:
A jakby tak wcześniej obliczyć sobie liczby pierwsze.
A potem tylko sprawdzać czy dana liczba pierwsza dzieli się bez reszty to jest czynnikiem tej liczby.
Czy taka opcja dawałaby dobre wyniki? I czy dużo by zajmowałoby miejsca obliczenie liczb pierwszych do 10 cyfr?

0
narnano napisał(a)

potem tylko **sprawdzać czy dana liczba pierwsza dzieli się bez reszty ** to jest czynnikiem tej liczby.

Jeśli jest liczbą pierwszą to trudno żeby dzieliła się bez reszty przez jakąkolwiek inna liczbę niż samą siebie i jedynkę :]

0

Moze cos pokreciłem.
Chce wyznaczyc w jak najszybszy sposob czynniki pierwsze podanej przeze mnie liczby. Z tym ze bd to duza liczba ok 10cyfrowa.
Czy wyliczenie najpierw liczb pierwszych przyspieszyloby proces szukania czynnikow ?

0

Niewątpliwie tak, bo dzieliłbyś swoją liczbę tylko przez liczby pierwsze ;]

0

Tylko jak to teraz zrealizowac?
zapisac kazdą liczbe pierwsza w jednej linijce pliku txt.
A potem w programie czytac linia po lini i sprawdzac warunek? czy jest na to lepszy sposob?

0
narnano napisał(a)

Czy taka opcja dawałaby dobre wyniki? I czy dużo by zajmowałoby miejsca obliczenie liczb pierwszych do 10 cyfr?
liczby pierwsze do milliarda zajmowałby troszkę ponad 60 MB.

0

Taki rozmiar mi odpowiada. Tylko czy przy sprawdzaniu wczytywac te liczby do tablicy i dopiero sprawdzac czy czytac je linijka po linijce i sprawdzac ?
ktore rozwiazanie bd najszybsze?

0

Operacje I/O są ekstremalnie wolne. Jak będziesz czytał to z pliku linijka po linijce (i kompilator nie uratuje cię buforowaniem) to szybciej byłoby liczyć to na bieżąco ;]

0

Po pierwsze wystarczą Ci tylko liczby pierwsze do sqrt(max). Po drugie jeżeli program ma wyznaczyć tylko rozkład jednej liczby (a nie dużego zbioru) to wystarczy, że będziesz dzielił przez kolejne liczby mniejsze niż pierwiastek z szukanej liczby. 10^5.5 dzieleń to nie jest wcale tak dużo (można dodać mnożenie, żeby szybciej wyjść z pętli).

0

Ekstremalny jest algorytm zmiany systemow liczbowych.
Dokladniejsze informacje o algorytmie oraz sposobie konwersji jest na
matformac.blogspot.com
Algorytm sprawdzil mi, ze liczba bliska wielkosci slowa maszynowego jest pierwsza w czasie krotszym niz milisekunda.

0

no to liczba lon long (64 bity) czy dziesięciocyfrowa?

0

Dla procesorów z zegarem 1,4 GHz (10-letnie) long long ma rozmiar 32 bity. To algorytm ma zmniejszoną złożoność. Korzysta tylko z operacji liniowych dla dużych liczb i jednego mnożenia na wzor Karatsuby.

1 użytkowników online, w tym zalogowanych: 0, gości: 1