Which znlog() algorithm is used for (ℤ/N ℤ)* with semiprime N=p*q?
| Newsgroups | gmane.comp.mathematics.pari.user |
|---|---|
| Message-ID | <[email protected]> |
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.