Простые числа (18 сентября 2013)

1. Факторизация числа за O(N^1/4) ро-эвристикой Полларда
1. Пародокс дней рождений: нужно Θ(√ N ) случайных чисел, чтобы пояилось совпадений
2. x_i = (x_i-1²+3) mod N − случайная последовательность
3. Предпериод и период − Θ(√ N )
4. Пусть N = pq, p ≤ q, p = O(√ N )
5. y_i = x_i mod p − тоже случайная последовательность, период и предпериод длины Θ(√ P ) = O(N^1/4)
6. Алгоритм
1. k = 5N^1/4 + 10
2. x₀ = RANDOM, for i=1..k do x_i = (x_i-1²+3) mod N
3. for i=1..k do check(gcd(N, x_k - x_i))
7. Чтобы найти все делители, при нахождении одного нужно сделать рекурсивный вызов
2. Умножение по модулю 10¹⁸
1. Первый способ за O(logN) операций − выразить через сложение
2. Второй способ за O(1) операций через long double
3. Решето Эратосфена
1. Задача: найти все простые числа от 1 до N
2. Факты: чисел от 1 до N примерно N/lnN, k-е простое примерно равно k*lnk
3. Алгоритм (A) за O(NloglogN) [код]
4. Док-во времени работы: loglogN = Sum_k=1..N/logN(1/klogk)
5. Алгоритм (B) за O(N) [код]
6. Док-во времени работы: для каждого a, min_prime[a] будет присвоено ровно один раз
7. Алгоритм (C) с использованием за O(√ N ) памяти [код]



4. Упражения на дом
1. Сколько работает точно алгоритм C в теме "решето Эратосфена"?