0
$\begingroup$

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.

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

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

Answer: Nobody knows.

Oh, sure, there are some examples where a lot can be said, but by and large, bupkes.

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.

$\endgroup$
  • $\begingroup$ guess I was thinking because both forms are on there That something could be said. $\endgroup$ – Roddy MacPhee Mar 27 at 0:59
  • $\begingroup$ we actually know, if we have n coprime to prime p coefficients to start, that at least n coefficients, can be reduced to 1 at iteration p-1. That comes from Fermat. $\endgroup$ – Roddy MacPhee Jul 15 at 23:49
  • $\begingroup$ 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$. $\endgroup$ – Gerry Myerson Jul 15 at 23:58
  • $\begingroup$ 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. $\endgroup$ – Roddy MacPhee Jul 16 at 0:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.