what is best deterministic primality checking algorithm??

general
,
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 Likes
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

2 Likes
3

@azimuthal , @kcahdog :

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

2 Likes
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.

1 Like