| 193 | } |
| 194 | |
| 195 | bool IsLucasProbablePrime(const Integer &n) |
| 196 | { |
| 197 | assert(n>1); |
| 198 | |
| 199 | if (n.IsEven()) |
| 200 | return n==2; |
| 201 | |
| 202 | Integer b=1, d; |
| 203 | unsigned int i=0; |
| 204 | int j; |
| 205 | |
| 206 | do |
| 207 | { |
| 208 | if (++i==64 && n.IsSquare()) // avoid infinite loop if n is a square |
| 209 | return false; |
| 210 | ++b; ++b; |
| 211 | d = (b.Squared()-4)%n; |
| 212 | } |
| 213 | while ((j=Jacobi(d,n)) == 1); |
| 214 | |
| 215 | if (j==0) |
| 216 | return false; |
| 217 | else |
| 218 | return Lucas(n+1, b, n)==2; |
| 219 | } |
| 220 | |
| 221 | bool IsStrongLucasProbablePrime(const Integer &n) |
| 222 | { |