What form are your primes (did you use Maurers idea to increase the relative hardness of factoring compared to discrete log, or did you just use more smaller primes?) How many primes have you used, and how many CPU hours did it take to calculate the discrete log to discover e?
N is the product of two primes, but each p-1 has about 16 small prime factors (about 25-35 bits) to allow calculating the discrete log efficiently. With this choice of primes it took about three hours to run the discrete log.
Also is the code for finding discrete logs given the prime factorisation of the modulus available?
Here you go. This uses cryptolib by Jack Lacy of AT&T (not to be confused with cryptlib by Peter Gutmann), available from ftp://ftp.funet.fi/pub/crypt/cryptography/libs/cryptolib_1.1.tar.gz /* Calculate discrete log using various algorithms */ /* Algorithms based on Handbook of Applied Cryptography by Menezes et al */ #include "libcrypt.h" /* Modular multiplication - m1*m2 mod n */ static void bigMultiplyN (BigInt m1, BigInt m2, BigInt n, BigInt result) { BigInt tmp = bigInit(0); bigMultiply (m1, m2, tmp); bigMod (tmp, n, result); freeBignum (tmp); } /* Modular addition, m1+m2 mod n */ static void bigAddN (BigInt m1, BigInt m2, BigInt n, BigInt result) { bigAdd (m1, m2, result); if (bigCompare (result, n) >= 0) bigSubtract (result, n, result); } /* Iterate the pollard rho. Modify x, a, b with next values */ static void prhoiter (BigInt base, BigInt val, BigInt mod, BigInt order, BigInt *x, BigInt *a, BigInt *b) { int xgroup; /* First decide what group x is in */ /* This is a cheat to be fast */ xgroup = ((unsigned)(*x)->num[0]+1) % 3; switch (xgroup) { case 0: bigMultiplyN (*x, val, mod, *x); bigAddN (*b, one, order, *b); break; case 1: bigMultiplyN (*x, *x, mod, *x); bigAddN (*a, *a, order, *a); bigAddN (*b, *b, order, *b); break; case 2: bigMultiplyN (*x, base, mod, *x); bigAddN (*a, one, order, *a); break; } } /* Pollard rho algorithm for discrete log */ BigInt pollardrho (BigInt base, BigInt val, BigInt mod, BigInt order) { BigInt x = bigInit(1), a = bigInit(0), b = bigInit(0), x2 = bigInit(1), a2 = bigInit(0), b2 = bigInit(0); int cnt = 0; for ( ; ; ) { prhoiter (base, val, mod, order, &x, &a, &b); prhoiter (base, val, mod, order, &x2, &a2, &b2); prhoiter (base, val, mod, order, &x2, &a2, &b2); if (bigCompare (x, x2) == 0) break; if (++cnt % 1000 == 0) { printf ("%d\r", cnt); fflush (stdout); } } if (cnt >= 1000) printf ("\n"); if (bigCompare (b, b2) < 0) bigAdd (order, b, b); bigSubtract (b, b2, b); if (bigCompare (a2, a) < 0) bigAdd (order, a2, a2); bigSubtract (a2, a, a); if (bigCompare (b, zero) == 0) { printf ("Pollard rho failed\n"); exit (1); } getInverse (b, order, b2); bigMultiplyN (a, b2, order, a); return a; } /* * Do the CRT with multiple congruences. congs are the values that the * answer should be congruent to, mods are the moduli for each congruence. * n tells how many in each array. */ static BigInt crtmult (BigInt congs[], BigInt mods[], int n) { int i; BigInt prod = bigInit(0); BigInt prod1 = bigInit(0); BigInt sum = bigInit(0); BigInt quot = bigInit(0); BigInt rem = bigInit(0); BigInt dum = bigInit(0); BigInt inv = bigInit(0); BigInt term = bigInit(0); /* Compute product of moduli */ bigCopy (one, prod); for (i=0; i<n; ++i) { bigMultiply (prod, mods[i], prod1); bigCopy (prod1, prod); } for (i=0; i<n; ++i) { bigDivide (prod, mods[i], quot, dum); bigDivide (quot, mods[i], dum, rem); getInverse (rem, mods[i], inv); bigMultiplyN (congs[i], quot, prod, term); bigMultiplyN (term, inv, prod, term); bigAddN (term, sum, prod, sum); } return sum; } /* Pohlig-Hellman discrete log algorithm for composites */ /* Return the exponent such that base^exponent == val modulo mod. */ /* Group order is product of factors[], of which there are n */ /* Assume each factor is to the first power */ BigInt phlog (BigInt base, BigInt val, BigInt mod, BigInt factors[], int n) { BigInt prod = bigInit(0), prod1 = bigInit(0), exp = bigInit(0), dum = bigInit(0), b = bigInit(0), v = bigInit(0); BigInt *dlogs; BigInt dl; int i; dlogs = (BigInt *) malloc (n * sizeof (BigInt)); /* Compute product of factors to get group order */ bigCopy (one, prod); for (i=0; i<n; ++i) { bigMultiply (prod, factors[i], prod1); bigCopy (prod1, prod); } /* Sanity check */ bigPow (base, prod, mod, b); if (bigCompare (b, one) != 0) { printf ("Inconsistency in group order on b\n"); fBigPrint (b, stdout); } bigPow (val, prod, mod, v); if (bigCompare (v, one) != 0) { printf ("Inconsistency in group order on v\n"); fBigPrint (v, stdout); } for (i=0; i<n; ++i) { bigDivide (prod, factors[i], exp, dum); bigPow (base, exp, mod, b); bigPow (val, exp, mod, v); printf ("Trying dlog with factor: "); fBigPrint (factors[i], stdout); printf ("b: "); fBigPrint (b, stdout); printf ("v: "); fBigPrint (v, stdout); /* Special case for 2, pollardrho doesn't work too well on it */ if (bigCompare (factors[i], two) == 0) { if (bigCompare (b, v) == 0) { dlogs[i] = bigInit(1); } else if (bigCompare (v, one) == 0) { dlogs[i] = bigInit(0); } else { printf ("Inconsistent b, v for factor == 2\n"); exit (1); } } else { /* Now find log of v mod b, has group order factors[i] */ dlogs[i] = pollardrho (b, v, mod, factors[i]); } printf ("dl: "); fBigPrint (dlogs[i], stdout); bigPow (b, dlogs[i], mod, b); if (bigCompare (b, v) != 0) { printf ("Error in discrete log calc!\n"); exit (1); } } /* Combine results with CRT */ dl = crtmult (dlogs, factors, n); return dl; }