# Fermat Primality Test

Page 1 of 1

## 0 Replies - 1476 Views - Last Post: 28 November 2009 - 08:53 PM

### #1 erik.price

• D.I.C Lover

Reputation: 486
• Posts: 2,690
• Joined: 18-December 08

# Fermat Primality Test

Posted 28 November 2009 - 08:53 PM

Description: Uses the probabilistic Fermat test to find whether a number is probably a prime
```def fermat(num, iter)
#num is the number to test, iter is the maximum number of iterations (higher is more accurate)
rand = 1+rand(num-1)
for i in 1..iter
if (rand**(num-1))%num == 0
return false
else
rand = 1+rand(num-1)
end
end
return true
end

#Example
puts fermat(16, 100) #=>false
puts fermat(7, 100)  #=>true
puts fermat(221, 100) #=>Counterexample. Called a Fermat Liar. Returns true (if the iter is low enough (usually)) actually is composite
```

Is This A Good Question/Topic? 0

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }