Fast discrete log() allows factoring RSA semiprimes easily

demo_executions.md

See comment below.

On fast AMD 7950X CPU with single core boost clock above 5.4GHz, the znlog() method of factoring can be done even for a 79 decimal digit RSA semiprime. Any exponent lower n, that still is above (p-1)*(q-1) is good, and faster than exponent n. Since n - 2*sqrtint(n) > (p-1)*(q-1), I used that to reduce runtime from 221s to only 189s:

hermann@7950x:~$ cat 79.gp 
n=7293469445285646172092483905177589838606665884410340391954917800303813280275279;
print(znlog(Mod(3,n)^eval(getenv("exp")),Mod(3,n)));
hermann@7950x:~$ 

hermann@7950x:~$ exp="n" perf stat -e cycles,task-clock gp -q < 79.gp
9447104136878167876008523981447380846703

 Performance counter stats for 'gp -q':

 1.210.399.153.364      cycles                           #    5,482 GHz                       
        220.808,29 msec task-clock                       #    1,000 CPUs utilized             

     220,830156627 seconds time elapsed

     215,142495000 seconds user
       5,664270000 seconds sys


hermann@7950x:~$ 

hermann@7950x:~$ exp="n-2*sqrtint(n)" perf stat -e cycles,task-clock gp -q < 79.gp
4045819309992754986324896359002457071397

 Performance counter stats for 'gp -q':

 1.032.300.598.464      cycles                           #    5,478 GHz                       
        188.454,92 msec task-clock                       #    1,000 CPUs utilized             

     188,468852904 seconds time elapsed

     183,628513000 seconds user
       4,825531000 seconds sys


hermann@7950x:~$

The 2nd computation still allows to factor n:

hermann@7950x:~$ gp -q
? quadint(a,b,c)={s=sqrtint(b^2-4*a*c);return([(-b-s)\(2*a),(-b+s)\(2*a)])};
? n=7293469445285646172092483905177589838606665884410340391954917800303813280275279;
? quadint(1,-(9447104136878167876008523981447380846703+1),n)
[848184382919488993608481009313734808977, 8598919753958678882400042972133646037727]
? n==848184382919488993608481009313734808977*8598919753958678882400042972133646037727
1
? quadint(1,-(4045819309992754986324896359002457071397+2*sqrtint(n)+1),n)
[848184382919488993608481009313734808977, 8598919753958678882400042972133646037727]
? 

The znlog() method with 189s is not competitive:

• msieve needs 66s to factor the 79 decimal digit number (single threaded)
• cado-nfs needs 52s to factor it (multi-threaded)

I learned from Bill on pari-users list that GP znlog() does factor first:
https://pari.math.u-bordeaux.fr/archives/pari-users-2506/msg00001.html

This can be seen by debug=3 log:

hermann@7950x:~$ cat 79.gp 
\g3
n=7293469445285646172092483905177589838606665884410340391954917800303813280275279;
print(znlog(Mod(3,n)^eval(getenv("exp")),Mod(3,n)));
hermann@7950x:~$ 

So factoring with znlog() does not help for big RSA semiprimes.
But the method demonstrated above would allow to factor easily in case of an efficient discrete log algorithm.
141s of the 185s for znlog() are taken by factoring the 79 decimal digit semiprime:

hermann@7950x:~$ exp="n-2*sqrtint(n)" perf stat -e cycles,task-clock gp -q < 79.gp
   debug = 3
IFAC: cracking composite
	7293469445285646172092483905177589838606665884410340391954917800303813280275279
IFAC: factor 8598919753958678882400042972133646037727
	is prime
IFAC: factor 848184382919488993608481009313734808977
	is prime
IFAC: prime 848184382919488993608481009313734808977
	appears with exponent = 1
IFAC: prime 8598919753958678882400042972133646037727
	appears with exponent = 1
IFAC: found 2 large prime (power) factors.
IFAC: cracking composite
	389549685329286893286221028002792699
