В основах существующих методов факторизации (метод решета числового поля, метод квадратичного решета) лежит принцип факторизации при помощи метода Ферма. Ускорение метода Ферма разложения чисел вида N = p*q где p и q простые, на множители можно достичь за счет прореживания пробных значений, путем перехода к модульному уравнению <$E x sup 2 mod B~=~(N mod B~+~y sup 2 mod B) mod B>, где B некоторый модуль (база). Эффективность такого подхода увеличивается с увеличением базы B. Рост базы в свою очередь ведет к росту требуемого объема памяти, для хранения допустимых значений xmodB и росту вычислительной сложности. Рост вычислительной сложности в дополнении с ростом требуемого объёма памяти превышает рост эффективности ускорения. В связи трудностями, возникающими при использовании модулей большого размера (B), предлагается использовать несколько модулей меньшего размера. При этом возникает задача эффективного их выбора. Проведен анализ эффективности, при использовании просеивания по двум базам b1 и b2, и даны сравнительные характеристики со случаем, когда используются просеивание по одной B = b1*b2. Определены условия эффективности просеивания для вариантов по одной и по двум базам.

  Повний текст PDF - 537.252 Kb    Зміст випуску     Цитування публікації

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"