[Algorytmy]Szybki algorytm rozkładu na czynniki pierwsze
- Borneq
- Użytkownik
- Posty: 247
- Rejestracja: 23 lip 2010, o 07:50
- Płeć: Mężczyzna
- Lokalizacja: geo:lat=0 geo:lon=0
- Podziękował: 13 razy
[Algorytmy]Szybki algorytm rozkładu na czynniki pierwsze
Jaki algorytm szybszy niż dzielenie przez nieparzyste liczby do pierwiastka z liczby?
[Algorytmy]Szybki algorytm rozkładu na czynniki pierwsze
Np. sito Erastostenesa, Atkina, algorytm rho Pollarda, SQUFOF, ogólne sito ciała liczbowego
- Cytryn
- Użytkownik
- Posty: 405
- Rejestracja: 17 wrz 2016, o 17:04
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 2 razy
- Pomógł: 46 razy
[Algorytmy]Szybki algorytm rozkładu na czynniki pierwsze
Jeżeli rozkładasz liczby do trzystu cyfr, będzie w miarę dobry.
Kod: Zaznacz cały
https://sourceforge.net/projects/msieve/
- Borneq
- Użytkownik
- Posty: 247
- Rejestracja: 23 lip 2010, o 07:50
- Płeć: Mężczyzna
- Lokalizacja: geo:lat=0 geo:lon=0
- Podziękował: 13 razy
[Algorytmy]Szybki algorytm rozkładu na czynniki pierwsze
Projekt msieve zawiera dwa najszybsze algorytmy. A co z liczbami specjalnymi w postaci na przykład \(\displaystyle{ 2^n-1}\) czy \(\displaystyle{ 2^n+1}\) ? Chociaż w tym przypadku, potrzebne raczej tylko sprawdzenie na pierwszość, bo po rozkładzie ta specjalna lcizba będzie musiała być rozkładana dalej w zwykły sposób.
Msieve wywołuję z parametrami msieve152 -p -v -np . Zwłaszcza ten ostatni parametr mnie zastanawia, bez niego znacznie wolniej, z nim nie zawsze działa, jest komunikat "stage 1..".
Sprawdzam dla liczby
Dodatkowe pytanie: jest szybsza metoda: "special number field sieve", tylko że general rozkłada wszytko a special - jakiej postaci muszą być liczby?
Msieve wywołuję z parametrami msieve152 -p -v -np . Zwłaszcza ten ostatni parametr mnie zastanawia, bez niego znacznie wolniej, z nim nie zawsze działa, jest komunikat "stage 1..".
Sprawdzam dla liczby
, którą mi rozkłada w 24 sekundy, ale gdy jest -np899694195938257768340968996941959382577683409689969419593825778340968996941959382577
Dodatkowe pytanie: jest szybsza metoda: "special number field sieve", tylko że general rozkłada wszytko a special - jakiej postaci muszą być liczby?