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

Тест на простоту Миллера-Рабина
Автор lth, 13 лет назад, По-русски

Всегда писал Миллера-Рабина для чисел в пределах [1, 2 ^ 31 - 1]. И вчера на одном OJ попалась задача,где нужно писать вышеупомянутый тест на простоту для чисел [1, 2 ^ 63 - 1].Все отлично, но вот возводить в степень за log(n) не получается.При возведении промежуточные результаты выходят за пределы long long.Не подскажите ли, знающие люди, как ето можно сделать ?

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

»
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
есть алгоритм "безопасного умножения по модулю". По сути тоже что и возведение в степень по модулю модулю, но тут вместо умножения - сложение, а вместо возведения в квадрат - умножение на 2.
→ Ответить
»
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
→ Ответить
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
что - то типа (u64 = unsigned long long)
u64 mulmod(u64 a, u64 b, u64 mod)
{
if(b&1)
return (mulmod(a, b-1, mod) + a)%mod;
else
return mulmod((a+a)%mod, b>>1, mod);
}
→ Ответить
»
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Есть два трюка первый это "бинарное умножение", это так-же как возведение в степень, только все умножения заменяются на сложения.
То есть основная идея a*b = a*2^0*b0 + ... + a*2^n*bn где bi - биты в записи числа b.

А вторая идея это посчитать такие вещи k = (long long)(((long double)a/m)*b) и res = a*b - k*m (m это модуль), бывает что res слегка ошибается и нужно прибавить или отнять m от него, чтобы всё стало корректно

→ Ответить
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Во, а кинь ссылку на задачу, если можно. Проверить кое-что хочется.
→ Ответить
»
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Use java, Luke. BigInteger.isProbablePrime(). а если серьезно, то можно сделать это в длинной арифметике быстрее, чем предложенные методы бинарного умножения. быстрее в несколько раз, но надо для этого книги Кнута поизучать, там есть где-то про деление длинного на длинное.
→ Ответить
  • »
    »
    13 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

    кроме того, там ограничения на N до 2^63 - 1, такчто без длинной арифметики или её подобия не обойтись. есть тупой алгоритм бинарного деления, сложность та же что при использовании бинарного умножения (но оно тут не применимо в чистом виде, из-за ограничений)

    int Mod(int a, int b)
{
    int k = 0;
    while (a > b)
    {
        b <<= 1;
        k++;
    }
    while (k >= 0)
    {
        if (a >= b)
            a -= b;
        b >>= 1;
        k--;
    }
    return a;
}

    UPD: вместо int - любой твой тип (длинное число)
    ну и длинку надо делать по основанию 2^16 или 2^32
    → Ответить
    • »
      »
      »
      13 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      Использование длинки можно обойти (код под спойлером)
      → Ответить
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        прочитай еще раз мое сообщение "кроме того, там ограничения на N до 2^63 - 1, такчто без длинной арифметики или её подобия не обойтись." что вычислит  твоя программа если mod = 2^63 -100, x = 2^63-1000, y = 2^63 -1000 ?
        → Ответить
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          опа, я гоню. 2^63 ведь, а не 2^64, да можно как ты сказал без длинки.
          → Ответить
»
9 лет назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

Бинарное умножение по модулю. binmult(a,b,mod) {

if (b == 1) x == a; else { x = } return x; }

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

Бинарное умножение по модулю. Разделяй и властвуй) long long binmultmod(long long a, long long b, long long mod) { long long x; if (a == 0 || b == 0) return 0; if (b==1){ x=a; } else{ x=binmultmod(a, b/2, mod); x=(x+x)%mod; if (b%2==1) x=(x+a)%mod; } return x; }

→ Ответить