Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

weily's blog

A Question about Miller-Rabin
By weily, history, 3 hours ago, In English

Upd: the first 8 primes are not enough, because $$$341550071728321 = 10670053 \times 32010157$$$ (for hacker).

===

Hi everyone,

Generally speaking, using the sequence (2, 325, 9375, 28178, 450775, 9780504, 1795265022) as bases in the Miller-Rabin primality test is sufficient to check prime numbers below $$$2^{64}$$$.

However, this sequence is quite hard to remember. Some sources suggest using the first 12 prime numbers as bases, while others claim that the first 8 primes are enough. Unfortunately, these claims lack clear references.

I'm curious about the minimum number of $$$n$$$ if we use the first $$$n$$$ prime numbers as bases for testing primality below $$$2^{64}$$$.

Does anyone know a definitive answer or a reliable source for this?

Thank you!

English is not my native language; please excuse typing errors.

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

»
2 hours ago, # |
  Vote: I like it +3 Vote: I do not like it

I'm not sure, but according to link(in Chinese),

if n < 2,047, choose a = 2 is enough;
if n < 1,373,653, choose a = 2, 3;
...
if n < 3,825,123,056,546,413,051, choose a = 2, 3, 5, 7, 11, 13, 17, 19 and 23.
the numbers in long long range can be checked by the first 10 prime numbers.

Again, I did not take part in this research. To make sure, you can use 12 primes or more as well. Of course 8 is not enough because I was hacked once because I was using the first 9 primes...

→ Reply
»
106 minutes ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

https://miller-rabin.appspot.com/#

this website seems unstable, https://web.archive.org/web/20240709103303/https://miller-rabin.appspot.com/ here is

→ Reply
»
56 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by weily (previous revision, new revision, compare).

→ Reply
»
52 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe the first 8 primes is for $$$2^{32}$$$? I'm not sure.

→ Reply