4 #include "base/cl_sysdep.h"
7 #include "cln/numtheory.h"
12 #include "cln/integer.h"
13 #include "integer/cl_I.h"
14 #include "cln/exception.h"
15 #include "base/cl_xmacros.h"
19 int jacobi (const cl_I& a, const cl_I& b)
21 // Check b > 0, b odd.
23 throw runtime_exception();
25 throw runtime_exception();
30 // If a and b are fixnums, choose faster routine.
32 return jacobi(FN_to_V(a),FN_to_V(b));
35 // (a/b) * v is invariant.
37 // b=1 implies (a/b) = 1.
40 // b>1 and a=0 imply (a/b) = 0.
43 // a > b/2, so (a/b) = (-1/b) * ((b-a)/b),
44 // and (-1/b) = -1 if b==3 mod 4.
46 if (FN_to_V(logand(b,3)) == 3)
51 // b>1 and a=2a', so (a/b) = (2/b) * (a'/b),
52 // and (2/b) = -1 if b==3,5 mod 8.
54 switch (FN_to_V(logand(b,7))) {
55 case 3: case 5: v = -v; break;
59 // a and b odd, 0 < a < b/2 < b, so apply quadratic reciprocity
60 // law (a/b) = (-1)^((a-1)/2)((b-1)/2) * (b/a).
61 if (FN_to_V(logand(logand(a,b),3)) == 3)
64 // Now a > 2*b, set a := a mod b.
68 { a = a-b; do { a = a-b; } while (a >= b); }