|
Bill Allombert on Sun, 01 Jun 2025 10:51:31 +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?
|
- To: pari-users@pari.math.u-bordeaux.fr
- Subject: Re: Which znlog() algorithm is used for (ℤ/Nℤ)* with semiprime N=p*q?
- From: Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>
- Date: Sun, 1 Jun 2025 10:51:27 +0200
- Delivery-date: Sun, 01 Jun 2025 10:51:31 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/simple; d=math.u-bordeaux.fr; s=2022; t=1748767888; bh=BaAc0nrfcEwFXbmCz2QpZkyfIYyR7bso7hsgCrLA3y8=; h=Date:From:To:Subject:References:In-Reply-To:From; b=NXa+ajF5LrHp6y7qTV8t8S+OBN8HvBv4bB+myAeTleu6IRAYr6D0GMlyWv3koSFBg eVMzbBYau+BVZm7+jsRFYL0Gwb4ceEzq5vCi0rIf8eVOmWPA9HUj5WDj5Sckg7JA2D bFgm7oLfHMQeDjoih1VHPXQl0yhRZcpEpXoTkh89ggdLZ8JbwrbaNyeHWClb+aghIa jC/6tc3VM560dq5JPNDurBXfbjscEgpDxcMmDeynSSq277oj6ADTxyv7E1HdU1RQdf e5QMg94tnTpS2itIXJxF6COTjTu4D2g5FF1sAhHHecarmN5aypF5d8kFlZfW+f85w6 JNDdtOQt9vd+/B5oBC+7N6gb6Q+BRh7agaWgCtUWEu0XZsNXGIqDobhC0rWaMbVHGK mNC7CjIhNczU+oQvdyHAQdZFNHL/p7r8YG5w37DGbKaoaPoB0AcFK3Z4eCQ8xna0U0 fWY5BnBPh+UXCh+v7Nxy+ShT55GZ69DGSyQSguM7WQ7EoehS2xx5yNFX79gMgs1o35 WA4ojmm62siDdNqQiuGA/DQ/4eNM64KI24hyf7GsXcviiBVza9rqGoGeAyKNwE5NTe ZrD0CUM8nB0rsghwAb9qiyKPQBtQ2ZoUoYBF4I4aB9zUl3aIUVpss3rhXGOYpN5hWj PUmZD+vP4Waj2nzeFr3eh6ig=
- In-reply-to: <c12cd1f33a59166768e3180571749218@stamm-wilbrandt.de>
- Mail-followup-to: pari-users@pari.math.u-bordeaux.fr
- References: <c12cd1f33a59166768e3180571749218@stamm-wilbrandt.de>
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.