monotone

monotone Mtn Source Tree

Root/botan/jacobi.cpp

1/*************************************************
2* Jacobi Function Source File *
3* (C) 1999-2007 The Botan Project *
4*************************************************/
5
6#include <botan/numthry.h>
7
8namespace Botan {
9
10/*************************************************
11* Calculate the Jacobi symbol *
12*************************************************/
13s32bit jacobi(const BigInt& a, const BigInt& n)
14 {
15 if(a.is_negative())
16 throw Invalid_Argument("jacobi: first argument must be non-negative");
17 if(n.is_even() || n < 2)
18 throw Invalid_Argument("jacobi: second argument must be odd and > 1");
19
20 BigInt x = a, y = n;
21 s32bit J = 1;
22
23 while(y > 1)
24 {
25 x %= y;
26 if(x > y / 2)
27 {
28 x = y - x;
29 if(y % 4 == 3)
30 J = -J;
31 }
32 if(x.is_zero())
33 return 0;
34
35 u32bit shifts = low_zero_bits(x);
36 x >>= shifts;
37 if(shifts % 2)
38 {
39 word y_mod_8 = y % 8;
40 if(y_mod_8 == 3 || y_mod_8 == 5)
41 J = -J;
42 }
43
44 if(x % 4 == 3 && y % 4 == 3)
45 J = -J;
46 std::swap(x, y);
47 }
48 return J;
49 }
50
51}

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status