Little ruby script to check if a given number is a Solinas prime, that is, a prime number of the form 2^a +/- 2^b +/- 1, where 0 < b < a. It is not efficient (4 nested loops) but works.

solinas.rb

#Check if a prime number is a solinas prime
#ModPow and Miller Rabin test extracted from http://en.literateprograms.org/Miller-Rabin_primality_test_(Ruby)

MAX_EXPONENT = 160

#Modular arithmetic power
def modPow(x, r, m)
    y = r
    z = x
    v = 1
    while y > 0
        u = y % 2
        t = y / 2
        if u == 1
            v = (v * z) % m
        end
        z = z * z % m
        y = t
    end
    return v
end

def miller_rabin_pass(a, n)
    d = n - 1
    s = 0
    while d % 2 == 0 do
        d >>= 1
        s += 1
    end
    a_to_power = modPow(a, d, n)
    if a_to_power == 1
        return true
    end
    for i in 0...s do
        if a_to_power == n - 1
            return true
        end
        a_to_power = (a_to_power * a_to_power) % n
    end
    return (a_to_power == n - 1)
end

#Miller rabin primality test
def miller_rabin(n)
    k = 20
    return true if n == 1
    for i in 0...k do
        a = 0
        while a == 0
             a = rand(n)
        end
        if (!miller_rabin_pass(a, n))
            return false
        end
    end
    return true
 end

#Overload integer class to check if a number is prime or solinas prime
class Integer

  #Check if number is prime using the Miller Rabin test
	def prime?
		miller_rabin(self)
	end

	#Check if a number p is a Solinas prime, i.e., p = 2^a +/- 2^b +/-1, where 0 < b < a
	def solinas?
		return false if !prime?
		#Generate all possible numbers until coincidence or return false
		(1..MAX_EXPONENT).to_a.each do |a|
			(1..a).to_a.each do |b|
				[-1,1].each do |sign1|
					[-1,1].each do |sign2|
						p = 2**a + sign1*2**b + sign2
						if p == self
							#Print number 'solinas decomposition'
							puts "2^#{a} #{sign1 == 1 ? '+' : '-'}2^#{b} #{sign2 == 1 ? "+1" : "-1"}"
							return true
						end
					end
				end
			end
		end
		return false
	end
end