Category Archives: number-theory

Links to Atiyah's preprints on the Riemann hypothesis

Sir Michael Atiyah's preprints are now on the internet: The Riemann Hypothesis The Fine Structure Constant The meat of the claimed proof of the Riemann hypothesis is in Atiyah's construction of the Todd map $T:\C\to \C$. It supposedly comes from the composition of two different isomorphisms $$\C\xrightarrow{t_+} C(A)\xrightarrow{t^{-1}_{-}} \C$$ of the complex field $\C$ with […]

For real? Atiyah's proof of the Riemann hypothesis

Well this is strange indeed: according to this New Scientist article published today, the famous Sir Michael Atiyah is supposed to talk this Monday at the Heidelberg Laureate Forum. The topic: a proof of the Riemann hypothesis. The Riemann hypothesis states that the Riemann Zeta function defined by the analytic continuation of $\zeta(s) = \sum_{n=1}^\infty […]

A little intro to the Jacobi symbol: Part 3

This is the final post on the Jacobi symbol. Recall that the Jacobi symbol $(m/n)$ for relatively prime integers $m$ and $n$ is defined to be the sign of the permutation $x\mapsto mx$ on the ring $\Z/n$. In the introductory post we saw this definition, some examples, and basic properties for calculation purposes. In Part […]

The Lucas primality test

We've been talking about the Miller-Rabin randomized primality test, which is one of the easiest to implement and most effective tests that, given a number, will either prove it to be composite or state that it is most likely prime. As good as it is for practical applications, the Miller-Rabin test leaves something to be […]

Effectiveness of the Miller-Rabin primality test

Last time, I explained the Miller-Rabin probabilistic primality test. Let's recall it: Theorem. Let $p$ be an odd prime and write $p-1 = 2^kq$ where $q$ is an odd number. If $a$ is relatively prime to $p$ then at least one of the following statements is true: $a^q\equiv 1\pmod{p}$, or One of $a^q,a^{2q},a^{4q},\dots,a^{2^{k-1}q}$ is congruent […]

Symmetric+RSA vs. RSA and Davida’s Attack

Alice wants her friends to send her stuff only she can read. RSA public-key encryption allows her to do that: she chooses huge primes $p$ and $q$ and releases $N = pq$ along with an encryption exponent $e$ such that ${\rm gcd}(e,(p-1)(q-1)) = 1$. If Bob wants to send Alice a message $m$, he sends […]