

<p>This function just directly iterates a given function at a point.</p>

{{{id=1|
def iteratedir(f,n,a):
    Q=a
    for i in range(n):
        Q=f(Q)
    return Q
///
}}}

<p>This function uses the division algorithm to speed up the iteration: If we want to find the nth iterate, we can use the division algorithm n=km+r for some choice of k that we will make later. Then, we iterate f a total of k times and then iterate f^k with itself m times. Lastly, we evaluate (f^k)^m at f^r(a). This involves fewer operations than just iterating f the full n number of times.</p>

<p> The question is, which value of k is optimal? Clearly there are some time-savings from using the division algorithm, but these savings are lost when we iterate f with itself too many times.</p>

{{{id=2|
def iterate_modk(f, n, a, k):
    F=f
    v=divmod(n,k)
    for i in range(k-1):
        F=f(F)
    Q=iteratedir(f,v[1],a)
    R=iteratedir(F,v[0],Q)
    return R
///
}}}

<p>Here is an example of the function. Below is the set-up (function, finite field, iterate we want).</p>

<p>To find the optimal choice of k, we compute a few examples and time our computations. We still don't know how to choose k, but for the few examples below we have seen that the optimal point occurs when k=4 or k=5. What does this have to do with anything?</p>

{{{id=4|
G.<c>=GF(3^19)
R.<x>=PolynomialRing(G)
f=x^2+2
n=floor(sqrt(len(G)))
for i in range(1,10):
    i
    time iterate_modk(f,n,c,i)
///
1
c^18 + c^16 + 2*c^14 + c^13 + 2*c^12 + 2*c^10 + c^9 + c^8 + 2*c^6 + c^5 + c^2 + 1
Time: CPU 51.19 s, Wall: 53.07 s
2
c^18 + c^16 + 2*c^14 + c^13 + 2*c^12 + 2*c^10 + c^9 + c^8 + 2*c^6 + c^5 + c^2 + 1
Time: CPU 26.12 s, Wall: 26.66 s
3
c^18 + c^16 + 2*c^14 + c^13 + 2*c^12 + 2*c^10 + c^9 + c^8 + 2*c^6 + c^5 + c^2 + 1
Time: CPU 19.39 s, Wall: 20.80 s
4
c^18 + c^16 + 2*c^14 + c^13 + 2*c^12 + 2*c^10 + c^9 + c^8 + 2*c^6 + c^5 + c^2 + 1
Time: CPU 16.61 s, Wall: 17.04 s
5
c^18 + c^16 + 2*c^14 + c^13 + 2*c^12 + 2*c^10 + c^9 + c^8 + 2*c^6 + c^5 + c^2 + 1
Time: CPU 16.41 s, Wall: 16.88 s
6
c^18 + c^16 + 2*c^14 + c^13 + 2*c^12 + 2*c^10 + c^9 + c^8 + 2*c^6 + c^5 + c^2 + 1
Time: CPU 18.49 s, Wall: 19.13 s
7
c^18 + c^16 + 2*c^14 + c^13 + 2*c^12 + 2*c^10 + c^9 + c^8 + 2*c^6 + c^5 + c^2 + 1
Time: CPU 25.34 s, Wall: 26.02 s
8
c^18 + c^16 + 2*c^14 + c^13 + 2*c^12 + 2*c^10 + c^9 + c^8 + 2*c^6 + c^5 + c^2 + 1
Time: CPU 37.68 s, Wall: 39.22 s
9
c^18 + c^16 + 2*c^14 + c^13 + 2*c^12 + 2*c^10 + c^9 + c^8 + 2*c^6 + c^5 + c^2 + 1
Time: CPU 61.25 s, Wall: 62.92 s
}}}

{{{id=5|
G.<c>=GF(5^13)
R.<x>=PolynomialRing(G)
f=x^2+2
n=floor(sqrt(len(G)))
for i in range(1,10):
    i
    time iterate_modk(f,n,c,i)
///
1
4*c^12 + c^10 + 4*c^9 + 3*c^8 + c^7 + 4*c^6 + 4*c^4 + 2*c^3 + 3*c^2 + 3*c + 2
Time: CPU 40.02 s, Wall: 41.83 s
2
4*c^12 + c^10 + 4*c^9 + 3*c^8 + c^7 + 4*c^6 + 4*c^4 + 2*c^3 + 3*c^2 + 3*c + 2
Time: CPU 20.95 s, Wall: 21.74 s
3
4*c^12 + c^10 + 4*c^9 + 3*c^8 + c^7 + 4*c^6 + 4*c^4 + 2*c^3 + 3*c^2 + 3*c + 2
Time: CPU 14.05 s, Wall: 14.20 s
4
4*c^12 + c^10 + 4*c^9 + 3*c^8 + c^7 + 4*c^6 + 4*c^4 + 2*c^3 + 3*c^2 + 3*c + 2
Time: CPU 11.80 s, Wall: 12.06 s
5
4*c^12 + c^10 + 4*c^9 + 3*c^8 + c^7 + 4*c^6 + 4*c^4 + 2*c^3 + 3*c^2 + 3*c + 2
Time: CPU 11.35 s, Wall: 11.55 s
6
4*c^12 + c^10 + 4*c^9 + 3*c^8 + c^7 + 4*c^6 + 4*c^4 + 2*c^3 + 3*c^2 + 3*c + 2
Time: CPU 12.71 s, Wall: 12.91 s
7
4*c^12 + c^10 + 4*c^9 + 3*c^8 + c^7 + 4*c^6 + 4*c^4 + 2*c^3 + 3*c^2 + 3*c + 2
Time: CPU 16.72 s, Wall: 17.32 s
8
4*c^12 + c^10 + 4*c^9 + 3*c^8 + c^7 + 4*c^6 + 4*c^4 + 2*c^3 + 3*c^2 + 3*c + 2
Time: CPU 24.17 s, Wall: 25.30 s
9
4*c^12 + c^10 + 4*c^9 + 3*c^8 + c^7 + 4*c^6 + 4*c^4 + 2*c^3 + 3*c^2 + 3*c + 2
Time: CPU 37.73 s, Wall: 38.39 s
}}}

