|
Bill Allombert on Wed, 21 Jun 2023 13:42:21 +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: Wed, 21 Jun 2023 13:37:40 +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=1687347450; c=relaxed/relaxed; bh=xS7R4KzCXpAtfVmJVGd1a7HK1Hjt7ZvAy3qbEsBoQiY=; h=DKIM-Signature:Date:From:To:Subject:Message-ID:Mail-Followup-To: References:MIME-Version:Content-Type:Content-Disposition: In-Reply-To; b=kIrMfZC8+G6+85yEjRBNcJFqwePyWkDiR3AyeWD6GkL1aIQ1TDHND/n66Vp1qnvJJPiGYQtgAG+aAbmgvqTfEdVXtLQyA9qGoDFzO1BrjJQLA03AtHSIr45NCg4k2NjXeZGABOGopjJfLYaIMZ6ZjQtJBLhvBZ/weF+vXYjIvGMHmEuufVXuIxXWmvF5LkZId9nQIlWC4aSPF7Vw40FPE/CrMr8IINxptLb8xVqQsNaHY1icbBHykgcEXv5of7QjlWkxoFJiAPzaPhVyhj2NzTXmhBK995Z3AhoSXTwxt2eGXv8uaIs0sqgsTlta9xWje2bMjGOMNNj+EGHWy74QUmSpZA0DpcN3H1SOTEnt1ksff/Gn/dzPpN1uQnJ/5CPs2BjFY028H6g0cmpaHfIilETo+h15YP/OwxQPZfjXCeFQVPnYfM7UFUOFxWsFapMf2Nlhxa0WuRD/Z8wFINH7uErtsNVmOGOcL+gGtqeBA8P5M2hTJFxbSOWcCXorFsaWATR1JVz81TO5V4aEovIdVVZvoFCl4ON5GE61IsjVOgUyh9J7JdgI9rRwT4/kNSuX1G2dpuzrsXjxWIx1zAJYKzuanNwJDg7tSc3o2ofArN+mcMG5DBHf2fd3w0X+M1BxQr6ouYJf/VoLSmLGOCwcHoPpHm2yBETJOU9EJRDeGww=
- Arc-seal: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1687347450; cv=none; b=BRVt2t3wivubBnIAgZqHXZt9VXz9TBSxj2w9NAsSSOKm4g0JNftrYmgKcU+OfXktga1LPqj/cU2V2xSHnOmxTL5ILLW3hZsUdDh8rY+eWwOE+YXC0xwfXFsP0yi2tgua+jOty+9JXKHQrIiyK/McCBOYxhEuyNl17yg4ZEZRDRmU3rkSPf+7GK5abRXJYew9aRtL49wZcvSQDXdux1uGjOOtvT+1Ms5J+1HK2OKqUPL3mHA4oKJLU0lqza62ft9XU+YqM54Xwr8QowrFvYQuJ7PbkWZqfWEX9wn56wGqzb+Iz2/En3zm1d5gkEeNms3NAFGPG6EK1XFDgVRQuLfRn7kJj7LFRJInFmuUeBL4rVtCHtaSmZ97EIunSYETSnO+HHYJURUHiaKYSFVuWRbgzL/bZlZEIOwdIATnfcrGI/ZoztraONbNK268dKbL5mjJaocEXHpgxNflUNq/7ROu1EqOvVnn15y5mpkcgIkDJ/TozSdfB0t1kUhT+BI2dDabqVr9bsuva0+HCFZ8AVSgFKGzWNcGy5xTAubi4Gg2u2tDfkW0VLFXXZRYdGZyBJ4CcBJYkkdb3OREGdjSE67kHXRjTXIUB0CGQR7nHYg0iBf2zKCzB/ZmS4MUw9fgovEBPa1OAsSyv8MB1tJT1GtWfNDpAXHtKlUqXyiTv1+PfcI=
- Authentication-results: smail; arc=none
- Delivery-date: Wed, 21 Jun 2023 13:42:21 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=math.u-bordeaux.fr; s=2022; t=1687347450; bh=xS7R4KzCXpAtfVmJVGd1a7HK1Hjt7ZvAy3qbEsBoQiY=; h=Date:From:To:Subject:References:In-Reply-To:From; b=dE2f8+2nLHnbiBDcEiqmRhGxiYGS4hJDL0+/vFCpBaR0OPi9hBM6p4LNATTRVYQ+Q NEeDhK5mCEi/9qCEDpLap0nJA0Phyk431H8fE4HxE9yuEO9UEqiANRfppcK5zyz3b1 cyav6V0NKvhqQktc9567inINbXiMtLVKbyQsL3Xm/nmUNEJ/nZbp6quQEm/KemHXw6 j5ehGM+mM1fcUY2lg1XYzuYjXDnNH/Dt3aaINH6JdSRak2idLhw0m6sAiymi+emv2C 53CegK3hCV+T692uUJZ2A4XKBW0V9pUpYRwWo1mdpj+ib3re7MpCOAni+V66jF1l2f xNmMUpNWzNHq1cuaK8V5vXQEiqjXiJ4W2PlvJgjOdwfx8K10/e2uHS1Csw3yCTGnUJ vyJd2YXy5rt8Hrc4p07/3KBva+H4tWIBaJ59YUR2aoxgKDEsMsJmKgjnvtnf2LBzl6 h0+vUXDUtAhMWKNUYX5VRn6EHnvYeBi6iKKbmN2mt6/MW0npa7FV7x83zULN9WerYm QQy1CS4CQG0lhF7FkdGpqTkWoFGFdZghLEQv2KUcUT7oZzxF+8lO2kX8DgK4PAY1kd 6ezFCEdv/3B+grIwpzltvTAKI5gDrT5VQWooKpoNu7FYqAuW3hT5Js7L8Saxpzqmbi oorIHNLlPr9HgojWN4Zv1CMs=
- In-reply-to: <3f13b3ca89d86d8309ac70bf0fbc59b3@stamm-wilbrandt.de>
- Mail-followup-to: pari-users@pari.math.u-bordeaux.fr
- References: <3f13b3ca89d86d8309ac70bf0fbc59b3@stamm-wilbrandt.de>
On Wed, Jun 21, 2023 at 01:02:48PM +0200, hermann@stamm-wilbrandt.de wrote:
> Pari userguide states that integers must be in absolute value less than
> 2^536870815 on 64bit systems.
>
> My n has only 79 decimal digits, but I assume the following error is because
> of said integer size restriction:
>
> ? #digits(n)
> %152 = 79
> ? Mod(2^(n+1),n)
> *** at top-level: Mod(2^(n+1),n)
> *** ^---------
> *** _^_: overflow in lg().
> *** Break loop: type 'break' to go back to GP prompt
> break>
>
> So it seems "Mod()" computes LHS value first before applying RHS modulo.
> Is that true?
Mod is not a modulo operation, it is a constructor for the ring Z/nZ.
(hence the capital M).
So if you want to compute in Z/nZ, map 2 to Z/nZ with Mod(2,n) and then
apply ^(n+1)
Mod(2,n)^(n+1)
Cheers,
Bill