p = 100003   &  g = 2
factor base = the 17 primes < 60

tried about 130 different g^k to find 17 + 10 relations

%4 = 
[9 -4 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 690526]

[0 0 1 -1 0 0 0 0 0 -1 0 0 0 0 0 1 0 1355936]

[0 3 -1 0 1 -2 0 0 0 0 0 0 0 0 0 0 0 1212247]

[0 1 0 0 -1 1 0 1 0 0 0 0 0 -1 0 0 0 1030849]

[3 -1 -3 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1264072]

[0 -4 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 800092]

[2 0 1 -1 0 0 0 0 0 0 1 0 0 0 0 0 -1 476338]

[0 0 0 0 1 -1 0 0 0 0 0 1 0 0 0 0 -1 535108]

[-3 -1 0 0 -1 0 0 2 0 0 0 0 0 0 0 0 0 372833]

[6 -3 0 0 1 0 0 0 -1 0 0 0 0 0 0 0 0 606619]

[-1 2 -1 0 0 0 0 0 0 0 0 0 1 0 0 -1 0 1497049]

[0 1 0 0 -1 0 1 0 0 -1 0 0 0 0 0 0 0 820689]

[2 0 -2 -1 0 1 0 1 0 0 0 0 0 0 0 0 0 565973]

[0 -3 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 175790]

[-3 -1 1 0 0 1 0 0 -1 0 0 0 0 0 0 0 0 154184]

[5 0 0 -2 -1 0 0 0 0 0 1 0 0 0 0 0 0 1484281]

[0 -1 -1 1 -1 0 0 0 0 0 0 0 0 0 0 0 1 867367]

[2 0 -1 -1 -1 0 0 0 0 1 0 0 0 0 0 0 0 1476243]

[0 0 2 0 1 -1 0 0 0 0 -1 0 0 0 0 0 0 475218]

[-1 1 0 0 0 -1 0 0 0 -1 0 0 0 1 0 0 0 818415]

[0 -1 0 1 0 -1 0 0 0 0 0 0 0 0 0 1 0 501808]

[-3 2 1 0 0 1 0 -1 0 0 0 0 0 0 0 0 0 1116478]

[5 1 1 -1 0 0 0 0 0 0 0 0 0 0 -1 0 0 608042]

[4 1 -1 -2 0 1 0 0 0 0 0 0 0 0 0 0 0 1359764]

[1 -1 0 0 0 1 0 0 0 0 1 0 0 0 0 -1 0 909391]

[0 3 0 0 1 0 0 0 0 -2 0 0 0 0 0 0 0 1346976]

[-1 0 -1 0 0 0 1 0 1 0 0 -1 0 0 0 0 0 620980]


solve system modulo prime divisors of p - 1 = 2 * 3 * 166667

(16:21) gp > h1=matker(hh*mod(1,166667))
%5 = 
[Mod(166666, 166667)]

[Mod(79057, 166667)]

[Mod(40955, 166667)]

[Mod(109815, 166667)]

[Mod(68414, 166667)]

[Mod(155104, 166667)]

[Mod(78282, 166667)]

[Mod(137318, 166667)]

[Mod(104522, 166667)]

[Mod(76279, 166667)]

[Mod(137104, 166667)]

[Mod(96162, 166667)]

[Mod(8333, 166667)]

[Mod(578, 166667)]

[Mod(118233, 166667)]

[Mod(122539, 166667)]

[Mod(44579, 166667)]

[1]

(16:22) gp > h2=matker(hh*mod(1,3))
%6 = 
[Mod(2, 3)]

[Mod(0, 3)]

[Mod(1, 3)]

[Mod(1, 3)]

[Mod(1, 3)]

[Mod(2, 3)]

[Mod(0, 3)]

[Mod(1, 3)]

[Mod(2, 3)]

[Mod(2, 3)]

[Mod(1, 3)]

[Mod(0, 3)]

[Mod(2, 3)]

[Mod(0, 3)]

[Mod(0, 3)]

[Mod(0, 3)]

[Mod(0, 3)]

[1]


(16:23) gp > h3=matker(hh*mod(1,2))
%7 = 
[Mod(1, 2)]

[Mod(1, 2)]

[Mod(1, 2)]

[Mod(1, 2)]

[Mod(1, 2)]

[Mod(0, 2)]

[Mod(1, 2)]

[Mod(0, 2)]

[Mod(1, 2)]

[Mod(0, 2)]

[Mod(1, 2)]

[Mod(0, 2)]

[Mod(1, 2)]

[Mod(1, 2)]

[Mod(0, 2)]

[Mod(0, 2)]

[Mod(1, 2)]


(16:35) gp > gp > for(k=1,bb,x=chinese(h1[k,1],h2[k,1]);\
print(cc[k],": ",-chinese(x,h3[k,1])))

2: Mod(1, 1000002)
3: Mod(254277, 1000002)
5: Mod(292379, 1000002)
7: Mod(556853, 1000002)
11: Mod(764921, 1000002)
13: Mod(511564, 1000002)
17: Mod(421719, 1000002)
19: Mod(196016, 1000002)
23: Mod(395479, 1000002)
29: Mod(90388, 1000002)
31: Mod(362897, 1000002)
37: Mod(903840, 1000002)
41: Mod(991669, 1000002)
43: Mod(166089, 1000002)
47: Mod(381768, 1000002)
53: Mod(710796, 1000002)
59: Mod(622089, 1000002)


compute discrete log of x = 61                                                                      ^

(16:38) gp > work5(61,1000003,17)

after about 3 to 4 tries:

k = 12235, [2, -5; 3, 1; 5, -2]

this means:

x * g^k = [2, -5; 3, 1; 5, -2]

so log(x) = - 12235 - 5 + 254277 - 2*292379 
          = -342721  = 657281  modulo  1000002

check
(16:39) gp > mod(2,1000003)^657281

%18 = Mod(61, 1000003)

OK!!


=======================================================================

(16:40) gp > p=nextprime(10^10)
time = 0 ms.
%21 = 10000000019


time = 0 ms.
(16:41) gp > work4(p,10)
time = 11,061 ms.
time = 9,063 ms.
time = 9,459 ms.
time = 11,415 ms.
time = 8,990 ms.

(16:43) gp > work4(p,20)
time = 1,003 ms.
time = 1,229 ms.
time = 717 ms.
time = 825 ms.
time = 1,079 ms.

(16:43) gp > work4(p,30)
time = 697 ms.
time = 502 ms.
time = 665 ms.
time = 514 ms.
time = 492 ms.

(16:43) gp > work4(p,50)
time = 284 ms.
time = 412 ms.
time = 320 ms.
time = 327 ms.
time = 332 ms.

(16:44) gp > work4(p,80)
time = 239 ms.
time = 244 ms.
time = 235 ms.
time = 265 ms.
time = 297 ms.

(16:44) gp > work4(p,100)
time = 318 ms.
time = 271 ms.
time = 261 ms.
time = 250 ms.
time = 327 ms.

(16:44) gp > work4(p,200)
time = 443 ms.
time = 426 ms.
time = 462 ms.
time = 404 ms.
time = 407 ms.

(16:45) gp > work4(p,400)
time = 977 ms.
time = 999 ms.
time = 1,009 ms.
time = 991 ms.
time = 1,013 ms.