# Modular arithmetic rules, of iteration of a polynomial function are?

What are the modular arithmetic properties of iterating a polynomial function ?

Iteration if you aren't familiar, is repeated composition of a function with itself. It follows the rules:$$\begin{eqnarray}f^{n}(x)\circ f^{m}(x) =f^{n+m}(x)\\{(f^{m})}^{n}(x)=f^{mn}(x)\end{eqnarray}$$ Admittedly, this is a rephrasing of a previously deleted question I posted. The reason I'm interested is, it's used a lot in primality testing. The Lucas-Lehmer test, can be reduced to iterations of $$2x^2+1$$ Mod other values of $$2x^2+1$$. In this form, it can be restated as:$$f^{p-2}(7)\equiv 0\bmod f^{1}(2^{\frac{p-1}{2}})\iff f^{1}(2^{\frac{p-1}{2}})\in\mathbb{P}$$

I'd like some help simplifying some of this to an easier test. EDIT: https://en.m.wikipedia.org/wiki/Iterated_function does have a few relevant things in it's example table.

EDIT2: we have that we can use polynomial remainder theorem , Fermat's little theorem, Chinese remainder theorem, and that $$2x^2-1$$ has no x term. This last 1 shows that both $$f^1(2^{\frac{p-1}{2}})$$ and $$f^1(f^1(2^{\frac{p-1}{2}})-2^{\frac{p-1}{2}})$$ and the relevant arithmetic progressions, are congruent mod the first. This fact is already known, posted at devalco.de by Bernhard Helmes, a mersenneforum user. $$2^{\frac{p-1}{2}}=7\cdot2^{\frac{p-7}{2}}+2^{\frac{p-7}{2}}-1$$

EDIT3 : and $$f^1(2^{\frac{p-1}{2}})=2^p-1,\text{p odd}$$ the real difficulty is to learn more in depth about iteration, ( purple math doesn't go that far) or dealing with a general form polynomial for the iterates. I know the use a real valued expression in proof of sufficiency, of the original form. I see where some of the iteration forms come from. But, just can't easily deal with them in modular arithmetic. If I could, I might be able to use them along with other facts I know about mersenne prime exponents, and whittle things down to solutions.

EDIT4: using the fact we are in the case of $$a=2$$ and $$b=0$$ of $$ax^2+bx+\frac{b^2-2b-8}{4a}$$ which has nth iterate of:$$\frac{2\alpha^{2^n}+2\alpha^{-2^n}-b}{2a}$$ where $$\alpha\equiv 2^{p-2}(2ax+b\pm\sqrt{(2ax+b)^2-16})\pmod{2^p-1}$$

using a=2,b=0,x=7,n=p-2 we get the first value congruent to:

$$2^{p-1}(2^{p-2}(28\pm\sqrt{28^2-16}))^{2^{p-2}}+2^{p-1}(2^{p-2}(28\pm\sqrt{28^2-16}))^{-2^{p-2}}\pmod {2^p-1}$$

which is then congruent to:

$$2^{p-1}(2^{p-2}(28\pm\sqrt{768}))^{2^{p-2}}+2^{p-1}(2^{p-2}(28\pm\sqrt{768}))^{-2^{p-2}}\pmod {2^p-1}$$

which is :

$$2^{p-1}(2^{p\cdot2^{p-2}+2^{p-1}}(28\pm 16\cdot\sqrt{3})^{2^{p-2}})+2^{p-1}(2^{-p\cdot2^{p-2}+2^{p-1}}(28\pm 16\cdot\sqrt{3})^{(-1)\cdot 2^{p-2}})\pmod {2^p-1}$$

I'll do (or try) the binomial expansion sums later. okay yes I'll go back and fix my error.

question now highlighted.

• What is the question? I'd like some help is not a question. – Marc van Leeuwen Mar 15 at 15:30
• highlighted in yellow now. – Roddy MacPhee Mar 15 at 15:39
• what needs clarification now ? – Roddy MacPhee Mar 17 at 20:57
• What are modular arithmetic properties of any function? – Marc van Leeuwen Mar 17 at 21:04
• for polynomials, we can apply polynomial remainder theorem, Fermat, Euler, CRT, etc. – Roddy MacPhee Mar 17 at 21:07

Question: What are the modular arithmetic properties of iterating a polynomial function?

Are you familiar with the Pollard rho method of factorization? You start with a number $$n$$ you are trying to factor, and a seed $$a$$ and a polynomial $$f$$ and you evaluate $$a,f(a),f(f(a)),f(f(f(a))),\dots$$ all modulo $$n$$. You keep checking (in a clever way) to see whether the difference of two of these numbers has a (non-trivial) common factor with $$n$$. If it does, you win – you have found a factor of $$n$$.
If we knew something about "the modular arithmetic properties of iterating a polynomial function," then we'd know what $$a$$ to take and what $$f$$ to take to guarantee quick success, but we don't. Sometimes you fail to get a non-trivial factor, and then you just have to try another polynomial – and that one may fail, too.
• Not sure I understand. $f(x)=x+1$ has $n=2$ coefficients prime to $p=3$. The 2nd iteration is $x+2$, which has only one coefficient that reduces to $1\bmod3$. – Gerry Myerson Jul 15 at 23:58
• well the constant term can be though of as not a coefficient in simple terms. but I take your point. my point is at least one of the terms created from every non constant term, will have the original coefficient raised to the $p-1$ st power. – Roddy MacPhee Jul 16 at 0:36