GDLOG Code
Implementation of the GNFS for discrete logarithm problem in GF(p)
Status: Alpha
Brought to you by:
olegbbl
File | Date | Author | Commit |
---|---|---|---|
dist | 2013-01-27 |
![]() |
[e56d04] Add release 1.0.2-alpha |
examples | 2014-11-25 |
![]() |
[db8966] Remove lc0Fact from configs |
progs | 2015-02-01 |
![]() |
[4f2a3e] Apply Style |
src | 2015-08-03 |
![]() |
[2c46d0] Fix tests |
tests | 2015-08-03 |
![]() |
[2c46d0] Fix tests |
AUTHORS | 2010-06-13 |
![]() |
[3387dc] Documentation |
CMakeLists.txt | 2015-08-03 |
![]() |
[2c46d0] Fix tests |
COPYING | 2009-12-10 |
![]() |
[75d7b3] GDLOG Alpha Initial |
ChangeLog | 2013-07-19 |
![]() |
[74d103] OS X support |
INSTALL | 2014-11-25 |
![]() |
[2dc85d] Update INSTALL |
LICENSE | 2010-06-13 |
![]() |
[3387dc] Documentation |
NEWS | 2013-01-27 |
![]() |
[82975d] Docs update |
README | 2013-01-27 |
![]() |
[92fc40] Release 1.0.2 |
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.