Factor base


Factor base

In computational number theory, the factor base is a mathematical tool commonly used in, as its name suggests, integer factorization algorithms, more specifically algorithms involving extensive sieving of potential factors.

Usage

The factor base is a relatively small set of prime numbers "P". Say we want to factorize an integer "n". We generate, in some way, a large number of integer pairs ("x", "y") for which x eq y and extstyle x equiv y pmod{n}, and "x", "y" can be completely factorized over the chosen factor base — that is, they are "p"-smooth for the largest prime "p" in "P".

We find a subset "S" of the integer pairs such that extstyle prod_{} x hbox{, } (x hbox{ in } S) and extstyle prod_{} y hbox{, } (y hbox{ in } S) are both perfect squares. Over our factor base this reduces to adding exponents of their prime factors, modulo 2, as we can distinguish squares from non-squares simply by checking the parity of the exponents.

We can represent each "x" and "y" as a vector of a matrix with 0 and 1 entries for the parity of each exponent. This essentially reformulates the problem into a system of linear equations, which can be solved using numerous methods such as Gaussian elimination; in practice advanced methods like the block Lanczos algorithm are used, that take advantage of certain properties of the system.

Once such a subset is found, we have essentially found a congruence of squares modulo "n" and can attempt to factorize "n". This congruence may generate the trivial extstyle n = 1 cdot n; in this case we try to find another suitable subset. If no such subset is found, we can search for more ("x", "y") pairs, or try again using a different factor base.

Algorithms

Factor bases are used in, for example, Dixon's factorization, the quadratic sieve, and the number field sieve. The difference between these algorithms is essentially the methods used to generate ("x", "y") candidates.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Factor de forma — Saltar a navegación, búsqueda Tamaños de factores de forma estándar Nombre Tamaño (mm) WTX 356×425 AT 350×305 Baby AT …   Wikipedia Español

  • Factor de Landé — Saltar a navegación, búsqueda En mecánica cuántica existe un efecto llamado Zeeman que consiste en el desdoblamiento de niveles de energía en un átomo cuando se aplica un campo magnético externo. Cuando el campo es lo bastante débil, podemos… …   Wikipedia Español

  • Factor de impacto — (también conocido como índice de impacto), más común en idioma inglés Impact Factor, es una medida de la importancia de una publicación científica. Cada año es calculado por el Instituto para la Información Científica (ISI o Institute for… …   Wikipedia Español

  • Base de datos de tablas de finales — Saltar a navegación, búsqueda Una interfaz típica para solicitar una base de datos de tablas. Para cada movimiento del Blanco, la base de datos devuelve el número de movimientos necesarios para ganar. Rc6 y Da6+ gana en cinco movimientos, por lo… …   Wikipedia Español

  • Factor-X — Saltar a navegación, búsqueda Para el programa de televisión, véase Factor X (TV). Un wikipedista está trabajando actualmente en extender este artículo. Es posible que, a causa de ello, haya lagunas de contenido o deficiencias de formato. Por… …   Wikipedia Español

  • Base (topología) — Saltar a navegación, búsqueda En matemáticas, una base β de un espacio topológico X con topología T, es una colección de abiertos de T que verifica que todo abierto de la topología T puede expresarse como unión de los elementos de β. Decimos que… …   Wikipedia Español

  • Factor de forma (informática) — Factor de forma (< inglés form factor) es el tamaño físico estándarizado de una placa base para ordenador personal. No obstante, también define algunas especificaciones técnicas básicas de éstas …   Enciclopedia Universal

  • Factor Three — Superteambox imagesize= caption= team name=Factor Three publisher=Marvel Comics debut= The X Men #28 (January 1968) creators=Stan Lee Jack Kirby base=Mt. Charteris; Burton Canyon, Colorado; the Alps in Europe members=Banshee Blob Changeling… …   Wikipedia

  • Base — (Del lat. basis < gr. basis.) ► sustantivo femenino 1 Parte de un objeto, o pieza independiente, que le sirve de apoyo o sobre la que se sostiene: ■ esa copa tiene muy poca base. SINÓNIMO fundamento asiento 2 Elemento más importante, que sirve …   Enciclopedia Universal

  • Factor (programming language) — Infobox programming language name = Factor paradigm = stack based year = 2003 developer = Slava Pestov latest release version = Continuous Builds [http://factorcode.org/binaries.fhtml] typing = strong, dynamic influenced by = Joy, Forth, Lisp,… …   Wikipedia