Я работаю над программой для вычисления больших полупростых чисел.Я использую простую технику Quadratic Sieve.Моя программа работает хорошо, но намного медленнее, потому что во время процесса просеивания (когда я искал числа B-Smooth) я использовал процесс деления (метод деления класса Java "BigInteger").Я слышал, что использование логарифма вместо деления может сделать это намного быстрее.Теперь я знаю, как работает логарифм, но я не понимаю, как я могу подогнать оператор логарифмирования вместо деления, потому что в процессе просеивания мне нужно разделить число, чтобы найти все основные факторы.
Вот пример:
N = 15347, число для факторинга.rootN = Ceil (sqrt (N)) = 124, коэффициент базы {2, 17, 23, 29}
Q (x) = (124 + x) ^ 2 - N
Сейчасдля некоторого x нам нужно найти Q (x), которые полностью разложены по факторной базе:
Q (0) = (124 + 0) ^ 2 - N = 29 = 2 ^ 0 + 17 ^0 + 23 ^ 0 + 29 ^ 1: B-гладкое число
Q (1) = (124 + 1) ^ 2 - N = 278 = НЕ полностью учтено по факторной базе.
Q (2) = (124 + 2) ^ 2 - N = 529 = 2 ^ 0 + 17 ^ 0 + 23 ^ 2 + 29 ^ 0: B-гладкое число
Q (3) = (124 + 3) ^ 2 - N = 782 = 2 ^ 1 + 17 ^ 1 + 23 ^ 1 + 29 ^ 0: B-гладкое число
и т. Д.
Итак, чтобыЧтобы определить число B-Smooth, мы должны попытаться разделить Q (x) со всеми простыми числами факторной базы и с их максимально возможным показателем степени.Я также использовал алгоритм Тонелли – Шенкса, чтобы ускорить поиск чисел B-Smooth.Тем не менее, мне нужен мод и процесс деления, чтобы определить, является ли Q (x) B-гладким или нет.
Теперь я не понимаю, как я могу использовать логарифм, чтобы избежать деления, которое может помочь найти B-гладкоеномера быстро.
Спасибо.