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? |
I disagreed and provided method and sample executions to factor semiprime in this gist:
https://gist.github.com/Hermann-SW/79ebd53c248b272c96b03a690cb488b7Later 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.