IFAC: factor 2451185072829526835550681952913
	is composite
IFAC: factor 158923
	is prime
IFAC: prime 158923
	appears with exponent = 1
IFAC: cracking composite
	2451185072829526835550681952913
IFAC: factor 17616807254846020469
	is prime
IFAC: factor 139139007277
	is prime
IFAC: prime 139139007277
	appears with exponent = 1
IFAC: prime 17616807254846020469
	appears with exponent = 1
IFAC: found 3 large prime (power) factors.
bnd=63688 Size FB=6384 extra gen=22262 
0% 0% 0% 0% 1% 1% 2% 2% 2% 3% 3% 3% 4% 4% 4% 5% 5% 5% 5% 6% 6% 6% 7% 7% 7% 8% 8% 8% 9% 9% 10% 10% 10% 11% 11% 12% 12% 12% 13% 13% 14% 14% 14% 15% 16% 17% 18% 19% 19% 19% 20% 20% 21% 21% 22% 22% 23% 23% 24% 24% 25% 26% 26% 27% 27% 28% 28% 29% 30% 30% 31% 31% 32% 32% 33% 34% 34% 35% 36% 36% 37% 38% 39% 39% 40% 41% 41% 42% 43% 43% 44% 45% 45% 46% 47% 47% 48% 49% 49% 50% 51% 52% 52% 53% 54% 55% 55% 56% 57% 58% 58% 59% 60% 61% 61% 62% 63% 64% 64% 65% 66% 67% 68% 68% 69% 70% 71% 72% 73% 73% 74% 75% 76% 77% 78% 79% 80% 81% 81% 82% 83% 84% 85% 86% 87% 88% 89% 90% 90% 91% 
Time  53075 relations, 28647 generators: 6584
Time structured elimination (53075 -> 10206): 644
Wiedemann: deg. minpoly: 10205
Time Wiedemann left kernel: 32711
Time found 28378/28647 logs: 57
Time  log element: 139
Time  log generator: 597
IFAC: cracking composite
	97627115897731237754199011200936327
IFAC: factor 134611158882680922107
	is prime
IFAC: factor 725252770335461
	is prime
IFAC: prime 725252770335461
	appears with exponent = 1
IFAC: prime 134611158882680922107
	appears with exponent = 1
IFAC: found 2 large prime (power) factors.
4045819309992754986324896359002457071397

 Performance counter stats for 'gp -q':

 1,018,528,362,549      cycles                           #    5.536 GHz                       
        183,996.65 msec task-clock                       #    1.000 CPUs utilized             

     184.023989460 seconds time elapsed

     179.301279000 seconds user
       4.694655000 seconds sys


hermann@7950x:~$ 

hermann@7950x:~$ cat 79.x.gp 
\g3
n=7293469445285646172092483905177589838606665884410340391954917800303813280275279;
print(factor(n));
hermann@7950x:~$ 

hermann@7950x:~$ perf stat -e cycles,task-clock gp -q < 79.x.gp
   debug = 3
IFAC: cracking composite
	7293469445285646172092483905177589838606665884410340391954917800303813280275279
IFAC: factor 8598919753958678882400042972133646037727
	is prime
IFAC: factor 848184382919488993608481009313734808977
	is prime
IFAC: prime 848184382919488993608481009313734808977
	appears with exponent = 1
IFAC: prime 8598919753958678882400042972133646037727
	appears with exponent = 1
IFAC: found 2 large prime (power) factors.
[848184382919488993608481009313734808977, 1; 8598919753958678882400042972133646037727, 1]

 Performance counter stats for 'gp -q':

   777,512,023,509      cycles                           #    5.543 GHz                       
        140,258.44 msec task-clock                       #    1.000 CPUs utilized             

     140.265773314 seconds time elapsed

     140.187513000 seconds user
       0.070996000 seconds sys


hermann@7950x:~$