Fast discrete log() allows factoring RSA semiprimes easily

demo_executions.md

See comment below.

Pointed to by this cado-nfs mailing list posting:
https://sympa.inria.fr/sympa/arc/cado-nfs/2025-05/msg00005.html

Having fast discrete log() allows to factor RSA semiprimes easily.

eulerphi(pq)=(p-1)(q-1)

So determining Mod(3,n)^n and then determining znlog() gives you p+q-1.
And you know p*q=n. That can be solved easily.

Demo with PARI/GP and Mathematica on Raspberry Pi5 for 61 decimal digit semiprime:

pi@raspberrypi5:~ $ gp 
Reading GPRC: /etc/gprc
GPRC Done.

                  GP/PARI CALCULATOR Version 2.15.5 (released)
              arm64 running linux (aarch64 kernel) 64-bit version
          compiled: Mar  8 2024, gcc version 12.2.0 (Debian 12.2.0-14)
                           threading engine: pthread
                 (readline v8.2 enabled, extended help enabled)

                     Copyright (C) 2000-2022 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and comes 
WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?18 for how to get moral (and possibly technical) support.

parisizemax = 3000008704, primelimit = 500000, nbthreads = 4
? 
...
? M=10^30
%40 = 1000000000000000000000000000000
? p=nextprime(random(M)+M);p
%41 = 1796661611918389511809994302463
? q=nextprime(random(M)+M);q
%42 = 1835662736201165479917987520529
? n=p*q
%43 = 3298064770561707395374626326810074602655535707456626247762927
? #
   timer = 1 (on)
? znlog(Mod(3,n)^n,Mod(3,n))
cpu time = 15,769 ms, real time = 15,127 ms.
%44 = 3632324348119554991727981822991
? #binary(n)
%45 = 202
? #digits(n)
%46 = 61
? 

Can be factored easily with integer solution quadratic formula:

? quadint(a,b,c)={s=sqrtint(b^2-4*a*c);return([(-b-s)\(2*a),(-b+s)\(2*a)])};
? quadint(1,-(3632324348119554991727981822991+1),3298064770561707395374626326810074602655535707456626247762927)
[1796661611918389511809994302463, 1835662736201165479917987520529]
? 

Or more clearly formulated using Mathematica Solve[...]:

https://www.wolfram.com/legal/agreements/wolfram-mathematica-raspberry-pi/

...
Permitted Uses and Installations

Subject to the terms of this Agreement and Your acceptance thereof, WRI grants You a non-exclusive license to use the Product solely for personal or educational purposes on a Raspberry Pi computer. You are also authorized to:

a. maintain one archival copy of the Software on storage media; and
b. author and distribute Computable Document Format™ (CDF) files consistent with any associated licensing terms.

...

(that free license was the reason I bought fastest Raspberry Pi5)

pi@raspberrypi5:~ $ wolfram
Mathematica 14.1.0 Kernel for Linux ARM (64-bit)
Copyright 1988-2024 Wolfram Research, Inc.

In[1]:= Solve[{p<q,p+q-1==3632324348119554991727981822991,                          
p*q==3298064770561707395374626326810074602655535707456626247762927}, {p,q}] 
                                                                                

Out[1]= {{p -> 1796661611918389511809994302463, 
 
>     q -> 1835662736201165479917987520529}}

In[2]:=     

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:~$