Common values of the arithmetic functions phi and sigma (2009)
Ford, Kevin, Luca, Florian, Pomerance, Carl
We show that the equation phi(a)=\sigma(b) has infinitely many solutions, where phi is Euler's totient function and sigma is the sum-of-divisors function. This proves a 50-year old conjecture of...
Rank statistics for a family of elliptic curves over a function field (2009)
Pomerance, Carl, Shparlinski, Igor E.
We show that the average and typical ranks in a certain parametric family of elliptic curves described by D. Ulmer tend to infinity as the parameter $d \to\infty$. This is perhaps unexpected since by...
Andrew Granville, Carl Pomerance, Andrew Granville, Carl Pomerance
Abstract. Erd}os [8] conjectured that there are x 1;o(1) Carmichael numbers up to x, whereas Shanks [24] was skeptical as to whether one might even nd an x up to which there are more than p x...
Computer Algorithms. Addison-Wesley, 1974. (2008)
Milton Abramowitz, Irene A. Stegun, Leonard M. Adleman, Carl Pomerance, ...
numbers from composite numbers. Annals of Mathematics, 117:173–206, 1983. [4] Alok Aggarwal and Jeffrey Scott Vitter. The input/output complexity of sorting and related problems. Communications of...
ERROR ESTIMATES FOR THE DAVENPORT-HEILBRONN THEOREMS (2008)
Karim Belabas, Manjul Bhargava, Carl Pomerance
Abstract. We improve the known remainder terms for the theorems of Davenport and Heilbronn on the density of discriminants of cubic fields and average 3-torsion in the class group of quadratic...
We discuss the smallest algebraic number field which contains the nth roots of unity and which may be reached from the rational field Q by a sequence of irreducible, radical, Galois extensions. The...
Heuristics for class numbers of prime-power real cyclotomic fields (2008)
Joe Buhler, Carl Pomerance, Leanne Robertson, Joe Buhler, Carl Pomerance, Leanne Robertson
Dedicated to Hugh Williams on the occasion of his sixtieth birthday Abstract. Let h + (ℓ n) denote the class number of the maximal totally real subfield Q(cos(2π/ℓ n)) of the field of ℓ n-th...
Jonathan M. Borwein, Richard E. Crandall, Carl Pomerance, D. H. Bailey
Résumé. En combinant des concepts de théorie additive des nombres avec des résultats sur les développements binaires et les séries partielles, nous établissons de nouvelles bornes pour la...
On the period of the linear congruential and power generators (2008)
We consider two standard pseudorandom number generators from number theory: the linear congruential generator and the power generator. For the former, we are given integers e, b, n (with e, n> 1)...
On the Least Prime in Certain Arithmetic Progressions (2008)
Andrew Granville, Carl Pomerance
We find infinitely many pairs of coprime integers, a and q, such that the least prime j a (mod q) is unusually large. In so doing we also consider the question of approximating rationals by other...
On Pseudosquares and Pseudopowers (2007)
Pomerance, Carl, Shparlinski, Igor E.
Introduced by Kraitchik and Lehmer, an $x$-pseudosquare is a positive integer $n\equiv1\pmod 8$ that is a quadratic residue for each odd prime $p\le x$, yet is not a square. We use bounds of...
On the Distribution of Pseudopowers (2007)
Konyagin, Sergei V., Pomerance, Carl, Shparlinski, Igor E.
An $x$-pseudopower to base $g$ is a positive integer which is not a power of $g$ yet is so modulo $p$ for all primes $p\le x$. We improve an upper bound for the least such number due to E. Bach, R....
Andrew Granville, Carl Pomerance, Paul Erdos
Abstract. Erdos [8] conjectured that there are x
ON THE NUMBER OF DIVISORS OF n! (2007)
Paul Erdős, S. W. Graham, Ar Ivić, Carl Pomerance
Abstract. Several results involving d(n!) are obtained, where d(m) denotes the number of positive divisors of m. These include estimates for d(n!)/d((n − 1)!), d(n!) − d((n − 1)!), as well as...
The Riemann Zeta-Function and the One-Dimensional Weyl-Berry Conjecture for Fractal Drums (2006)
Lapidus, Michel L., Pomerance, Carl
Based on his earlier work on the vibrations of ‘drums with fractal boundary’, the first author has refined M. V. Berry's conjecture that extended from the ‘smooth’ to the ‘fractal’ case...
On the Least Prime in Certain Arithmetic Progressions (2006)
Granville, Andrew, Pomerance, Carl
We find infinitely many pairs of coprime integers, a and q, such that the least prime congruent to a (modulo q) is unusually large. In so doing we also consider the question of approximating...
SIEVING BY LARGE INTEGERS AND COVERING SYSTEMS OF CONGRUENCES (2006)
Michael Filaseta, Sergei Konyagin, Gang Yu, Kevin Ford, Carl Pomerance
An old question of Erdős asks if there exists, for each number N, a finite set S of integers greater than N and residue classes r(n) (mod n) for n ∈ S whose union is Z. We prove that if � n∈S...
Sieving by large integers and covering systems of congruences (2005)
Filaseta, Michael, Ford, Kevin, Konyagin, Sergei, Pomerance, Carl, Yu, Gang
An old question of Erdos asks if there exists, for each number N, a finite set S of integers greater than N and residue classes r(n) mod n for n in S whose union is all the integers. We prove that if...
On products of ratios of consecutive integers (2005)
De La Bretèche, Régis, Pomerance, Carl, Tenenbaum, Gérald
Take the product of the numbers (n/(n+1))^{\epsilon_n} for 1
On products of ratios of consecutive integers (2005)
De La Bretèche, Régis, Pomerance, Carl, Tenenbaum, Gérald
Take the product of the numbers (n/(n+1))^{\epsilon_n} for 1
On products of ratios of consecutive integers (2005)
De La Bretèche, Régis, Pomerance, Carl, Tenenbaum, Gérald
Take the product of the numbers (n/(n+1))^{\epsilon_n} for 1
On products of ratios of consecutive integers (2005)
De La Bretèche, Régis, Pomerance, Carl, Tenenbaum, Gérald
Take the product of the numbers (n/(n+1))^{\epsilon_n} for 1
Smooth numbers and the quadratic sieve (2005)
When faced with a large number n to factor, what do you do first? You might say “Look at the last digit, ” with the idea of cheaply pulling out possible factors of 2 and 5. Sure, and more...
Prime numbers: a computational perspective. Second Edition (2005)
Richard Crandall, Carl Pomerance, Richard Crandall, Carl Pomerance
Cover illustration: The cover shows a magnified view—through a watchmaker’s loupe—of a very small portion of an actual poster giving the 7.2 million decimal digits of the prime 2 24036583-1....
The iterated Carmichael \lambda-function and the number of cycles of the power generator (2004)
Iteration of the modular l-th power function f(x) = x^l (mod n) provides a common pseudorandom number generator (known as the Blum-Blum-Shub generator when l=2). The period of this pseudorandom...
On the binary expansions of algebraic numbers (2004)
Bailey, David H., Borwein, Jonathan M., Crandall, Richard E., Pomerance, Carl
On the binary expansions of algebraic numbers (2003)
Bailey, David H., Borwein, Jonathan M., Crandall, Richard E., Pomerance, Carl
Employing concepts from additive number theory, together with results on binary evaluations and partial series, we establish bounds on the density of 1's in the binary expansions of real algebraic...
On the binary expansions of algebraic numbers (2003)
Borwein, Jonathan M., Bailey, David H., Crandall, Richard, Pomerance, Carl
Employing concepts from additive number theory, together with results on binary evaluations and partial series, we establish bounds on the density of 1's in the binary expansions of real algebraic...
Timed fair exchange of standard signatures (2003)
In this paper we show how to achieve timed fair exchange of digital signatures of standard type. Timed fair exchange (in particular, contract signing) has been considered before, but only for Rabin...
Primality testing with Gaussian periods (2003)
The problem of quickly determining whether a given large integer is prime or composite has been of interest for centuries, if not longer. The past 30 years has seen a great deal of progress, leading...
E. Rodney Canfield, Carl Pomerance
Say that an integer n is exceptional if the maximum Stirling number of the second kind S(n, k) occurs for two (of necessity consecutive) values of k. We prove that the number of exceptional integers...
Convergence Rates for Runlength Constrained Capacities (2001)
Convergence results are given for the number of binary arrays with at least d and at most k zeros between ones, along any coordinate axis, asymptotically for fixed d as k !1.
Residue classes free of values of Euler’s function (1999)
Kevin Ford, Sergei Konyagin, Carl Pomerance
Dedicated to Andrzej Schinzel on his sixtieth birthday By a totient we mean a value taken by Euler’s function φ(n). Dence and Pomerance [DP] have established Theorem A. If a residue class contains...
H. W. Lenstra, J. Pila, Carl Pomerance
2. Articulation of the proofs.............................108 3. Curves of genus 2 and their Jacobians.....................111 4. Estimates for zeta functions............................113
A Search for Wieferich and Wilson Primes (1997)
Richard Crandall, Karl Dilcher, Carl Pomerance
Abstract. An odd prime p is called a Wieferich prime if 2 p−1 ≡ 1 (mod p 2); alternatively, a Wilson prime if (p − 1)! ≡−1 (mod p 2). To date, the only known Wieferich primes are p = 1093...
It is the best of times for the game of factoring large numbers into their prime factors. In 1970 it was barely possible to factor “hard ” 20-digit numbers. In 1980, in the heyday of the...
Paul Erdős, László Babai, Carl Pomerance, Péter Vértesi, Paul Erdős Number, Carl Pomerance
a memorial article appears elsewhere in this issue. This feature article gives a cross section of his monumental oeuvre. Most of Erdős’s work falls roughly into the following categories: •...
Automaticity II: Descriptional Complexity in the Unary Case (1995)
Carl Pomerance, John Michael Robson, Jeffrey Shallit
Let \Sigma and \Delta be finite alphabets, and let f be a map from \Sigma to \Delta. Then the deterministic automaticity of f , A f (n), is defined to be the size of the minimum finitestate machine...
An upper bound in Goldbach's problem (1993)
Jean-Marc Deshouillers, Andrew Granville, Wladyslaw Narkiewicz, Carl Pomerance
: It is clear that the number of distinct representations of a number n as the sum of two primes is at most the number of primes in the interval [n=2; n \Gamma 2]. We show that 210 is the largest...
Reduction of huge, sparse matrices over finite fields via created catastrophes (1992)
We present a heuristic method for the reduction modulo 2 of a large, sparse bit matrix to a smaller, dense bit matrix that can then be solved by conventional means, such as Gaussian elimination. This...
Reduction of huge, sparse matrices over finite fields via created catastrophes (1992)
2. Description of the Method
The Generation of Random Numbers That Are Probably Prime (1988)
Pierre Beauchemin, Gilles Brassard, Claude Crepeau, Claude Goutier, Carl Pomerance
In this paper we make two observations on Rabin's probabilistic primality test. The first is a provocative reason why Rabin's test is so good. It turned out that a single iteration has a...
A polynomial Time Algorithm for (1982)
A.Shamir, W. R. Alford, Andrew Granville, Carl Pomerance
this paper we show that C(x) ? x