All the data you need.

Tag: Number Theory

How probable is a probable prime?
A probable prime is a number that passes a test that all primes pass and that most composite numbers fail. Specifically, a Fermat probable prime is a number that passes Fermat’s primality test. Fermat’s test is the most commonly used, so that’s nearly always what anyone means by probable prime …
Relatively prime determinants
Suppose you fill two n×n matrices with random integers. What is the probability that the determinants of the two matrices are relatively prime? By “random integers” we mean that the integers are chosen from a finite interval, and we take the limit as the size of the interval grows to …
Prime plus power of 2
A new article [1] looks at the problem of determining the proportion of odd numbers that can be written as a power of 2 and a prime. A. de Polignac conjectured in 1849 that all odd numbers have this form. An immediate counterexample is 3, and so apparently the conjecture …
Powers that don’t change the last digit
If you raise any number to the fifth power, the last digit doesn’t change. Here’s a little Python code to verify this claim. >>> [n**5 for n in range(10)] [0, 1, 32, 243, 1024, 3125, 7776, 16807, 32768, 59049] In case you’re not familiar with Python, or familiar with Python …
Various kinds of pseudoprimes
Every condition that all primes satisfy has a corresponding primality test and corresponding class of pseudoprimes. The most famous example is Fermat’s little theorem. That theorem says that for all primes p, a certain congruence holds. The corresponding notion of pseudoprime is a composite number that also satisfies Fermat’s congruence. …
Finding large pseudoprimes
Fermat’s little theorem says that if p is a prime number, then for any integer b, bp-1 = 1 (mod p). This gives a necessary but not sufficient test for a number to be prime. A number that satisfies the equation above but is not prime is called a pseudoprime …
Estimating the proportion of smooth numbers
A number is said to be “smooth” if it only has small factors. To make this precise, a number is said to be y-smooth if it only has factors less than or equal to y. So, for example, 1000 is 5-smooth. The de Bruijn function φ(x, y) counts the number …
New RSA factoring challenge solved
How hard is it to factor large numbers? And how secure are encryption methods based on the difficulty of factoring large numbers? The RSA factoring challenges were set up to address these questions. Last year RSA-230 was factored, and this week RSA-240 was factored. This is a 240 digit (795 …
Near zeros of zeta
Alex Kontorovich had an interesting tweet about the Riemann hypothesis a few days ago. Why is the Riemann Hypothesis hard? Just one reason (of very many): it’s not an analytic question. Here are the values of zeta on the 1/2-line (where at least 40% of the zeros are, all should …
Any number can start a factorial
Any positive number can be found at the beginning of a factorial. That is, for every positive positive integer n, there is an integer m such that the leading digits of m! are the digits of n. There’s a tradition in math to use the current year when you need …
A simple unsolved problem
Are there infinitely many positive integers n such that tan(n) > n? David P. Bellamy and Felix Lazebnik [1] asked in 1998 whether there were infinitely man solutions to |tan(n)| > n and tan(n) > n/4. In both cases the answer is yes. But at least as recently as 2014 …
Primes that don’t look like primes
Primes usually look odd. They’re literally odd [1], but they typically don’t look like they have a pattern, because a pattern would often imply a way to factor the number. However, 12345678910987654321 is prime! I posted this on Twitter, and someone with the handle lagomoof replied that the analogous numbers …
Predicted distribution of Mersenne primes
Mersenne primes are prime numbers of the form 2p – 1. It turns out that if 2p – 1 is a prime, so is p; the requirement that p is prime is a theorem, not part of the definition. So far 51 Mersenne primes have discovered [1]. Maybe that’s all …
Beating the odds on the Diffie-Hellman decision problem
There are a couple variations on the Diffie-Hellman problem in cryptography: the computation problem (CDH) and the decision problem (DDH). This post will explain both and give an example of where the former is hard and the latter easy. The Diffie-Hellman problems The Diffie-Hellman problems are formulated for an Abelian …
Fame, difficulty, and usefulness
Pierre Fermat is best known for two theorems, dubbed his “last” theorem and his “little” theorem. His last theorem is famous, difficult to prove, and useless. His little theorem is relatively arcane, easy to prove, and extremely useful. There’s little relation between technical difficulty and usefulness. Fermat’s last theorem Fermat’s …
Twisted elliptic curves
This morning I was sitting at a little bakery thinking about what to do before I check out of my hotel. I saw that the name of the bakery was Twist Bakery & Cafe, and that made me think of writing about twisted elliptic curves when I got back to …
Distribution of quadratic residues
Let p be an odd prime number. If the equation x² = n mod p has a solution then n is a square mod p, or in classical terminology, n is a quadratic residue mod p. Half of the numbers between 0 and p are quadratic residues and half are …
Software to factor integers
In my previous post, I showed how changing one bit of a semiprime (i.e. the product of two primes) creates an integer that can be factored much faster. I started writing that post using Python with SymPy, but moved to Mathematica because factoring took too long. SymPy vs Mathematica When …