**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Factor base

Summary

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

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related people

Related publications

Related lectures

No results

No results

No results

Related units

No results

Related concepts

No results

Related courses

No results