hermann on Sun, 01 Jun 2025 11:50:18 +0200


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

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

On 2025-06-01 10:51, Bill Allombert wrote:

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.


Thanks, I used debug log too seldom.
Factoring the 79 decimal digits semiprime took 141s of the 185s znlog() took on AMD 7950X: 
https://gist.github.com/Hermann-SW/79ebd53c248b272c96b03a690cb488b7?permalink_comment_id=5600462#gistcomment-5600462

Regards,

Hermann.