Lines Matching refs:rn
42 /* Input is {ap,rn}; output is {rp,rn}, computation is
43 mod B^rn - 1, and values are semi-normalised; zero is represented
44 as either 0 or B^n - 1. Needs a scratch of 2rn limbs at tp.
47 mpn_bc_sqrmod_bnm1 (mp_ptr rp, mp_srcptr ap, mp_size_t rn, mp_ptr tp)
51 ASSERT (0 < rn);
53 mpn_sqr (tp, ap, rn);
54 cy = mpn_add_n (rp, tp, tp + rn, rn);
55 /* If cy == 1, then the value of rp is at most B^rn - 2, so there can
57 MPN_INCR_U (rp, rn, cy);
61 /* Input is {ap,rn+1}; output is {rp,rn+1}, in
62 semi-normalised representation, computation is mod B^rn + 1. Needs
63 a scratch area of 2rn + 2 limbs at tp; tp == rp is allowed.
66 mpn_bc_sqrmod_bnp1 (mp_ptr rp, mp_srcptr ap, mp_size_t rn, mp_ptr tp)
70 ASSERT (0 < rn);
72 mpn_sqr (tp, ap, rn + 1);
73 ASSERT (tp[2*rn+1] == 0);
74 ASSERT (tp[2*rn] < GMP_NUMB_MAX);
75 cy = tp[2*rn] + mpn_sub_n (rp, tp, tp+rn, rn);
76 rp[rn] = 0;
77 MPN_INCR_U (rp, rn+1, cy);
81 /* Computes {rp,MIN(rn,2an)} <- {ap,an}^2 Mod(B^rn-1)
84 * already is. Otherwise the class [0] Mod(B^rn-1) is represented by
85 * B^rn-1.
87 * compute the full square with an <= 2*rn, because this condition
88 * implies (B^an-1)^2 < (B^rn-1) .
90 * Requires rn/4 < an <= rn
91 * Scratch need: rn/2 + (need for recursive call OR rn + 3). This gives
93 * S(n) <= rn/2 + MAX (rn + 4, S(n/2)) <= 3/2 rn + 4
96 mpn_sqrmod_bnm1 (mp_ptr rp, mp_size_t rn, mp_srcptr ap, mp_size_t an, mp_ptr tp)
99 ASSERT (an <= rn);
101 if ((rn & 1) != 0 || BELOW_THRESHOLD (rn, SQRMOD_BNM1_THRESHOLD))
103 if (UNLIKELY (an < rn))
105 if (UNLIKELY (2*an <= rn))
113 cy = mpn_add (rp, tp, rn, tp + rn, 2*an - rn);
114 MPN_INCR_U (rp, rn, cy);
118 mpn_bc_sqrmod_bnm1 (rp, ap, rn, tp);
126 n = rn >> 1;
263 if (UNLIKELY (2*an < rn))
266 zero mod B^{rn} - 1 is if the input is zero, and
268 reconstruction is zero, not B^{rn} - 1. */
275 xp + 2*an - n, rn - 2*an, cy);
276 ASSERT (mpn_zero_p (xp + 2*an - n+1, rn - 1 - 2*an));
Indexes created Fri Apr 03 00:24:04 UTC 2026