Menu

Tree [2c46d0] master /
 History

HTTPS access


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


Want the latest updates on software, tech news, and AI?
Get latest updates about software, tech news, and AI from SourceForge directly in your inbox once a month.