Class: Numeric

Inherits:
Object
  • Object
show all
Defined in:
ext/prime.c

Instance Method Summary collapse

Instance Method Details

#prime? ⇒ Boolean

Miller-Rabin algorithm to determine primality of a number. Uses values for a that guarantee correct results up to 314T. Above that, uses [email protected]’s Mr.Prime.

Returns:

  • (Boolean) 


33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
 
# File 'ext/prime.c', line 33

VALUE
integer_is_prime(VALUE self)
{
  if (!FIXNUM_P(self)) {
    return mrprime(self);
  }

  ullong n = NUM2ULL(self);
  
  int *primes;
  int nprimes;
  int k, i, j;
  ullong m, b;
  bool prime;
  
  static int primes_1[] = {2, 3};
  static int primes_2[] = {31, 73};
  static int primes_3[] = {2, 7, 61};
  static int primes_4[] = {2, 3, 5, 7, 11};
  static int primes_5[] = {2, 3, 5, 7, 11, 13};
  static int primes_6[] = {2, 3, 5, 7, 11, 13, 17};
  
  if (n < 2) {
    return Qfalse;
  } else if (n < 4) {
    return Qtrue;
  } else if (n < 1373653) {
    primes = primes_1;
    nprimes = 2;
  } else if (n < 9080191) {
    primes = primes_2;
    nprimes = 2;
  } else if (n < 4759123141ULL) { 
    primes = primes_3;
    nprimes = 3;
  } else if (n < 2152302989747ULL) {
    primes = primes_4;
    nprimes = 5;
  } else if (n < 3474749660383ULL) {
    primes = primes_5;
    nprimes = 6;
  } else if (n < 341550071728321ULL) {
    primes = primes_6;
    nprimes = 7;
  } else {
    // Quick, do something sensible!
    return mrprime(self);
  }

  k = 0;
  m = n - 1;
  while (m & 1) {
    m >>= 1;
    k += 1;
  }

  for (i = 0; i < nprimes; i++) {
    b = expmod(primes[i], m, n);

    if (b != 1) {
      prime = false;
      for (j = 0; j < k; j++) {
        if (b == n - 1) {
          prime = true;
          break;
        }
        b = expmod(b, 2, n);
      }
      if (!prime) {
        return Qfalse;
      }
    }
  }
  
  return Qtrue;
}