Intereting Posts

Identify $\sum\limits_{n=0}^\infty \left(x_n-L\right)$ where $x_{n+1}=\sqrt{1+x_n}$ and $L^3=L+1$
Separated schemes and unicity of extension
Extension of Sections of Restricted Vector Bundles
finding the combinatorial sum
difficulty in solving first order PDE: $ (y+xz)z_x + (x+yz)z_y = z^2 – 1$
Good Number Theory books to start with?
What is the use of moments in statistics
The system of genus characters determined by a binary quadratic form
Questions about manifolds
Question About Notation In Field Theory.
Your favourite application of the Baire Category Theorem
Proof of Extended Euclidean Algorithm?
e as sum of an infinite series
$Y$ is normally distributed or constant if $X$ and $X+Y$ are normally distributed and $X$, $Y$ are independent
equality of two operators…

new user here. Where does a layman go to get a basic understanding of AKS primality testing. I am not talking about the optimal choice of “r” (which I am told is the hardcore number theoretic part of the algorithm). I mean basic things, like what does “mod(n, x^r-1)” mean (how can something be mod two things?) And what does binomial expansion have to do with anything. I can’t find anything in Wikipedia that is appropriate for my level. Thanks.

- Find the Remainder when $24242424$… upto $300$ digits is divided by $999$?
- Sum of digits of number from 1 to n
- Is $\lim_{k \to \infty}\left}\right]=1$?
- Show $\frac{(2n)!}{n!\cdot 2^n}$ is an integer for $n$ greater than or equal to $0$
- Vieta Jumping: Related to IMO problem 6, 1988: If $ab + 1$ divides $a^2 + b^2$ then $ab + 1$ cannot be a perfect square.
- Are my calculations of a recursive prime-generating function based on logarithms correct?
- Nature of the series $\sum\limits_{n}(g_n/p_n)^\alpha$ with $(p_n)$ primes and $(g_n)$ prime gaps
- How many different ways can a number N be expressed as a sum of K different positive integers?
- Prove that the sum of digits of $(999…9)^{3}$ (cube of integer with $n$ digits $9$) is $18n$
- How many ways can $133$ be written as sum of only $1s$ and $2s$

Informally $\rm\:(mod\ n,\ x^r – 1)\:$ denotes polynomial arithmetic mod assumptions $\rm\:n = 0,\ x^r -1 = 0\:.\:$ Using these assumptions we can reduce an integer coefficient polynomial to normal form form as follows. Reduce all coefficients mod $\rm\:n\ $ and then substitute $\rm\:x^r = 1\:,\ $ so $\rm\ x^{r+1} =x,\:\ x^{r+2} = x^2,\ \ldots,\:$ Notice that this is equivalent to replacing all of the exponents of $\rm\:x\:$ by their remainders $\rm\:(mod\ r)\:.\ $

This yields a polynomial of degree $\rm < r\:$ with coefficients between $0$ and $\rm\:n-1\:.\:$ Two polynomials are congruent $\rm\:(mod\ n,\ x^r-1)\:$ iff they have the same reduced normal forms (or, equivalently, if their difference reduces to $0\:$). This reduction is the same as using the the Division Algorithm to reduce a polynomial by mapping it to its remainder after division by $\rm\: x^r-1\:,\:$ doing coefficient arithmetic $\rm\:mod\ n\:,\:$ i.e. considering the polynomials as being over the ring $\rm\:\mathbb Z/n =\: $ integers $\rm\:(mod\ n)\:.\:$

I will address the two question that are directly stated. If you ask more, I can change this answer.

To mod by two things, in this case a number and a polynomial, is not as bad as it might seem. Modding by the number n is just as before – treat every coefficient separately. So $16x^2 + 10x + 7 \equiv x^2 + 2 \mod 5$. The polynomial modulus is a little stranger. But in the case where it’s $x^k – 1$, this just means that you reduce all exponents greater than $k$ by $k$, effectively dividing polynomials that are “too large” by a smaller polynomial.

Many more sources exist. Here is a great primer. This is a short FAQ aimed at the AKS. And here is a list of other sources or learning about the AKS algorithm.

I’m not sure it’s suitable for the layman, nor indeed whether there is an account of AKS that is suitable for the layman, but the book Primality Testing in Polynomial Time by Dietzfelbinger is very nice.

- A familiar quasigroup – about independent axioms
- Construct a function which is continuous in $$ but not differentiable at $2, 3, 4$
- Roulette betting system probability
- Shortest path between two points on a surface
- Logarithm proof problem: $a^{\log_b c} = c^{\log_b a}$
- Integral with logarithm – residue
- $A^{T}A$ positive definite then A is invertible?
- $\arcsin$ written as $\sin^{-1}(x)$
- The solution of $\min_x \max_{1\leq r \leq N} \left|\frac{\sin rMx}{\sin rx}\right|$
- What is meant by a continuous-time white noise process?
- Show that the countable product of metric spaces is metrizable
- If A is an infinite set and B is at most countable set, prove that A and $A \cup B$ have the same cardinality
- Distance Between A Point And A Line
- Can you prove the following formula for hypergeometric functions?
- Is Cross Product Defined on Vector Space?