Concept

# Factor base

Résumé
In computational number theory, a factor base is a small set of prime numbers commonly used as a mathematical tool in algorithms involving extensive sieving for potential factors of a given integer. Usage in factoring algorithms A factor base is a relatively small set of distinct prime numbers P, sometimes together with -1. Say we want to factorize an integer n. We generate, in some way, a large number of integer pairs (x, y) for which x \neq \pm y, x^2 \equiv y^2 \pmod{n}, and x^2 \pmod{n} \text{ and }y^2 \pmod{n} can be completely factorized over the chosen factor base—that is, all their prime factors are in P. In practice, several integers x are found such that x^2 \pmod{n} has all of its prime factors in the pre-chosen factor base. We represent each x^2 \pmod{n} expression as a vector of a matrix with integer entries being the exponents of factors in the factor base. Linear combinations of the rows corresp
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés

Chargement

Cours associés

Chargement

Séances de cours associées

Chargement