/* -*-c-*-
*
- * $Id: mp-modsqrt.c,v 1.4 2001/06/16 12:56:38 mdw Exp $
+ * $Id: mp-modsqrt.c,v 1.5 2004/04/08 01:36:15 mdw Exp $
*
* Compute square roots modulo a prime
*
* (c) 2000 Straylight/Edgeware
*/
-/*----- Licensing notice --------------------------------------------------*
+/*----- Licensing notice --------------------------------------------------*
*
* This file is part of Catacomb.
*
* it under the terms of the GNU Library General Public License as
* published by the Free Software Foundation; either version 2 of the
* License, or (at your option) any later version.
- *
+ *
* Catacomb is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU Library General Public License for more details.
- *
+ *
* You should have received a copy of the GNU Library General Public
* License along with Catacomb; if not, write to the Free
* Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
* MA 02111-1307, USA.
*/
-/*----- Revision history --------------------------------------------------*
- *
- * $Log: mp-modsqrt.c,v $
- * Revision 1.4 2001/06/16 12:56:38 mdw
- * Fixes for interface change to @mpmont_expr@ and @mpmont_mexpr@.
- *
- * Revision 1.3 2001/02/03 12:00:29 mdw
- * Now @mp_drop@ checks its argument is non-NULL before attempting to free
- * it. Note that the macro version @MP_DROP@ doesn't do this.
- *
- * Revision 1.2 2000/10/08 12:02:21 mdw
- * Use @MP_EQ@ instead of @MP_CMP@.
- *
- * Revision 1.1 2000/06/22 19:01:31 mdw
- * Compute square roots in a prime field.
- *
- */
-
/*----- Header files ------------------------------------------------------*/
#include "fibrand.h"
* work if %$p$% is composite: you must factor the modulus, take
* a square root mod each factor, and recombine the results
* using the Chinese Remainder Theorem.
+ *
+ * We guarantee that the square root returned is the smallest
+ * one (i.e., the `positive' square root).
*/
mp *mp_modsqrt(mp *d, mp *a, mp *p)
/* --- Find the inverse of %$a$% --- */
- ainv = MP_NEW;
- mp_gcd(0, &ainv, 0, a, p);
-
+ ainv = mp_modinv(MP_NEW, a, p);
+
/* --- Split %$p - 1$% into a power of two and an odd number --- */
t = mp_sub(MP_NEW, p, MP_ONE);
dd = mpmont_reduce(&mm, dd, dd);
dd = mpmont_mul(&mm, dd, dd, ainv);
- /* --- Now %$d = d_0^{s - i - 1}$% --- */
+ /* --- Now %$d = d_0^{2^{s - i - 1}}$% --- */
for (j = i; j < s - 1; j++) {
dd = mp_sqr(dd, dd);
c = mpmont_reduce(&mm, c, c);
}
- /* --- Done, so tidy up --- */
+ /* --- Done, so tidy up --- *
+ *
+ * Canonify the answer.
+ */
d = mpmont_reduce(&mm, d, r);
+ r = mp_sub(r, p, d);
+ if (MP_CMP(r, <, d)) { mp *tt = r; r = d; d = tt; }
mp_drop(ainv);
mp_drop(r); mp_drop(c);
mp_drop(dd);
ok = 0;
else if (MP_EQ(r, rr))
ok = 1;
- else {
- r = mp_sub(r, p, r);
- if (MP_EQ(r, rr))
- ok = 1;
- }
if (!ok) {
fputs("\n*** fail\n", stderr);
fputs("a = ", stderr); mp_writefile(a, stderr, 10); fputc('\n', stderr);
fputs("p = ", stderr); mp_writefile(p, stderr, 10); fputc('\n', stderr);
if (r) {
- fputs("r = ", stderr);
+ fputs("r = ", stderr);
mp_writefile(r, stderr, 10);
fputc('\n', stderr);
} else
- fputs("r = <undef>\n", stderr);
+ fputs("r = <undef>\n", stderr);
fputs("rr = ", stderr); mp_writefile(rr, stderr, 10); fputc('\n', stderr);
ok = 0;
}