File	Date	Author	Commit
dist	2013-01-27	olegbbl13	[e56d04] Add release 1.0.2-alpha
examples	2014-11-25	Oleg Babul	[db8966] Remove lc0Fact from configs
progs	2015-02-01	Oleg Babul	[4f2a3e] Apply Style
src	2015-08-03	Oleg Babul	[2c46d0] Fix tests
tests	2015-08-03	Oleg Babul	[2c46d0] Fix tests
AUTHORS	2010-06-13	olegbbl13	[3387dc] Documentation
CMakeLists.txt	2015-08-03	Oleg Babul	[2c46d0] Fix tests
COPYING	2009-12-10	olegbbl13	[75d7b3] GDLOG Alpha Initial
ChangeLog	2013-07-19	ababul	[74d103] OS X support
INSTALL	2014-11-25	Oleg Babul	[2dc85d] Update INSTALL
LICENSE	2010-06-13	olegbbl13	[3387dc] Documentation
NEWS	2013-01-27	olegbbl13	[82975d] Docs update
README	2013-01-27	olegbbl13	[92fc40] Release 1.0.2

Read Me

		GDLOG folders structure
	======================================
/progs/*     - programs for GNFS (for dlog) stages:

	       gdlg_polsel -  polynomial selection
	       gdlg_sieve  -  sieve
	       gdlg_sys    -  solve system
	       gdlg_dlog   -  calculate final logarithm
	       gdlog.py    -  automation script
	
/src/*       - sources
/include/*   - headers
/tests/*     - tests
/examples/*  - example configuration files	

		GDLOG Usage
	================================
GDLOG is an implementation of the Number Filed Sieve algorithm to solve discrete
logarithm problem in the Z\pZ. GDLOG can be used to solve the following problem:

Let p - prime number and q | p - 1 - odd prime divisor.
Let 0 < g < p and 0 < t < p in Z\pZ. 
Find 0 <= x < q - 1 such that g^(x*(p-1)/q) mod p = b^((p-1)/q) mod p (assuming that such x exists).

To get started with GDLOG:

1. Go to /examples directory
2. Choose configuration file (for example 30). 
Configuration file contains prime numbers p and q | p - 1 and job name (optional).
3. Execute
   
   ../progs/gdlog.py  30

4. Python script  executes gdlg_polsel to select pair of polynomials. After execution of this program
   pair of the polynomials with common root m modulo p will be added to the configuration file.
5. After polynomial selection automation script will launch several (for each processor/core) instances 
of the gdlg_sieve program. After completion of the sieving stage several *.rel files. These files
contain relations with factorization.
6. After sieving automation script will launch gdlg_sys to build and solve system of the linear equations over 
Z/qZ. To build the system script will request to enter factorization for the leading coefficient of the f0 polynomial
(which was added to the configuration file during polynomial selection stage):

Add factorization for lc(f0) ([p0 p1 p2 ...]) to configuration file (30 for example)

lc0Fact: [13 1409 22271]

gdlg_sys program will generate *.logbase file which contains  "virtual" logarithms and is used 
as input for the next stage.
7. After solve system stage automation script will launch gdlg_dlog to find final logarithm.
gdlg_dlog requires:

a) p - 1 factorization:

Add factorization for p-1 ([p0 p1 p2 ...]) to configuration file (30 for example)

p1Fact:  [2 3 79043 3998741 290240017 454197539]

b) Add g and t to configuration file:
g: 5
t: 123456789012345678901234567890

After successful execution gdlg_dlog prints:

Logarithm of the 123456789012345678901234567890 to the 5 is 5483932. Checking result: ok

See NEWS file for more GDLOG results.

		GDLOG References
	==================================

Cohen, H. A course in computational algebraic number theory/ Henri Cohen -- New York: Springer-Verlag, 1995. -- 540 p.

Shirokauer, O. Discrete logarithms and local units/O. Shirokauer
//Phil. Trans. R. Soc. Lond. A -- 1993. -- V. 345, № 1676.\dash P. 409--423.

Lercier, R. Improvements to the number filed sieve for discrete logarithms in prime fields. 
a comparision with the gaussian integer method/Reynald Lercier, Antoine Joux
//Mathematics of computation -- 1999. -- Vol. 72\dash P. 953--967.

Murphy, B. Polynomial Selection for the Number Filed Sieve Integer Factorization Algorithm/B. A. Murphy.
//PhD thesis, The Australian National University, 1999.

Franke, J. Continued fractions and lattice sieving/J. Franke, T. Kleinjung
//Proceedings SHARCS 2005[Electronic resource]. -- 2005. -- Mode of access: http://www.hyperelliptic.org/tanja/SHARCS/talks/FrankeKleinjung.pdf

Aoki, K. Sieving Using Bucket Sort /Kazumaro Aoki.
//Advances in Cryptology - ASIACRYPT 2004, Springer Berlin / Heidelberg -- 2004. -- V. 3329 -- P. 92-102.

Coppersmith, D. Discrete Logarithms in GF (p)/Don Coppersmith, Andrew M. Odlyzko, Richard Schroeppel
//Algorithmica -- 1986. \dash V. 1, № 1. -- P. 1--15.

LaMacchia, B. A. Computation of Discrete Logarithms in Prime Fields/B. A. LaMacchia A. M. Odlyzko.
//Lecture Notes in Computer Science -- 1991. -- V. 537/1991. -- P. 617-618.

Buhler, J. P. Factoring integers with the number field sieve /J. P. Buhler, H. W. Lenstra Jr. and Carl Pomerance
//Springer Berlin / Heidelberg, Lecture Notes in Mathematics\dash  1993. -- V. 1554. -- P. 50--94.