Sha256: 78fceafeba1274da1a2d3899660926ffe4627573fa01124df254c4d2c55b51a2
Contents?: true
Size: 512 Bytes
Versions: 8
Compression:
Stored size: 512 Bytes
Contents
class Integer
def carmichael?
return false unless odd? and composite? and square_free?
prime_factors.all? do |p|
(self - 1).remainder(p - 1) == 0
end
end
def carmichael
case self
when 1, 2 then 1
when 4 then 2
else
if primaries.size == 1
p, a = primaries.first
return totient if p.odd?
return totient/2 if p == 2 and a >= 3
end
primaries.map{|p| p.reduce(:**)}.map(&:carmichael).reduce(&:lcm)
end
end
end
Version data entries
8 entries across 8 versions & 1 rubygems