Re: How to compute "Mod(2^(n+1), n)" for very big n?

Andreas Enge on Wed, 21 Jun 2023 13:11:07 +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: hermann@stamm-wilbrandt.de
Subject: Re: How to compute "Mod(2^(n+1), n)" for very big n?
From: Andreas Enge <andreas.enge@inria.fr>
Date: Wed, 21 Jun 2023 13:06:27 +0200
Authentication-results: mail2-relais-roc.national.inria.fr; dkim=none (message not signed) header.i=none; spf=SoftFail smtp.mailfrom=andreas.enge@inria.fr; dmarc=fail (p=none dis=none) d=inria.fr
Cc: pari-users@pari.math.u-bordeaux.fr
Delivery-date: Wed, 21 Jun 2023 13:11:07 +0200
Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=inria.fr; s=dc; h=date:from:to:cc:subject:message-id:references: mime-version:in-reply-to; bh=bg2nOX2Kb/8kaEF7vOmc9ugU6cXC5TjbZNHKq/gpVns=; b=r/cojgdUpvecYxFkCArhcmEKc/SPjBz0UZJF/CehL/9m8itEPHHCnJVS ojrrGZdf3l8ml2xLfbNzEBJ2X3dhou8EYW47HzS6ObP3m1rPXdg06IbSG snaHmUiqCggEUDzCKJBj3k5YhgWqDfkNGnQbhylFzyqpqBPERzA/jH+2a s=;
In-reply-to: <3f13b3ca89d86d8309ac70bf0fbc59b3@stamm-wilbrandt.de>
References: <3f13b3ca89d86d8309ac70bf0fbc59b3@stamm-wilbrandt.de>

Am Wed, Jun 21, 2023 at 01:02:48PM +0200 schrieb hermann@stamm-wilbrandt.de:
> ? Mod(2^(n+1),n)

Do it the other way round:
   Mod(2,n)^(n+1).
This way, exponentiation happens directly in Z/nZ (by successive squaring
and multiplying, each followed by a reduction modulo n), instead of trying
to compute integers that may not fit into the universe.

Andreas

Follow-Ups:
- Re: How to compute "Mod(2^(n+1), n)" for very big n?
  - From: hermann@stamm-wilbrandt.de

References:
- How to compute "Mod(2^(n+1), n)" for very big n?
  - From: hermann@stamm-wilbrandt.de

Prev by Date: How to compute "Mod(2^(n+1), n)" for very big n?
Next by Date: Re: How to compute "Mod(2^(n+1), n)" for very big n?
Previous by thread: How to compute "Mod(2^(n+1), n)" for very big n?
Next by thread: Re: How to compute "Mod(2^(n+1), n)" for very big n?
Index(es):
- Date
- Thread