what is best deterministic primality checking algorithm??

i hv tried checking primality of a number bt testing till sqrt of number bt its too time consuming for big numbers… Fermats test involves expotential terms and is tedious to implement for a large number(say for 10^10).

I have heard about AKS algortithm invented at IIT Kanpur in 2002 which is deterministic and pretty fast as well. works in (log(n))^x where n is the number and x is some constant between 7.5 and 12 depending on the implementation. here is the wikipedia link

Miller Rabin Test is good for numbers till 10^18 , i can say with experience .

Particularly note this line in wiki link :

``````if n < 1,373,653, it is enough to test a = 2 and 3;

if n < 9,080,191, it is enough to test a = 31 and 73;

if n < 4,759,123,141, it is enough to test a = 2, 7, and 61;

if n < 1,122,004,669,633, it is enough to test a = 2, 13, 23, and 1662803;

if n < 2,152,302,898,747, it is enough to test a = 2, 3, 5, 7, and 11;

if n < 3,474,749,660,383, it is enough to test a = 2, 3, 5, 7, 11, and 13;

if n < 341,550,071,728,321, it is enough to test a = 2, 3, 5, 7, 11, 13, and 17.
``````
10 Likes

If you use java, the BigInteger class has an in built `isProbablePrime` method, which is quite fast and accurate.

@xylon97 : That’s correct , if you use the BigInteger’s isProbablePrime method with a certainity factor about 100 , then it returns correct answers for all integers in range of “long” and is quite fast also .

it uses Miller-Rabin

2 Likes

@betlista @vineetpaliwal can you tell me what is the probablity that Rabin-Miller gives the correct answer. I know it is very high and will suffice for all practical purposes but it is still non-deterministic.

1 Like

ds rtedgsd fgdfg dgdsfgdf

hgj tjtydjhgjgjhghjhgjgf

hjghjgjgjgj

dfg dg hrthfhdfhjgj