Блог пользователя 126378

Автор 126378, история, 4 года назад, По-английски

Can you give me the easy and understandable implementation of Miller Rabin in C++?

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    but it gives wrong output in some cases. Example: 999999999999999989 its a prime number but the output is its a composite number.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Are you sure? I just tried it, and MillerRabin(999999999999999989LL) returns true, indicating that it is probably prime.

      You must made an error calling the function (maybe you forgot to mark it as a long long number?).

      Also, if you want to go safe, just use the deterministic Miller-Rabin code, from the next section.