Title:

Primality proving with Gauss and Jacobi sums, Journal of Telecommunications and Information Technology, 2004, nr 4

Creator:

Chmielowiec, Andrzej

Subject and Keywords:

cyclotomic ring ; Gauss sum ; prime numbers ; primality proving ; APR ; Jacobi sum

Description:

This article presents a primality test known as APR (Adleman, Pomerance and Rumely) which was invented in 1980. It was later simplified and improved by Cohen and Lenstra. It can be used to prove primality of numbers with thousands of bits in a reasonable amount of time. The running time of this algorithm for number N is O((lnN)Cln ln lnN) for some constant C. This is almost polynomial time since for all practical purposes the function lnlnlnN acts like a constant.

Publisher:

Instytut Łączności - Państwowy Instytut Badawczy, Warszawa

Date:

2004, nr 4

Resource Type:

artykuł

Format:

application/pdf

DOI:

10.26636/jtit.2004.4.262

ISSN:

1509-4553

eISSN:

1899-8852

Source:

Journal of Telecommunications and Information Technology

Language:

ang

Rights Management:

Biblioteka Naukowa Instytutu Łączności