what is best deterministic primality checking algorithm??

algorithms
primality

#1

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).


#2

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


#3

@azimuthal , @kcahdog :

http://en.wikipedia.org/wiki/Miller–Rabin_primality_test

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; <br>
if n < 9,080,191, it is enough to test a = 31 and 73; <br>
if n < 4,759,123,141, it is enough to test a = 2, 7, and 61; <br>
if n < 1,122,004,669,633, it is enough to test a = 2, 13, 23, and 1662803; <br>
if n < 2,152,302,898,747, it is enough to test a = 2, 3, 5, 7, and 11; <br>
if n < 3,474,749,660,383, it is enough to test a = 2, 3, 5, 7, 11, and 13; <br>
if n < 341,550,071,728,321, it is enough to test a = 2, 3, 5, 7, 11, 13, and 17.<br>

#4

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


#5

hjghjgjgjgj


#6

ds rtedgsd fgdfg dgdsfgdf


#7

hgj tjtydjhgjgjhghjhgjgf


#8

dfg dg hrthfhdfhjgj


#9

@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 .


#10

it uses Miller-Rabin


#11

@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.