4 #include "base/cl_sysdep.h"
7 #include "cln/numtheory.h"
12 #include "cln/exception.h"
13 #include "base/cl_xmacros.h"
18 inline int jacobi_aux (uintV a, uintV b)
22 // (a/b) * v is invariant.
24 // b=1 implies (a/b) = 1.
27 // b>1 and a=0 imply (a/b) = 0.
30 // a > b/2, so (a/b) = (-1/b) * ((b-a)/b),
31 // and (-1/b) = -1 if b==3 mod 4.
35 case 3: v = -v; break;
36 default: throw runtime_exception();
41 // b>1 and a=2a', so (a/b) = (2/b) * (a'/b),
42 // and (2/b) = -1 if b==3,5 mod 8.
45 case 1: case 7: break;
46 case 3: case 5: v = -v; break;
47 default: throw runtime_exception();
51 // a and b odd, 0 < a < b/2 < b, so apply quadratic reciprocity
52 // law (a/b) = (-1)^((a-1)/2)((b-1)/2) * (b/a).
56 // Now a > 2*b, set a := a mod b.
60 { a = a-b; do { a = a-b; } while (a >= b); }
64 int jacobi (sintV a, sintV b)
66 // Check b > 0, b odd.
68 throw runtime_exception();
70 throw runtime_exception();
73 a = (uintV)a % (uintV)b;
75 a = b-1-((uintV)(~a) % (uintV)b);
76 return jacobi_aux(a,b);