|
Packit |
5c3484 |
/* mpz_powm(res,base,exp,mod) -- Set R to (U^E) mod M.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
Contributed to the GNU project by Torbjorn Granlund.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
Copyright 1991, 1993, 1994, 1996, 1997, 2000-2002, 2005, 2008, 2009, 2011, 2012
|
|
Packit |
5c3484 |
Free Software Foundation, Inc.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
This file is part of the GNU MP Library.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
The GNU MP Library is free software; you can redistribute it and/or modify
|
|
Packit |
5c3484 |
it under the terms of either:
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
* the GNU Lesser General Public License as published by the Free
|
|
Packit |
5c3484 |
Software Foundation; either version 3 of the License, or (at your
|
|
Packit |
5c3484 |
option) any later version.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
or
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
* the GNU General Public License as published by the Free Software
|
|
Packit |
5c3484 |
Foundation; either version 2 of the License, or (at your option) any
|
|
Packit |
5c3484 |
later version.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
or both in parallel, as here.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
The GNU MP Library is distributed in the hope that it will be useful, but
|
|
Packit |
5c3484 |
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
|
|
Packit |
5c3484 |
or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
Packit |
5c3484 |
for more details.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
You should have received copies of the GNU General Public License and the
|
|
Packit |
5c3484 |
GNU Lesser General Public License along with the GNU MP Library. If not,
|
|
Packit |
5c3484 |
see https://www.gnu.org/licenses/. */
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#include "gmp.h"
|
|
Packit |
5c3484 |
#include "gmp-impl.h"
|
|
Packit |
5c3484 |
#include "longlong.h"
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* TODO
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
* Improve handling of buffers. It is pretty ugly now.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
* For even moduli, we compute a binvert of its odd part both here and in
|
|
Packit |
5c3484 |
mpn_powm. How can we avoid this recomputation?
|
|
Packit |
5c3484 |
*/
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/*
|
|
Packit |
5c3484 |
b ^ e mod m res
|
|
Packit |
5c3484 |
0 0 0 ?
|
|
Packit |
5c3484 |
0 e 0 ?
|
|
Packit |
5c3484 |
0 0 m ?
|
|
Packit |
5c3484 |
0 e m 0
|
|
Packit |
5c3484 |
b 0 0 ?
|
|
Packit |
5c3484 |
b e 0 ?
|
|
Packit |
5c3484 |
b 0 m 1 mod m
|
|
Packit |
5c3484 |
b e m b^e mod m
|
|
Packit |
5c3484 |
*/
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#define HANDLE_NEGATIVE_EXPONENT 1
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
void
|
|
Packit |
5c3484 |
mpz_powm (mpz_ptr r, mpz_srcptr b, mpz_srcptr e, mpz_srcptr m)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mp_size_t n, nodd, ncnt;
|
|
Packit |
5c3484 |
int cnt;
|
|
Packit |
5c3484 |
mp_ptr rp, tp;
|
|
Packit |
5c3484 |
mp_srcptr bp, ep, mp;
|
|
Packit |
5c3484 |
mp_size_t rn, bn, es, en, itch;
|
|
Packit |
5c3484 |
mpz_t new_b; /* note: value lives long via 'b' */
|
|
Packit |
5c3484 |
TMP_DECL;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
n = ABSIZ(m);
|
|
Packit |
5c3484 |
if (UNLIKELY (n == 0))
|
|
Packit |
5c3484 |
DIVIDE_BY_ZERO;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
mp = PTR(m);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
TMP_MARK;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
es = SIZ(e);
|
|
Packit |
5c3484 |
if (UNLIKELY (es <= 0))
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
if (es == 0)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
/* b^0 mod m, b is anything and m is non-zero.
|
|
Packit |
5c3484 |
Result is 1 mod m, i.e., 1 or 0 depending on if m = 1. */
|
|
Packit |
5c3484 |
SIZ(r) = n != 1 || mp[0] != 1;
|
|
Packit |
5c3484 |
PTR(r)[0] = 1;
|
|
Packit |
5c3484 |
TMP_FREE; /* we haven't really allocated anything here */
|
|
Packit |
5c3484 |
return;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
#if HANDLE_NEGATIVE_EXPONENT
|
|
Packit |
5c3484 |
MPZ_TMP_INIT (new_b, n + 1);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
if (UNLIKELY (! mpz_invert (new_b, b, m)))
|
|
Packit |
5c3484 |
DIVIDE_BY_ZERO;
|
|
Packit |
5c3484 |
b = new_b;
|
|
Packit |
5c3484 |
es = -es;
|
|
Packit |
5c3484 |
#else
|
|
Packit |
5c3484 |
DIVIDE_BY_ZERO;
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
en = es;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
bn = ABSIZ(b);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
if (UNLIKELY (bn == 0))
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
SIZ(r) = 0;
|
|
Packit |
5c3484 |
TMP_FREE;
|
|
Packit |
5c3484 |
return;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
ep = PTR(e);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* Handle (b^1 mod m) early, since mpn_pow* do not handle that case. */
|
|
Packit |
5c3484 |
if (UNLIKELY (en == 1 && ep[0] == 1))
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
rp = TMP_ALLOC_LIMBS (n);
|
|
Packit |
5c3484 |
bp = PTR(b);
|
|
Packit |
5c3484 |
if (bn >= n)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mp_ptr qp = TMP_ALLOC_LIMBS (bn - n + 1);
|
|
Packit |
5c3484 |
mpn_tdiv_qr (qp, rp, 0L, bp, bn, mp, n);
|
|
Packit |
5c3484 |
rn = n;
|
|
Packit |
5c3484 |
MPN_NORMALIZE (rp, rn);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
if (SIZ(b) < 0 && rn != 0)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mpn_sub (rp, mp, n, rp, rn);
|
|
Packit |
5c3484 |
rn = n;
|
|
Packit |
5c3484 |
MPN_NORMALIZE (rp, rn);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
else
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
if (SIZ(b) < 0)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mpn_sub (rp, mp, n, bp, bn);
|
|
Packit |
5c3484 |
rn = n;
|
|
Packit |
5c3484 |
rn -= (rp[rn - 1] == 0);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
else
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
MPN_COPY (rp, bp, bn);
|
|
Packit |
5c3484 |
rn = bn;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
goto ret;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* Remove low zero limbs from M. This loop will terminate for correctly
|
|
Packit |
5c3484 |
represented mpz numbers. */
|
|
Packit |
5c3484 |
ncnt = 0;
|
|
Packit |
5c3484 |
while (UNLIKELY (mp[0] == 0))
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mp++;
|
|
Packit |
5c3484 |
ncnt++;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
nodd = n - ncnt;
|
|
Packit |
5c3484 |
cnt = 0;
|
|
Packit |
5c3484 |
if (mp[0] % 2 == 0)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mp_ptr newmp = TMP_ALLOC_LIMBS (nodd);
|
|
Packit |
5c3484 |
count_trailing_zeros (cnt, mp[0]);
|
|
Packit |
5c3484 |
mpn_rshift (newmp, mp, nodd, cnt);
|
|
Packit |
5c3484 |
nodd -= newmp[nodd - 1] == 0;
|
|
Packit |
5c3484 |
mp = newmp;
|
|
Packit |
5c3484 |
ncnt++;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
if (ncnt != 0)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
/* We will call both mpn_powm and mpn_powlo. */
|
|
Packit |
5c3484 |
/* rp needs n, mpn_powlo needs 4n, the 2 mpn_binvert might need more */
|
|
Packit |
5c3484 |
mp_size_t n_largest_binvert = MAX (ncnt, nodd);
|
|
Packit |
5c3484 |
mp_size_t itch_binvert = mpn_binvert_itch (n_largest_binvert);
|
|
Packit |
5c3484 |
itch = 3 * n + MAX (itch_binvert, 2 * n);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
else
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
/* We will call just mpn_powm. */
|
|
Packit |
5c3484 |
mp_size_t itch_binvert = mpn_binvert_itch (nodd);
|
|
Packit |
5c3484 |
itch = n + MAX (itch_binvert, 2 * n);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
tp = TMP_ALLOC_LIMBS (itch);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
rp = tp; tp += n;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
bp = PTR(b);
|
|
Packit |
5c3484 |
mpn_powm (rp, bp, bn, ep, en, mp, nodd, tp);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
rn = n;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
if (ncnt != 0)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mp_ptr r2, xp, yp, odd_inv_2exp;
|
|
Packit |
5c3484 |
unsigned long t;
|
|
Packit |
5c3484 |
int bcnt;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
if (bn < ncnt)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mp_ptr newbp = TMP_ALLOC_LIMBS (ncnt);
|
|
Packit |
5c3484 |
MPN_COPY (newbp, bp, bn);
|
|
Packit |
5c3484 |
MPN_ZERO (newbp + bn, ncnt - bn);
|
|
Packit |
5c3484 |
bp = newbp;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
r2 = tp;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
if (bp[0] % 2 == 0)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
if (en > 1)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
MPN_ZERO (r2, ncnt);
|
|
Packit |
5c3484 |
goto zero;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
ASSERT (en == 1);
|
|
Packit |
5c3484 |
t = (ncnt - (cnt != 0)) * GMP_NUMB_BITS + cnt;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* Count number of low zero bits in B, up to 3. */
|
|
Packit |
5c3484 |
bcnt = (0x1213 >> ((bp[0] & 7) << 1)) & 0x3;
|
|
Packit |
5c3484 |
/* Note that ep[0] * bcnt might overflow, but that just results
|
|
Packit |
5c3484 |
in a missed optimization. */
|
|
Packit |
5c3484 |
if (ep[0] * bcnt >= t)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
MPN_ZERO (r2, ncnt);
|
|
Packit |
5c3484 |
goto zero;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
mpn_powlo (r2, bp, ep, en, ncnt, tp + ncnt);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
zero:
|
|
Packit |
5c3484 |
if (nodd < ncnt)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mp_ptr newmp = TMP_ALLOC_LIMBS (ncnt);
|
|
Packit |
5c3484 |
MPN_COPY (newmp, mp, nodd);
|
|
Packit |
5c3484 |
MPN_ZERO (newmp + nodd, ncnt - nodd);
|
|
Packit |
5c3484 |
mp = newmp;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
odd_inv_2exp = tp + n;
|
|
Packit |
5c3484 |
mpn_binvert (odd_inv_2exp, mp, ncnt, tp + 2 * n);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
mpn_sub (r2, r2, ncnt, rp, nodd > ncnt ? ncnt : nodd);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
xp = tp + 2 * n;
|
|
Packit |
5c3484 |
mpn_mullo_n (xp, odd_inv_2exp, r2, ncnt);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
if (cnt != 0)
|
|
Packit |
5c3484 |
xp[ncnt - 1] &= (CNST_LIMB(1) << cnt) - 1;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
yp = tp;
|
|
Packit |
5c3484 |
if (ncnt > nodd)
|
|
Packit |
5c3484 |
mpn_mul (yp, xp, ncnt, mp, nodd);
|
|
Packit |
5c3484 |
else
|
|
Packit |
5c3484 |
mpn_mul (yp, mp, nodd, xp, ncnt);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
mpn_add (rp, yp, n, rp, nodd);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
ASSERT (nodd + ncnt >= n);
|
|
Packit |
5c3484 |
ASSERT (nodd + ncnt <= n + 1);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
MPN_NORMALIZE (rp, rn);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
if ((ep[0] & 1) && SIZ(b) < 0 && rn != 0)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mpn_sub (rp, PTR(m), n, rp, rn);
|
|
Packit |
5c3484 |
rn = n;
|
|
Packit |
5c3484 |
MPN_NORMALIZE (rp, rn);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
ret:
|
|
Packit |
5c3484 |
MPZ_REALLOC (r, rn);
|
|
Packit |
5c3484 |
SIZ(r) = rn;
|
|
Packit |
5c3484 |
MPN_COPY (PTR(r), rp, rn);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
TMP_FREE;
|
|
Packit |
5c3484 |
}
|