hermann on Sun, 01 Jun 2025 10:05:50 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

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


On cado-nfs list somebody stated that fast discrete log would not help in factoring.

I disagreed and provided method and sample executions to factor semiprime in this gist:
https://gist.github.com/Hermann-SW/79ebd53c248b272c96b03a690cb488b7

Later I was able to use improved znlog() method to factor 79 decimal digit semiprime
in 3:09min (still not competitive with msieve or cado-nfs):
https://gist.github.com/Hermann-SW/79ebd53c248b272c96b03a690cb488b7?permalink_comment_id=5600123#gistcomment-5600123

znlog is documented in 3.8.126:
https://pari.math.u-bordeaux.fr/pub/pari/manuals/2.17.2/users.pdf#page=241

Under "This function uses" the algorithms used are described.

Since N is not prime, linear sieve index calculus method is not used.

Since 79 decimal digit cannot be factored in 3min with PARI/GP, the condition
"q|p − 1 and p is an odd prime divisor of N" cannot be checked for p.
So Pohlig-Hellman is not used.

Shanks and Pollard algorithms refer to q and therefore to p as well,
and cannot be used.

So which algorithm is used for semiprime N=p*q?

Regards,

Hermann.