← Back to branch summary

~ubuntu-branches/debian/lenny/dropbear/lenny

« back to all changes in this revision

Viewing changes to libtommath/bn_mp_sqrt.c

  • Committer: Bazaar Package Importer
  • Author(s): Matt Johnston
  • Date: 2004-06-16 12:44:54 UTC
  • Revision ID: james.westby@ubuntu.com-20040616124454-1udcijfiroqczfpe
Tags: upstream-0.42
Import upstream version 0.42

Show diffs side-by-side

added added

removed removed

Lines of Context:
libtommath/bn_mp_sqrt.c
 
1
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 
2
 *
 
3
 * LibTomMath is a library that provides multiple-precision
 
4
 * integer arithmetic as well as number theoretic functionality.
 
5
 *
 
6
 * The library was designed directly after the MPI library by
 
7
 * Michael Fromberger but has been written from scratch with
 
8
 * additional optimizations in place.
 
9
 *
 
10
 * The library is free for all purposes without any express
 
11
 * guarantee it works.
 
12
 *
 
13
 * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org
 
14
 */
 
15
#include <tommath.h>
 
16
 
 
17
/* this function is less generic than mp_n_root, simpler and faster */
 
18
int mp_sqrt(mp_int *arg, mp_int *ret) 
 
19
{
 
20
  int res;
 
21
  mp_int t1,t2;
 
22
 
 
23
  /* must be positive */
 
24
  if (arg->sign == MP_NEG) {
 
25
    return MP_VAL;
 
26
  }
 
27
 
 
28
  /* easy out */
 
29
  if (mp_iszero(arg) == MP_YES) {
 
30
    mp_zero(ret);
 
31
    return MP_OKAY;
 
32
  }
 
33
 
 
34
  if ((res = mp_init_copy(&t1, arg)) != MP_OKAY) {
 
35
    return res;
 
36
  }
 
37
 
 
38
  if ((res = mp_init(&t2)) != MP_OKAY) {
 
39
    goto E2;
 
40
  }
 
41
 
 
42
  /* First approx. (not very bad for large arg) */
 
43
  mp_rshd (&t1,t1.used/2);
 
44
 
 
45
  /* t1 > 0  */ 
 
46
  if ((res = mp_div(arg,&t1,&t2,NULL)) != MP_OKAY) {
 
47
    goto E1;
 
48
  }
 
49
  if ((res = mp_add(&t1,&t2,&t1)) != MP_OKAY) {
 
50
    goto E1;
 
51
  }
 
52
  if ((res = mp_div_2(&t1,&t1)) != MP_OKAY) {
 
53
    goto E1;
 
54
  }
 
55
  /* And now t1 > sqrt(arg) */
 
56
  do { 
 
57
    if ((res = mp_div(arg,&t1,&t2,NULL)) != MP_OKAY) {
 
58
      goto E1;
 
59
    }
 
60
    if ((res = mp_add(&t1,&t2,&t1)) != MP_OKAY) {
 
61
      goto E1;
 
62
    }
 
63
    if ((res = mp_div_2(&t1,&t1)) != MP_OKAY) {
 
64
      goto E1;
 
65
    }
 
66
    /* t1 >= sqrt(arg) >= t2 at this point */
 
67
  } while (mp_cmp_mag(&t1,&t2) == MP_GT);
 
68
 
 
69
  mp_exch(&t1,ret);
 
70
 
 
71
E1: mp_clear(&t2);
 
72
E2: mp_clear(&t1);
 
73
  return res;
 
74
}
 
75