V některých Linuxových distribucích najdete NTL jako balíček, takže např. v Ubuntu nainstalujete NTL příkazem
sudo apt-get install libntl-dev
Hotovo.
Pokud se rozhodnete knihovnu přeložit sami, pak můžete použít následující posloupnost příkazů, která stáhne knihovnu NTL, rozbalí, nastaví, přeloží, ověří, že vše funguje, jak má, a nainstaluje do /usr/local
. Pokud však nemáte možnost do tohoto adresáře zapisovat, pak si ji nainstalujte někam do domovského adresáře tak, že příkaz ./configure
nahradíte např. ./configure PREFIX=$HOME/sw
(v tomto případě pochopitelně vynechte sudo
v posledním příkazu).
wget http://www.shoup.net/ntl/ntl-5.5.2.tar.gz
tar xzf ntl-5.5.2.tar.gz
cd ntl-5.5.2/src
./configure
make
make check
sudo make install
Adresář ntl-5.5.2
a soubor ntl-5.5.2.tar.gz
můžete potom odstranit. Další podrobnosti najdete v návodu na stránkách Victora Shoupa.
Svůj program pak přeložíte příkazem
g++ nazev_zdrojaku.cc -o nazev_programu -lntl -lm
nebo pokud jste NTL instalovali do domovského adresáře, příkazem
g++ -I$HOME/sw/include nazev_zdrojaku.cc -o nazev_programu -L$HOME/sw/lib -lntl -lm
Přepínače -lntl
a -lm
musejí být na konci příkazu!
Jestliže budete používat překladač MinGW (tj. např. prostředí Code::Blocks), pak postupujte podle návodu na stránkách Milana Straky.
Jestliže budete používat Microsoft Visual C++, pak si stáhněte tuto binárku, anebo pokud si chcete NTL přeložit sami, stáhněte si tento projekt pro Visual C++ Express 2008.
Pokud máte přístup k adresáři C:\Program Files\Microsoft Visual Studio 9.0\VC\include\
zkopírujte do něj složku NTL
, která obsahuje hlavičkové soubory, a do adresáře C:\Program Files\Microsoft Visual Studio 9.0\VC\lib\
zkopírujte soubor ntl.lib
. Pokud k těmto adresářům přístup nemáte, pak budete muset vždy při založení nového projektu sdělit vývojovému prostředí, kde se nacházejí hlavičkové soubory a soubor ntl.lib
, takto:
Project
→ Properties
→ Configuration Properties
→ C/C++
→ General
→ Additional Include Directories
přidáte adresář include
, ve kterém se nachází podadresář NTL
s hlavičkovými soubory.Project
→ Properties
→ Configuration Properties
→ Linker
→ General
→ Additional Library Directories
přidáte adresář lib
, ve kterém máte soubor ntl.lib
.Při založení každého nového projektu musíte sdělit překladači, že budete používat knihovnu NTL, tak, že do Project
→ Properties
→ Configuration Properties
→ Linker
→ Input
→ Additional Dependencies
přidáte ntl.lib
.
Knihovna GMP je nainstalovaná v karlínském labu i na výpočetním clusteru Sněhurka.
Ve většině Linuxových distribucích najdete GMP jako balíček, takže např. v Ubuntu nainstalujete GMP příkazem
sudo apt-get install libgmp3-dev
Hotovo.
Pokud se rozhodnete knihovnu přeložit sami, musíte mít nainstalovaný procesor maker m4
. Následující posloupnost příkazů nainstaluje m4
(na Ubuntu) a stáhne, přeloží a nainstaluje knihovnu GMP.
sudo apt-get install m4
wget ftp://ftp.gmplib.org/pub/gmp-5.0.4/gmp-5.0.4.tar.bz2
tar xjf gmp-5.0.4.tar.bz2
cd gmp-5.0.4
./configure --enable-cxx
make
make check
sudo make install
Adresář gmp-5.0.4
a soubor gmp-5.0.4.tar.bz2
můžete potom odstranit. Další podrobnosti najdete v manuálu na stránkách knihovny GMP.
Svůj program pak přeložíte příkazem
g++ nazev_zdrojaku.cc -o nazev_programu -lgmpxx -lgmp
Z níže uvedeného seznamu vám bude náhodně přiřazen jeden algoritmus. Pro získání zápočtu je třeba
Použitím knihovny NTL se rozumí, že váš program nebude omezen standardními datovými typy jako int
nebo double
, ale bude využívat např. typy ZZ
, RR
nebo ZZX
z knihovny NTL a bude tak umět pracovat s libovolně velkými čísly, s polynomy libovolného stupně atp.
Pokud nejste spokojeni s přiřazeným algoritmem, můžete si vybrat jeden z algoritmů, které jsou označeny *. Tyto algoritmy se probírají na přednášce Počítačová algebra II, popřípadě na přednášce Teorie čísel a RSA (viz skripta Aleše Drápala).
Algoritmus | Student | Zápočet |
---|---|---|
Čínská věta o zbytcích v Zp[x]: Lagrange vs. Garner | Adéla Zajíčková | ANO |
Čínská věta o zbytcích v Q[x]: Lagrange vs. Garner | Ondřej Väter | |
Násobení polynomů v Z[x]: školské vs. pomocí FFT v Zp[x] | František Steinhauser | ANO |
Násobení polynomů v Z[x]: školské vs. pomocí FFT v C[x] | Jakub Töpfer | ANO |
Dělení polynomů v Z[x]: školské vs. rychlé (Newton) | Anežka Titěrová | ANO |
Dělení polynomů v Zp[x]: školské vs. rychlé (Newton) | David Mařák | ANO |
Dělení v Z: Newtonova metoda vs. půlení intervalu vs. školské | Radka Luňáčková | ANO |
NSD pomocí PRS v Z[x] | Miloš Klouček | ANO |
NSD pomocí PRS v Z[x,y] | Richard Dubiel | ANO |
NSD - modulární algoritmus v Z[x] | Lukáš Gurník | ANO |
NSD - modulární algoritmus v Z[x] | Michal Mutňanský | ANO |
Bezčtvercová faktorizace v Z[x] | Lukáš Langer | ANO |
Bezčtvercová faktorizace v Zp[x] | Marek Trunkát | ANO |
Berlekampův algoritmus (faktorizace v Zp[x]) | Romana Linkeová | ANO |
Henselovo liftování a faktorizace v Z[x] | Kristina Hostáková | ANO |
Testování ireducibility v Z[x] a v Zp[x] | Bernd Mangold | |
Kroneckerův algoritmus (faktorizace v Z[x,y]) | Adam Ivánek | ANO |
Buchbergerův algoritmus a redukce Gröbnerovy báze* | Ludmila Divišová | ANO |
Rabin-Millerův a Solovay-Strassenův test prvočíselnosti* | Zbyněk Chmela | ANO |
V knihovně NTL není implementována aritmetika v Q[x], použijte floating point aritmetiku. Aritmetikou v C[x] se rozumí floating point aritmetika. Pro dělení v Z[x] uvažujte pouze monické dělitele.
U většiny zápočtových programů mi bude stačit, když pošlete zdrojové kódy a stručnou dokumentaci emailem. V případě nejasností vás dodatečně požádám o osobní odevzdání a předvedení programu. Jako dokumentace postačí popis nebo příklad vstupu/výstupu a pár komentářů v kódu, abych se v něm mohl snadno zorientovat. Zejména pokud se váš program skládá z více algoritmů, tak je ve svém kódu označte komentářem. Nejlépe, když uvedete přímo číslo, kterým je algoritmus označen v učebnici. Pokud jste svou úlohu rozdělili do několika programů, tak ke každému napište popis vstupu/výstupu a jednou větou co dělá, není-li to na první pohled zřejmé.