CODEWITHSUNDEEP
algorithmprimality-test
Isura Manchanayake
Isura Manchanayake

Reputation: 245

Miller Rabin primality test two types?

I encountered two types of Miller Rabin primality test methods suddenly. One which uses randoms and another does not use randoms.

Is there a hidden random generation inside the second one or what? Thank you.

Upvotes: 1

Views: 401

Answers (1)

samgak
samgak

Reputation: 24427

The second one is a deterministic variant of the Miller-Rabin primality test. Instead of using "witness" numbers generated from random numbers, a list of primes that are known to be sufficient is used instead:

When the number n to be tested is small, trying all a < 2(ln n)2 is not necessary, as much smaller sets of potential witnesses are known to suffice"

if n < 3,825,123,056,546,413,051, it is enough to test a = 2, 3, 5, 7, 11, 13, 17, 19, and 23.

This is the list of primes in alist in the linked source code.

Upvotes: 2

Related Questions