Algorithmic Number Theory - A Classical Introduction to Cryptography: Applications for Communications Security - page 182

n − 1
2

2 3

= 280 = × 35; thus

b n − 1 362 2 3

× 35

mod n = mod 561

2

362 2 2 2 35

=

mod 561

331 2 2 35

= mod 561

= 166 2 35

mod 561

67 35 = mod 561

× 67 2 17

= 67 mod 561

1 17

= 67 × mod 561

= 67 .

Here we do not even have to compute the Jacobi symbol since 67 is neither 1 nor − 1.

We could have computed it without any factorization as follows.

b
n

362
561

=

2

× 181

561

(factor 2 isolation) =

2
561

181
561

(multiplicativity) = ×

181
561

(561 ≡ 1 (mod 8)) =

561
181

(quadratic reciprocity) =

18
181

(modular reduction) =

2

×

9
181

=

(factor 2 isolation)

2
181

9
181

(multiplicativity) = ×

9
181

(181 ≡− 3 (mod 8)) =−

181
9

(quadratic reciprocity) =−

1
9

(modular reduction) =−

=− 1