ospaceteam /
outerspace
| @@ 212-229 (lines=18) @@ | ||
| 209 | ||
| 210 | return (read_random_int(nbits) % range) + minvalue |
|
| 211 | ||
| 212 | def jacobi(a, b): |
|
| 213 | """Calculates the value of the Jacobi symbol (a/b) |
|
| 214 | where both a and b are positive integers, and b is odd |
|
| 215 | """ |
|
| 216 | ||
| 217 | if a == 0: return 0 |
|
| 218 | result = 1 |
|
| 219 | while a > 1: |
|
| 220 | if a & 1: |
|
| 221 | if ((a-1)*(b-1) >> 2) & 1: |
|
| 222 | result = -result |
|
| 223 | a, b = b % a, a |
|
| 224 | else: |
|
| 225 | if (((b * b) - 1) >> 3) & 1: |
|
| 226 | result = -result |
|
| 227 | a >>= 1 |
|
| 228 | if a == 0: return 0 |
|
| 229 | return result |
|
| 230 | ||
| 231 | def jacobi_witness(x, n): |
|
| 232 | """Returns False if n is an Euler pseudo-prime with base x, and |
|
| @@ 36-53 (lines=18) @@ | ||
| 33 | return p |
|
| 34 | ||
| 35 | ||
| 36 | def jacobi(a, b): |
|
| 37 | """Calculates the value of the Jacobi symbol (a/b) where both a and b are |
|
| 38 | positive integers, and b is odd |
|
| 39 | """ |
|
| 40 | ||
| 41 | if a == 0: return 0 |
|
| 42 | result = 1 |
|
| 43 | while a > 1: |
|
| 44 | if a & 1: |
|
| 45 | if ((a-1)*(b-1) >> 2) & 1: |
|
| 46 | result = -result |
|
| 47 | a, b = b % a, a |
|
| 48 | else: |
|
| 49 | if (((b * b) - 1) >> 3) & 1: |
|
| 50 | result = -result |
|
| 51 | a >>= 1 |
|
| 52 | if a == 0: return 0 |
|
| 53 | return result |
|
| 54 | ||
| 55 | def jacobi_witness(x, n): |
|
| 56 | """Returns False if n is an Euler pseudo-prime with base x, and |
|
