| dbo:abstract
|
- Wheel factorization is an improvement of the trial division method for integer factorization. The trial division method consists of dividing the number to be factorized successively by the first integers (2, 3, 4, 5, ...) until finding a divisor. For wheel factorization, one starts from a small list of numbers, called the basis — generally the first few prime numbers; then one generates the list, called the wheel, of the integers that are coprime with all numbers of the basis. Then to find the smallest divisor of the number to be factorized, one divides it successively by the numbers in the basis, and in the wheel. With the basis {2, 3}, this method reduces the number of divisions to 1/3 < 34% of the number necessary for trial division. Larger bases reduce this proportion even further; for example, with basis {2, 3, 5} to 8/30 < 27%; and with basis {2, 3, 5, 7} to 48/210 < 23%. (en)
- Колесна факторизація[усталений термін?] — це вдосконалення методу пробного поділу для цілочислової факторизації . Метод пробного ділення складається з ділення числа, яке слід послідовно розділити на перші цілі числа (2, 3, 4, 5,…) до знаходження дільника. Колісна факторизація починається з невеликого списку чисел, що має назву основа перших кількох простих чисел; після чого генерується список, що називається колесом, цілих чисел, які є взаємно простими числами з усіма числами основи. Щоб знайти найменший дільник числа, що підлягає факторизації, слід ділити його(число) послідовно на числа основи та на числа самого колеса. На основі {2, 3} цей метод зменшує кількість операцій ділення до 1/3 від кількості, необхідної для пробного поділу. Більші основи ще більше зменшують цю пропорцію; наприклад, за основою {2, 3, 5} до 8/30; і з основою {2, 3, 5, 7} до 48/210. (uk)
|
| rdfs:comment
|
- Wheel factorization is an improvement of the trial division method for integer factorization. The trial division method consists of dividing the number to be factorized successively by the first integers (2, 3, 4, 5, ...) until finding a divisor. For wheel factorization, one starts from a small list of numbers, called the basis — generally the first few prime numbers; then one generates the list, called the wheel, of the integers that are coprime with all numbers of the basis. Then to find the smallest divisor of the number to be factorized, one divides it successively by the numbers in the basis, and in the wheel. (en)
- Колесна факторизація[усталений термін?] — це вдосконалення методу пробного поділу для цілочислової факторизації . Метод пробного ділення складається з ділення числа, яке слід послідовно розділити на перші цілі числа (2, 3, 4, 5,…) до знаходження дільника. Колісна факторизація починається з невеликого списку чисел, що має назву основа перших кількох простих чисел; після чого генерується список, що називається колесом, цілих чисел, які є взаємно простими числами з усіма числами основи. Щоб знайти найменший дільник числа, що підлягає факторизації, слід ділити його(число) послідовно на числа основи та на числа самого колеса. (uk)
|
