Просіювання пробних значень в методі множинного квадратичного k-решета на основі сигнальних остач

Анотація

Запропоновано спосіб проріджування пробних значень Х для методу множинного квадратичного k-решета (MQkS), що є модифікацією методу квадратичного решета (QS), в якій здійснюється попереднє просіювання Х на основі порівнянь сигнальних остач Y*(X) з остачами Y(X) = X2 – kN, де сигнальні остачі – це добуток перших степенів множників Y(X). Встановлено, що час обчислення достатньої кількості В-гладких залежить від значення параметра h в умові Y*(X) > h ×Y(X) де кращі значення часу отримуються при h ³ 0,7, які майже вдвічі менші за час, що відповідає h = 0. При цьому з ростом N доцільно збільшувати значення h. Показано, що подальше зниження обчислювальної складності можна досягнути за рахунок пошуку тільки тих В-гладких, для яких показники степенів дільників В-гладкого можуть перевищувати одиницю лише при відносно малих значеннях елементів факторної бази, максимальна величина яких визначається на основі значення параметра kff. Встановлено, що в порівнянні з даними розрахунків для значення параметра kff = 1 (обмеження відсутні) час розрахунку зменшувався на величину від 1,128 (для чисел N порядку 1018) до 1,541 (для чисел N порядку 1032) разів при його монотонному рості з ростом N.