oversolver's blog

Prime checking
By oversolver, history, 7 years ago, In English

Your given a simple task:

For given number 2 ≤ n ≤ 1018 check prime or not it is.

Limits are: 1 second TL, 16Mb ML.

And we have solution:

bool isprime(LL n){
	if(n<2) return false;
	for(LL i=2;i*i*i<=n;++i) if(n%i==0) return false;
	for(int it=0;it<1e5;++it){
		LL i = rand()%(n-1)+1;
		if(__gcd(i,n)!=1) return false;
		if(mpow(i,n-1,n)!=1) return false;
	}
	return true;
}

where rand() returns 64-bit random integer and mpow(a,b,m) is ab modulo m.

Can you challenge this solution?

  • Vote: I like it
  • +42
  • Vote: I do not like it

Comments Comments (26)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How likely is it that it is gonna say that the number is a prime, when in reality it isn't?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Fails for 999999999999999989

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Link

Line if(mpow(i,n-1,n)!=1) return false; won't never be executed.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Line with __gcd is very likely to be executed for Carmichael numbers, since they have small primes in their factorization.

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it +8 Vote: I do not like it

    those numbers have at least 3 primes in factorization?

    if yes then ok, because of this line

    for(LL i=2;i*i*i<=n;++i) if(n%i==0) return false;

    → Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

im fake reyna 15241579244017681=123456791^2

→ Reply
»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it 
bool isprime(LL n){
	if(n<2) return false;
	for(LL i=2;i<1000000;++i) if(n%i==0) return false;
	LL i = rand()%(n-1)+1;
	if(mpow(i,n-1,n)!=1) return false;
	return true;
}

I slightly modified the code and now it performs the power test only once, still I'm quite confident that it's correct.

The only interesting case is N = pq where p, q > 1000000 are large primes. The test fails when in - 1 = 1. However, by Euler's theorem, you know i(p - 1)(q - 1) = 1, and by combining these two equations you get ip + q - 2 = 1. There are at most p + q - 2 such i and the probability that this happens is at most (p + q - 2) / (n - 1) < 0.000002.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    "There are at most p  +  q  -  2 such i"

    I don't get it. Can you explain why?

    UPD. I think that if q = 2p - 1 and p, q are both primes then we have only two conditions on i: and . First one holds for remainders modulo q (exactly for quadratic residues) and second for p - 1 remainders modulo p (all non-zero remainders). So there are solutions modulo pq (because of Chinese remainder theorem).

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Let P be a polynomial of degree k (on any field). Then the number of roots of P is at most k.

      (If r1, r2, ... are roots, (x - r1)(x - r2)... must be a divisor of P(x))

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I still don't get it. is not a field. I expressed my doubts in UPD to my previous comment.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes, you are right, I was stupid :)

          → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

Do you know how to challenge this solution or you wondering whether it possible? It seems to me that this code is correct and 105 iterations is way too much.

Explanation
→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    answer to the question: second, i'm just interesting

    → Reply
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Btw, it's Fermat primality test, with hack to work with Carmichael numbers.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    see my answer to RomaWhite before

    but thanks, i didn't knew such test, I created this function 2 years ago just for fun

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

Just in case someone didn't know about this. Some time ago, collares told me there were small bases of witnesses to perform Miller-Rabin deterministically for values up to 264.

Then I found this. Here you can find such witnesses and perform safely your primality test in O(logn).

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    You can also use the first 12 primes as candidate witnesses (source). Arguably, 12 candidates might be a bit less efficient than 7, but the set is much easier to remember.

    → Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

There is a inbuilt method in JAVA in BigInteger class for prime checking. Is that method slow for prime checking? Should I avoid using that in live competition? { Method is object.isProbablePrime(int certainty))

→ Reply