**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 Graph Search.

Concept# Sieve of Atkin

Summary

In mathematics, the sieve of Atkin is a modern algorithm for finding all prime numbers up to a specified integer. Compared with the ancient sieve of Eratosthenes, which marks off multiples of primes, the sieve of Atkin does some preliminary work and then marks off multiples of squares of primes, thus achieving a better theoretical asymptotic complexity. It was created in 2003 by A. O. L. Atkin and Daniel J. Bernstein.
In the algorithm:
All remainders are modulo-sixty remainders (divide the number by 60 and return the remainder).
All numbers, including x and y, are positive integers.
Flipping an entry in the sieve list means to change the marking (prime or nonprime) to the opposite marking.
This results in numbers with an odd number of solutions to the corresponding equation being potentially prime (prime if they are also square free), and numbers with an even number of solutions being composite.
The algorithm:
Create a results list, filled with 2, 3, and 5.
Create a sieve list with an entry for each positive integer; all entries of this list should initially be marked non prime (composite).
For each entry number n in the sieve list, with modulo-sixty remainder r :
If r is 1, 13, 17, 29, 37, 41, 49, or 53, flip the entry for each possible solution to 4x2 + y2 = n. The number of flipping operations as a ratio to the sieving range for this step approaches 4/15 × 8/60 (the "8" in the fraction comes from the eight modulos handled by this quadratic and the 60 because Atkin calculated this based on an even number of modulo 60 wheels), which results in a fraction of about 0.1117010721276....
If r is 7, 19, 31, or 43, flip the entry for each possible solution to 3x2 + y2 = n. The number of flipping operations as a ratio to the sieving range for this step approaches π × 4/60 (the "4" in the fraction comes from the four modulos handled by this quadratic and the 60 because Atkin calculated this based on an even number of modulo 60 wheels), which results in a fraction of about 0.072551974569....

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 courses (2)

Related lectures (14)

Related publications (6)

Related concepts (1)

MATH-521: Advanced analytic number theory

We will present the work of James Maynard (MF 2022) on the existence of bounded gaps between primes

MATH-489: Number theory II.c - Cryptography

The goal of the course is to introduce basic notions from public key cryptography (PKC) as well as basic number-theoretic methods and algorithms for cryptanalysis of protocols and schemes based on PKC

Sieve of Eratosthenes

In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them that is equal to that prime. This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.

Integer Factorization: Quadratic Sieve

Covers the Quadratic Sieve method for integer factorization, emphasizing the importance of choosing the right parameters for efficient factorization.

Computing with Infinite Sequences

Introduces lazy lists for computing infinite sequences like prime numbers.

Granulation of Ceramic Suspension by Atomization

Explores the granulation of ceramic suspension through atomization and related processes such as slip casting and density measurements.

Luiz Felippe De Alencastro, Florian Faure

A growing number of studies focusing on microplastics (plastic particles smaller than 5 mm) show this issue affects all environmental matrices and compartments, and suspicions grow as to their toxicity. In this context, the Commission Internationale pour l ...

2017We propose an efficient variant for the initialisation step of quadratic sieving, the sieving step of the quadratic sieve and its variants, which is also used in sieving-based algorithms for computing class groups of quadratic fields. As an application we ...

Aquatic oligochaetes are important bioindicators of sediment quality in watercourses and lakes, but their morphological identiﬁcation to the species level is challenging and sometimes impossible. The use of DNA barcoding and metabarcoding could greatly fac ...

2019