Class: MR_Prime

Inherits:
Object
  • Object
show all
Defined in:
lib/better_prime/mr_prime.rb

Overview

Test r&s can reconstitute n properly

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(n, opts = {}) ⇒ MR_Prime

Returns a new instance of MR_Prime.



34
35
36
37
 
# File 'lib/better_prime/mr_prime.rb', line 34

def initialize(n,opts={})
  self.number = n
  set_trials(opts)
end

Instance Attribute Details

#number ⇒ Object

Returns the value of attribute number.



18
19
20
 
# File 'lib/better_prime/mr_prime.rb', line 18

def number
  @number
end

#r ⇒ Object (readonly)

Returns the value of attribute r.



19
20
21
 
# File 'lib/better_prime/mr_prime.rb', line 19

def r
  @r
end

#s ⇒ Object (readonly)

Returns the value of attribute s.



19
20
21
 
# File 'lib/better_prime/mr_prime.rb', line 19

def s
  @s
end

#trials ⇒ Object (readonly)

Returns the value of attribute trials.



19
20
21
 
# File 'lib/better_prime/mr_prime.rb', line 19

def trials
  @trials
end

Class Method Details

.[](n, opts = {}) ⇒ Object

Allow for easier access to instance of class via MR_Prime



22
23
24
 
# File 'lib/better_prime/mr_prime.rb', line 22

def self.[](n,opts={})
  MR_Prime.new(n,opts).prime?
end

.trials_for_precision(prec) ⇒ Object 



26
27
28
29
30
31
32
 
# File 'lib/better_prime/mr_prime.rb', line 26

def self.trials_for_precision(prec)
  k = 1
  while( 1.0 / (4.0 ** k) > prec)
    k += 1
  end
  return k
end

Instance Method Details

#prime? ⇒ Boolean

Returns:

  • (Boolean) 


59
60
61
 
# File 'lib/better_prime/mr_prime.rb', line 59

def prime?
  witnesses.all? { |a| witnessed_by? a }
end

#resolve_r_and_s ⇒ Object

Find R and S such that 2^r * s + 1 == @number (as per MR def’n)



82
83
84
85
86
87
88
 
# File 'lib/better_prime/mr_prime.rb', line 82

def resolve_r_and_s
  @r,@s=0,@number-1
  while(@s.even?)
    @r += 1
    @s /= 2
  end
end

#set_trials(opts) ⇒ Object

Set the number of trials to the max of num required for precision, witnesses opt, or 19 (giving at max 1.0e-10 chance of failure)



66
67
68
69
70
71
72
73
74
75
76
77
78
79
 
# File 'lib/better_prime/mr_prime.rb', line 66

def set_trials(opts)
  trials = [19] # default precision of 0.00000000036% chance of failure
  if opts[:precision]
    if opts[:precision] == 0 # Short circuit of absolute precision is required
      @absolute = true
      @trials = -1
      return
    else
      trials.push(MR_Prime.trials_for_precision(opts[:precision]))
    end
  end
  trials.push(opts[:witnesses]) if opts[:witnesses]
  @trials = trials.max
end

#witnessed_by?(a) ⇒ Boolean

Returns:

  • (Boolean) 


39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
# File 'lib/better_prime/mr_prime.rb', line 39

def witnessed_by?(a)
  result = exponent_mod(a,@s,@number)
  if result == 1
    return true
  else
    0.upto(@r-1) do |j|
      result = exponent_mod(a,(2**j)*@s,@number)
      if result == -1 or result == @number - 1
        return true
      end
    end
  end
  return false
end

#witnesses ⇒ Object

Witnesses require for absoulte certainty for any number < key

OR

the number of trials specified by :witnesses or :precision arguments Source Wikipedia and “The Primes Page”



94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
 
# File 'lib/better_prime/mr_prime.rb', line 94

def witnesses
  witnesses = []
  if @number < 1_373_653
    witnesses = [2,3]
  elsif @number < 9_080_191
    witnesses = [31,73]
  elsif @number < 4_759_123_141
    witnesses = [2,7,61]
  elsif @number < 2_152_302_898_747
    witnesses = [2,3,5,7,11]
  elsif @number < 3_474_749_660_383
    witnesses = [2, 3, 5, 7, 11, 13]
  elsif @number < 341_550_071_728_321
    witnesses = [2, 3, 5, 7, 11, 13, 17]
  elsif @precision
    witnesses = (2...@number)
  else
    witnesses = Array.new(@trials).map { rand(@number-1)+1 }
  end
  return witnesses
end