<p>The following polynomial is not irreducible. Furthermore, we observe that the time dip occurs at k=2... Is there a connection between the reducibility of f and the optimal choice of k?</p>

{{{id=12|
G.<c>=GF(3^19)
R.<x>=PolynomialRing(G)
f=x^4+2
n=floor(sqrt(len(G)))
for i in range(1,10):
    i
    time iterate_modk(f,n,c,i)
///
1
2*c^18 + 2*c^17 + c^13 + c^11 + c^10 + 2*c^9 + c^8 + 2*c^7 + c^6 + 2*c^5 + c^4 + 2*c + 2
Time: CPU 52.77 s, Wall: 54.40 s
2
2*c^18 + 2*c^17 + c^13 + c^11 + c^10 + 2*c^9 + c^8 + 2*c^7 + c^6 + 2*c^5 + c^4 + 2*c + 2
Time: CPU 32.36 s, Wall: 33.96 s
3
2*c^18 + 2*c^17 + c^13 + c^11 + c^10 + 2*c^9 + c^8 + 2*c^7 + c^6 + 2*c^5 + c^4 + 2*c + 2
Time: CPU 37.83 s, Wall: 39.16 s
4
2*c^18 + 2*c^17 + c^13 + c^11 + c^10 + 2*c^9 + c^8 + 2*c^7 + c^6 + 2*c^5 + c^4 + 2*c + 2
Time: CPU 74.94 s, Wall: 77.39 s
5
2*c^18 + 2*c^17 + c^13 + c^11 + c^10 + 2*c^9 + c^8 + 2*c^7 + c^6 + 2*c^5 + c^4 + 2*c + 2
Time: CPU 208.04 s, Wall: 213.04 s
6
^CTraceback (most recent call last):        time iterate_modk(f,n,c,i)
  File "", line 1, in <module>
    
  File "/private/var/folders/of/of1uAoZoGDOU7RzXM1esKJ8kyXA/-Tmp-/tmpB_PLL3/___code___.py", line 7, in <module>
    exec compile(u'for i in range(_sage_const_1 ,_sage_const_10 ):\n    i\n    __time__=misc.cputime(); __wall__=misc.walltime(); iterate_modk(f,n,c,i); print "Time: CPU %.2f s, Wall: %.2f s"%(misc.cputime(__time__), misc.walltime(__wall__))' + '\n', '', 'single')
  File "", line 3, in <module>
    
  File "/private/var/folders/of/of1uAoZoGDOU7RzXM1esKJ8kyXA/-Tmp-/tmpOhPZKg/___code___.py", line 9, in iterate_modk
    R=iteratedir(F,v[_sage_const_0 ],Q)
  File "/private/var/folders/of/of1uAoZoGDOU7RzXM1esKJ8kyXA/-Tmp-/tmpHkjbNd/___code___.py", line 5, in iteratedir
    Q=f(Q)
  File "polynomial_zz_pex.pyx", line 283, in sage.rings.polynomial.polynomial_zz_pex.Polynomial_ZZ_pEX.__call__ (sage/rings/polynomial/polynomial_zz_pex.cpp:12684)
  File "polynomial_zz_pex.pyx", line 55, in sage.rings.polynomial.polynomial_zz_pex.ZZ_pE_c_to_list (sage/rings/polynomial/polynomial_zz_pex.cpp:10741)
  File "integer_ring.pyx", line 429, in sage.rings.integer_ring.IntegerRing_class._coerce_ZZ (sage/rings/integer_ring.c:6448)
^C
__SAGE__

Traceback (most recent call last):
  File "/Applications/sage/local/lib/python/encodings/utf_8.py", line 15, in decode
    def decode(input, errors='strict'):
KeyboardInterrupt
}}}

{{{id=13|

///
}}}