Factoring with two large primes

Arjen Lenstra
1991
Article

Résumé

We describe a modification to the well-known large prime variant of the multiple polynomial quadratic sieve factoring algorithm. In practice this leads to a speed-up factor of 2 to 2.5. We discuss several implementation-related aspects, and we include some examples. Our new variation is also of practical importance for the number field sieve factoring algorithm.

Source officielle

https://infoscience.epfl.ch/record/149704?ln=fr

À 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.

A new elementary proof of the Prime Number Theorem

Florian Karl Richter

Let

\Omega(n)

denote the number of prime factors of

n

. We show that for any bounded

f\colon\mathbb{N}\to\mathbb{C}

one has [ \frac{1}{N}\sum_{n=1}^N, f(\Omega(n)+1)=\frac{1}{N}\sum_{n=1}^N, f(\Omega(n))+\mathrm{o}_{N\to\infty}(1). ] This yields a ...

2021

Factoring with two large primes

Non-planarity of Markoff graphs mod p

The double exponential runtime is tight for 2-stage stochastic ILPs

A new elementary proof of the Prime Number Theorem

The double exponential runtime is tight for 2-stage stochastic ILPs

A new elementary proof of the Prime Number Theorem

Non-planarity of Markoff graphs mod p