Line data Source code
1 : #line 2 "../src/kernel/gmp/gcdext.c"
2 : /* Copyright (C) 2000-2003 The PARI group.
3 :
4 : This file is part of the PARI/GP package.
5 :
6 : PARI/GP is free software; you can redistribute it and/or modify it under the
7 : terms of the GNU General Public License as published by the Free Software
8 : Foundation; either version 2 of the License, or (at your option) any later
9 : version. It is distributed in the hope that it will be useful, but WITHOUT
10 : ANY WARRANTY WHATSOEVER.
11 :
12 : Check the License for details. You should have received a copy of it, along
13 : with the package; see the file 'COPYING'. If not, write to the Free Software
14 : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
15 :
16 : /*==================================
17 : * invmod(a,b,res)
18 : *==================================
19 : * If a is invertible, return 1, and set res = a^{ -1 }
20 : * Otherwise, return 0, and set res = gcd(a,b)
21 : */
22 : int
23 21986986 : invmod(GEN a, GEN b, GEN *res)
24 : {
25 21986986 : if (!signe(b)) { *res=absi(a); return 0; }
26 21986986 : if (NLIMBS(b) < INVMOD_GMP_LIMIT)
27 19839039 : return invmod_pari(a,b,res);
28 : { /* General case: use gcdext(a+b, b) since mpn_gcdext require S1>=S2 */
29 2147947 : pari_sp av = avma;
30 : GEN ca, cb, u, d;
31 2147947 : long l, su, sa = signe(a), lb,lna;
32 : mp_size_t lu;
33 : GEN na;
34 2147947 : if (!sa) { set_avma(av); *res = absi(b); return 0; }
35 2147943 : if (signe(b) < 0) b = negi(b);
36 2147943 : if (abscmpii(a, b) < 0)
37 2141194 : na = sa > 0? addii(a, b): subii(a, b);
38 : else
39 6798 : na = a;
40 : /* Copy serves two purposes:
41 : * 1) mpn_gcdext destroys its input and needs an extra limb
42 : * 2) allows us to use icopy instead of gerepile later. */
43 2147990 : lb = lgefint(b); lna = lgefint(na);
44 2147990 : ca = icopy_ef(na,lna+1);
45 2147988 : cb = icopy_ef( b,lb+1);
46 : /* must create u first else final icopy could fail. */
47 2147990 : u = cgeti(lna+1);
48 2147989 : d = cgeti(lna+1);
49 : /* na >= b */
50 2147987 : l = mpn_gcdext(LIMBS(d), LIMBS(u), &lu, LIMBS(ca), NLIMBS(ca), LIMBS(cb), NLIMBS(cb));
51 2147993 : d[1] = evalsigne(1)|evallgefint(l+2);
52 2147993 : if (!is_pm1(d)) {set_avma(av); *res=icopy(d); return 0;}
53 2147846 : su = lu?((sa ^ lu) < 0)? -1: 1: 0;
54 2147846 : u[1] = evalsigne(su) | evallgefint(labs(lu)+2);
55 2147846 : if (su < 0) u = addii(u, b);
56 2147846 : set_avma(av); *res=icopy(u); return 1;
57 : }
58 : }
59 :
60 : /*==================================
61 : * bezout(a,b,pu,pv)
62 : *==================================
63 : * Return g = gcd(a,b) >= 0, and assign GENs u,v through pointers pu,pv
64 : * such that g = u*a + v*b.
65 : * Special cases:
66 : * a == b == 0 ==> pick u=1, v=0
67 : * a != 0 == b ==> keep v=0
68 : * a == 0 != b ==> keep u=0
69 : * |a| == |b| != 0 ==> keep u=0, set v=+-1
70 : * Assignments through pu,pv will be suppressed when the corresponding
71 : * pointer is NULL (but the computations will happen nonetheless).
72 : */
73 :
74 : GEN
75 84991427 : bezout(GEN a, GEN b, GEN *pu, GEN *pv)
76 : {
77 : long s, sa, sb;
78 : ulong g;
79 : ulong xu,xu1,xv,xv1; /* Lehmer stage recurrence matrix */
80 :
81 84991427 : s = abscmpii(a,b);
82 84996205 : if (s < 0) { swap(a,b); pswap(pu,pv); }
83 : /* now |a| >= |b| */
84 :
85 84996205 : sa = signe(a); sb = signe(b);
86 84996205 : if (!sb)
87 : {
88 2998181 : if (pv) *pv = gen_0;
89 2998181 : switch(sa)
90 : {
91 4 : case 0: if (pu) *pu = gen_0; return gen_0;
92 2994420 : case 1: if (pu) *pu = gen_1; return icopy(a);
93 3756 : case -1: if (pu) *pu = gen_m1; return negi(a);
94 : }
95 : }
96 81998025 : if (s == 0) /* |a| == |b| != 0 */
97 : {
98 10542427 : if (pu) *pu = gen_0;
99 10542427 : if (sb > 0)
100 10037805 : { if (pv) *pv = gen_1; return icopy(b); }
101 : else
102 504622 : { if (pv) *pv = gen_m1; return negi(b); }
103 : }
104 : /* now |a| > |b| > 0 */
105 :
106 71455598 : if (lgefint(a) == 3) /* single-word affair */
107 : {
108 68289528 : g = xxgcduu((ulong)a[2], (ulong)b[2], 0, &xu, &xu1, &xv, &xv1, &s);
109 68530855 : sa = s > 0 ? sa : -sa;
110 68530855 : sb = s > 0 ? -sb : sb;
111 68530855 : if (pu)
112 : {
113 35133637 : if (xu == 0) *pu = gen_0; /* can happen when b divides a */
114 12339667 : else if (xu == 1) *pu = sa < 0 ? gen_m1 : gen_1;
115 6905600 : else if (xu == 2) *pu = sa < 0 ? gen_m2 : gen_2;
116 : else
117 : {
118 6137518 : *pu = cgeti(3);
119 6138239 : (*pu)[1] = evalsigne(sa)|evallgefint(3);
120 6138239 : (*pu)[2] = xu;
121 : }
122 : }
123 68531576 : if (pv)
124 : {
125 62941523 : if (xv == 1) *pv = sb < 0 ? gen_m1 : gen_1;
126 26451336 : else if (xv == 2) *pv = sb < 0 ? gen_m2 : gen_2;
127 : else
128 : {
129 23956708 : *pv = cgeti(3);
130 23919611 : (*pv)[1] = evalsigne(sb)|evallgefint(3);
131 23919611 : (*pv)[2] = xv;
132 : }
133 : }
134 68494479 : if (g == 1) return gen_1;
135 23178409 : else if (g == 2) return gen_2;
136 16077457 : else return utoipos(g);
137 : }
138 : else
139 : { /* general case */
140 3166070 : pari_sp av = avma;
141 : /*Copy serves two purposes:
142 : * 1) mpn_gcdext destroys its input and needs an extra limb
143 : * 2) allows us to use icopy instead of gerepile later.
144 : * NOTE: we must put u before d else the final icopy could fail. */
145 3166070 : GEN ca = icopy_ef(a,lgefint(a)+1);
146 3234835 : GEN cb = icopy_ef(b,lgefint(b)+1);
147 3234834 : GEN u = cgeti(lgefint(a)+1), v = NULL;
148 3234825 : GEN d = cgeti(lgefint(a)+1);
149 : long su,l;
150 : mp_size_t lu;
151 3234819 : l = mpn_gcdext(LIMBS(d), LIMBS(u), &lu, LIMBS(ca), NLIMBS(ca), LIMBS(cb), NLIMBS(cb));
152 3234839 : if (lu<=0)
153 : {
154 2724115 : if (lu==0) su=0;
155 396468 : else {su=-1;lu=-lu;}
156 : }
157 : else
158 510724 : su=1;
159 3234839 : if (sa<0) su=-su;
160 3234839 : d[1] = evalsigne(1)|evallgefint(l+2);
161 3234839 : u[1] = evalsigne(su)|evallgefint(lu+2);
162 3234839 : if (pv) v=diviiexact(subii(d,mulii(u,a)),b);
163 3234831 : set_avma(av);
164 3234829 : if (pu) *pu=icopy(u);
165 3234827 : if (pv) *pv=icopy(v);
166 3234827 : return icopy(d);
167 : }
168 : }
|
