|
Bill Allombert on Fri, 23 Jun 2023 13:22:37 +0200
|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|
Re: How to compute "Mod(2^(n+1), n)" for very big n?
|
- To: pari-users@pari.math.u-bordeaux.fr
- Subject: Re: How to compute "Mod(2^(n+1), n)" for very big n?
- From: Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>
- Date: Fri, 23 Jun 2023 13:17:55 +0200
- Arc-authentication-results: i=1; smail; arc=none
- Arc-message-signature: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1687519065; c=relaxed/relaxed; bh=Dh0wzskkJYLbh+DVc+uGzYXgUDg5zaJA1Pwb3ur3ecM=; h=DKIM-Signature:Date:From:To:Subject:Message-ID:Mail-Followup-To: References:MIME-Version:Content-Type:Content-Disposition: In-Reply-To; b=HyKIpGKa6nNsOh817hJrokhbwFF9MttYmY8/xDGReUJvQusesxgAZ41l9iqMRMkfT4Z60aUwg3wQojn9OZlqRqLghOKn0EDYJA2vbKIAid8SkWKecfCl1okrc+tSs62u0IGXD9bfkabwsCxH1DCfeih2/mFAMJgC9B3f91EMe5TfBkD/B4SD7wDlgSYyWtrm+vw3xBwRJJPw6PKLCgwDeCRXFncbSLNUgX+VO59wsmSP6DOQEj8ReT1LhrccxFaRgvgDg7z3629+1jiRPr2khH8w4Hkppg6VgZE/mcP6oFbdZjZ78/k2ksAqGeBqOaFqBnbQla2AVlpE9+XFNkHtVsuArsQqbP/jpKlmBPmE0MMx0hs2Fc6F1J6JfbAZ2JLQ9dhLda7dPsHwZPJH5kRPvIwvpfBt08cj9iCRHT45suUiRDyulphtRuogkYSYyuWno6Jl57lXMZu2w/mK9atpYyhcI5HjCys9G4RPEXqiQA6i+NZQG6paBGpHHytx8xGh7MVKoLR5GV6IlGaZkHrcYg0fiuptTfPtKGebMLas+tYJgPt0yIoLlJ/6iLXXRYYYVxZNFFHHiTNXhpiky2kjTJZHZdMJrjWP0DgZcJbdXTsdVFw8gkJd4JvFiO1WXBwADyNADEILTvn+m1CI25pzICVraA09DLZ8Zay4HUtEEEQ=
- Arc-seal: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1687519065; cv=none; b=MERUBkeOW0YlzqLrHQd6tOwfTsLcR7GJQYWtz7QQbSLc1MAdunkbykVcG7P3YFjHbVJFNZLIKlH47VYk7S+LRfpY4dy6reqaQ8EOF2GzRZ32V0dk74/EWKVRmS+wxBiG6kBEM/GNLf6FhTA9B1F95sHMYMThZYOAj90mTjMYNy9+RxXERn5/UISRwLCfzvRpP11V6UexxqJwOx+2vK+2hGMWUvqeyhvXYZWW3BfKn/N83L1uPLpB1LMtJxHB5RN5E7AjN0/aHqQNh+zijeXA3vCmw9bdq3UksVLX3P5anJ4zJfSBTd+rR/3f7XbpMWA368d8JZr6hyY+YU0kYqHokg32DevQuMPMIcxXPpIV9QCbxkE31OMMQuFLOgucfl2uYteKUJ6+m16VqSOBmG217r047+s4tx8oQh1Ct7xCx2Gpx4eE2KgsGOYSTCglOkInH6KQN50WL5X3vxHSHm9GZdzteqGOGLtUdgSqK5Rcfb8+VOe3zRwT/hGK4PFsbXlUiqby/ulqfZ/kWP92lZzvere0IEaB/32ZmTJy6XbPLPXie0RMnpJ1IIZ3+eEfTn5gqIBAk3e8vXrZPQ74hdXZoqYaU3xraNfo7LkDXN46fKL0DEEOyUmvZEl+xpOLy8FBpfZMWMMIICwEoG1iSt/qk441ryDBilNkuv1YUI5Hm1Y=
- Authentication-results: smail; arc=none
- Delivery-date: Fri, 23 Jun 2023 13:22:37 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=math.u-bordeaux.fr; s=2022; t=1687519065; bh=Dh0wzskkJYLbh+DVc+uGzYXgUDg5zaJA1Pwb3ur3ecM=; h=Date:From:To:Subject:References:In-Reply-To:From; b=lJMqoHP34aYmflOAJarkQ2bQhvqXfxFQ8Tw4QEDNTrrbAlcWstOfcPX9nU8Pg+gED cul9Q1+IpjvtsvkOU7iHh7cz/cTm4koYQfoZ+kaTvf8nRkIwD2KrURLLL1AlqN1nOO vXS64EZCC0pZGBjxxrzKkNGswK40Jn+VRcR/D28AixvbWmDy/9fzjjDSK7MqaG7qPX XGP3vMwPqZYoyUPPnjPLMMtyOgy+JrWCKGZn3Gjo71fYWDNipEMIXmE7TogSUANbUj LF12JtxIvtDOz/qK3IPCgn7/Lgd09P4g10yv8PQWZ3XAri7lf1FycCvbAyBtV0Bdoq fAPxJ2+ZZZU+rOda8IFdiDBe6tpDD6ENC1oxqCqypCkytM1R5fOrxA0h0xiK78asNr odZBFaze7hK8JrKA6sltEBf08Fal1SDxTwIza2LMFSdJ7CZq/CM/aln/7Yh62vfgqc WPC4ZsCf4mgD1aZXgYeAlw1eu9DVw4aJo5J4iaUtWQGfLc0ivtUBNY3sMf5Ec2l3/M OViSWvIrXy68wcS8lIYbDturIDKpy9bKFEv+c9KLDBYUdIzD/iMEUpMIEx2UORe+KN K/gZuY89O14xPt4wgACg2aRxGFFCWFKjAlXkm2AVz7Zg3NlUhNOIQ7qCdwCg+5PCEx j4uIrZCY4ZkngTVEfjBwrR1Q=
- In-reply-to: <f841c1a76e66f57c8cccc932da66b897@stamm-wilbrandt.de>
- Mail-followup-to: pari-users@pari.math.u-bordeaux.fr
- References: <3f13b3ca89d86d8309ac70bf0fbc59b3@stamm-wilbrandt.de> <ZJLZszjqOCinDkv3@jurong> <ebeeaa417d6426893a751caca375d469@stamm-wilbrandt.de> <ZJMemdxXSleyjSv1@seventeen> <437223146652ba0008a5099dde1f1292@stamm-wilbrandt.de> <f841c1a76e66f57c8cccc932da66b897@stamm-wilbrandt.de>
On Thu, Jun 22, 2023 at 07:30:27AM +0200, hermann@stamm-wilbrandt.de wrote:
> Anyway, here is gp session (with definition of function "fact()" factoring
> given sum and product):
>
> RSA_numbers_factored/pari:$ gp-2.15 -q
> ? \r RSA_numbers_factored
> ? [l,n,p,q] = rsa[3][1..4];
> ? [l, l==#digits(n) && n=p*q]
> [100, 1]
> ? d2 = 2 * sqrtint(n)
> 78041143710802531024579146678968742037810013800388
> ? #digits(p+q)
> 50
> ? #digits(p+q-d2)
> 47
> ? znlog(Mod(2, n)^(n+1-d2), Mod(2, n))
> 28775177062023928913461369238354205970422561872
> ? ##
> *** last result computed in 11h, 12min, 15,497 ms.
Well, if you do addprimes([p,q]) it only take 45 minutes.
so taking 10h30 to factor RSA100 is not that bad.
Cheers,
Bill.