[Algorytmy]Szybki algorytm rozkładu na czynniki pierwsze

Awatar użytkownika
Borneq
Użytkownik
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

Post autor: Borneq »

Jaki algorytm szybszy niż dzielenie przez nieparzyste liczby do pierwiastka z liczby?
dec1
Użytkownik
Użytkownik
Posty: 714
Rejestracja: 21 mar 2016, o 21:42
Płeć: Mężczyzna
Pomógł: 191 razy

[Algorytmy]Szybki algorytm rozkładu na czynniki pierwsze

Post autor: dec1 »

Np. sito Erastostenesa, Atkina, algorytm rho Pollarda, SQUFOF, ogólne sito ciała liczbowego
Awatar użytkownika
Cytryn
Użytkownik
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

Post autor: Cytryn »

Jeżeli rozkładasz liczby do trzystu cyfr,

Kod: Zaznacz cały

https://sourceforge.net/projects/msieve/
będzie w miarę dobry.
Awatar użytkownika
Borneq
Użytkownik
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

Post autor: Borneq »

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
899694195938257768340968996941959382577683409689969419593825778340968996941959382577
, którą mi rozkłada w 24 sekundy, ale gdy jest -np

Dodatkowe pytanie: jest szybsza metoda: "special number field sieve", tylko że general rozkłada wszytko a special - jakiej postaci muszą być liczby?
ODPOWIEDZ