Re: Which znlog() algorithm is used for (ℤ/Nℤ)* with semiprime N=p*q?

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Sun, Jun 01, 2025 at 10:05:37AM +0200, hermann@stamm-wilbrandt.de wrote:
> On cado-nfs list somebody stated that fast discrete log would not help in
> factoring.

It is a matter of definition. Shor algorithm for factoring on quantum computer
rely on fast discrete log. However he does not use the same definition
of 'fast discrete log' as used in crypto.

In crypto, we normally have a base g _whose order is known_, which is not the
case for Shor algorithm.

> Since 79 decimal digit cannot be factored in 3min with PARI/GP, the
> condition

Why not ? factor took 7 minutes on my laptop.

Do
\g3
n=7293469445285646172092483905177589838606665884410340391954917800303813280275279;
znlog(Mod(3,n)^n,Mod(3,n))

The first lines printed are
IFAC: cracking composite
7293469445285646172092483905177589838606665884410340391954917800303813280275279

Cheers,
Bill.