• May 22, 2022, 10:04:34 AM

Author Topic:  functional graph of modular arithmetic  (Read 183 times)

0 Members and 1 Guest are viewing this topic.

Offline kh40tika

  • Fractal Freshman
  • *
  • Posts: 7
functional graph of modular arithmetic
« on: May 10, 2022, 06:11:57 AM »
Let p be a prime number of form 3n+1, let w be a 3rd root of unity of prime field F_p. Let x be an element of F_p, define:

reduce(x) = min(x, x*w, x*w^2)

Now define a pseudo random iterated map within F_p:

f(x) = reduce(x-1)

Note all the above operations are done in F_p. For example, let p = 19. Solutions of w^3 == 1 (mod 19) are 1, 7, 11. Thus w can be either 7 or 11.
Since they are 3rd roots of unity, it's trivial 7^2 == 11 (mod 19) && 11^2 == 7 (mod 19). Selecting either of them gives the same f(x). Assume x = 3, then f(x) = min(x, mod(x*7, 19), mod(x*11, 19)) = min(3,2,14) = 2

It's trivial to see iterated map f(f(f(x)))... would always converge to 1, since each iteration would make x smaller. If we put all elements of F_p into a directed graph, where edges are defined  by the map f(x), we always obtain a tree. Turns out the structure of this tree is somewhat non-random while being not so trivial. Here's some short Mathematica code to give a plot:

Code: [Select]
(*generate random prime of form 3n+1*)
range = 10000;
irule[i_Integer] := With[{ir = reduce[i]}, ir -> reduce[ir - 1]];
graphList = {};
gridShape = {5, 5};
genPrime[lo_Integer, hi_Integer] := Do[With[{ret = RandomPrime[{lo, hi}]}, If[Mod[ret, 3] == 1, Return@ret]], {\[Infinity]}]
Do[
  p = genPrime[range, 2*range];
  pr = PrimitiveRoot[p];
  w = PowerMod[pr, (p - 1)/3, p]; (*3rd root*)
  reduce[x_Integer] := Min[Mod[{x, x*w, x*w*w}, p]];
  cbrtlist = Table[PowerMod[pr, i, p], {i, 0, (p - 1)/3 - 1}];
  graph = irule /@ cbrtlist;
  AppendTo[graphList, graph]
, {Times @@ gridShape}]
(* render & save *)
img = ImageAssemble@ArrayReshape[Image[GraphPlot[#, PlotStyle -> {Opacity[0.3]}], ImageSize -> {256, 256}] & /@ graphList, gridShape]

Running the above code would give the attached file intro.png



If we modify f(x) into f(x) = reduce(x + 1), then the iterated map no longer converges to 1 and the resulting graph would have cycles. Attached file intro2.png shows the case.



Linkback: https://fractalforums.org/index.php?topic=4752.0

Offline kh40tika

  • Fractal Freshman
  • *
  • Posts: 7
Re: functional graph of modular arithmetic
« Reply #1 on: May 10, 2022, 06:57:45 AM »
More plots coming. Using f(x) = reduce(x + 128) gives a more segmented graph (intro3.png), while using f(x) = reduce(2x + 1) gives a graph closer to random functional graph (intro4.png).


Offline Alef

  • Fractal Freak
  • **
  • Posts: 772
  • a catalisator / z=z*sinh(z)-c^2
    • My deviant art page
Re: functional graph of modular arithmetic
« Reply #2 on: May 10, 2022, 07:22:48 AM »
Is this from a number theory, do lines are connecting numbers?
It looks like hand drawings with a pencil on paper.
« Last Edit: May 10, 2022, 08:18:30 AM by Alef »
by Edgar Malinovsky aka Edgars Malinovskis.

Offline kh40tika

  • Fractal Freshman
  • *
  • Posts: 7
Re: functional graph of modular arithmetic
« Reply #3 on: May 10, 2022, 08:41:15 AM »
Is this from a number theory, do lines are connecting numbers?
It looks like hand drawings with a pencil on paper.

The object of interest is called functional graph.

https://math.stackexchange.com/questions/280717/whats-the-meaning-of-functional-graph

The function f(x) over F_p defines the topology of such a graph. To obtain a nice looking plot, one would need a graph embedding algorithm to assign 2D or 3D coordinates to all graph vertices.

Offline kh40tika

  • Fractal Freshman
  • *
  • Posts: 7
Re: functional graph of modular arithmetic
« Reply #4 on: May 10, 2022, 02:19:12 PM »
The iterative map over finite elements would always converge to either a loop or a fixed point. Using attractor time as shader input produces more interesting render. The graph embedding algorithm has also been changed for the new render. Formula is the one giving fixed point attractor: f(x) = reduce(x-1)

Offline Adam Majewski

  • Fractal Frankfurter
  • *
  • Posts: 641

Offline kh40tika

  • Fractal Freshman
  • *
  • Posts: 7
Re: functional graph of modular arithmetic
« Reply #6 on: May 11, 2022, 12:22:17 PM »
What about 3d fractals? Apart from finding a graph embedding in with 3d coordinates, one may also use high degree field extensions. By joining functional graph from multiple reduction directions, fractal surfaces may be obtained.

Consider field extension of degree 2. Let p > 3 be a prime number, let q = p^2. Since p^2 == 1 (mod 3), F_q would always have 3rd roots (now without requirement of being 3n+1 form). Let (x,y) be an element of F_q. if we define two iterative maps:

u(x,y) = reduce(x-1, y)
v(x,y) = reduce(x, y-1)

Merging functional graph of u(.) and v(.) gives new interesting manifold-like structure.

Code: [Select]
Needs["FiniteFields`"];
POWER = 3;(*power degree for reduction during iteration*)
EXTPWR = \
2;(*field extension degree*)
p = RandomPrime[{150, 210}];
q = p^EXTPWR;
Fq = GF[p, EXTPWR];
nVert = (q - 1)/POWER; nEdge = nVert - 1;
pr = Fq[{0, 1}];
w = Power[pr, (q - 1)/POWER];
pwrlist = Table[Power[w, i], {i, 0, POWER - 1}];
pwrlist[[1]] =
 Fq[{1, 0}];(*fix integer 1*)
Clear[reduce, ifn, fieldElemSize];
(*this will allow some unique ording among elements of F_q*)

fieldElemSize[1] := 1;
fieldElemSize[GF[p_, _][{i_Integer, j_Integer}]] := i + j*p;

reduce[x_] := MinimalBy[x*pwrlist, fieldElemSize][[1]];
ifn[i_] := reduce[i - 1];
ifn2[i_] := reduce[i - Fq[{0, 1}]];

xlist = Table[reduce[Power[pr, i]], {i, 0, nEdge}];
ixmap = Association@Table[xlist[[i]] -> i, {i, Length@xlist}];
ixmap[0] = 0;
graph = {};
Do[
  If[i[[1, 1]] != 0, AppendTo[graph, ixmap[i] -> ixmap[ifn[i]]]];
  If[i[[1, 2]] != 0, AppendTo[graph, ixmap[i] -> ixmap[ifn2[i]]]]
  , {i, xlist}];
graphMap = Association@graph;
graph = graph /. Rule -> UndirectedEdge;

Rasterize[
 GraphPlot3D[graph,
  GraphLayout -> {"SpringElectricalEmbedding",
    "MaxIteration" -> 100000, "Tolerance" -> 0.0001},
  Background -> Black], ImageSize -> 1000]

Offline kh40tika

  • Fractal Freshman
  • *
  • Posts: 7
Re: functional graph of modular arithmetic
« Reply #7 on: May 11, 2022, 01:54:07 PM »
More complicated formula and more 3d graph embeddings. Graph embedding operation has gone pretty slow. Might consider GPU accelerated sparse system solver.

Code: [Select]
{U, V} = RandomInteger[{1, 5}, {2}];
reduce[x_] := MinimalBy[x*pwrlist, fieldElemSize][[1]];
ifn[i_] := reduce[i - U];
ifn2[i_] := reduce[i - Fq[{0, V}]];
ifn3[i_] := reduce[i - Fq[{U, V}]];

sparseFactor = RandomInteger[{4, 24}];
xlist = Table[reduce[Power[pr, i]], {i, 0, nEdge}];
ixmap = Association@Table[xlist[[i]] -> i, {i, Length@xlist}];
ixmap[0] = 0;
graph = {};
Do[With[{xy = i[[1]]},
   AppendTo[graph, ixmap[i] -> ixmap[ifn[i]]];
   If[Mod[xy[[1]] + xy[[2]], sparseFactor] == 0,
    AppendTo[graph, ixmap[i] -> ixmap[ifn2[i]]]
    ]
   ]
  , {i, xlist}];

Offline kh40tika

  • Fractal Freshman
  • *
  • Posts: 7
Re: functional graph of modular arithmetic
« Reply #8 on: May 12, 2022, 04:13:28 AM »
What about elliptic curves? Let E be an elliptic curve of isogeny y^2 = x^3 + k where k != 0.  Then we search for a prime p of form 3n+1 such that E[F_p] has a prime order q also of form 3n+1. Such curves has a nice property called complex multiplication. Let w be 3rd root of unity (sqrt(3)I - 1)/2 Let (x,y) be a point on C, we have:

w . (x,y) == (x / w, y)

Now let w_p and w_q be w reduced on F_p and F_q respectively. Let (x,y) be a point on E[F_p], we have:

w_q . (x,y) == (x / w_p, y)

We can now do a 3rd root "reduction" similar to the finite field version. Combined with the EC point negation law -(x, y) == (x, -y), it's possible to do a 6th root "reduction".

reduce_3(x,y) = (min(x, x*w_p, x*w_p^2), y)  mod p
reduce_6(x,y) = (min(x, x*w_p, x*w_p^2), min(y, -y))  mod p

Fact: bitcoin uses a curve with above properties.

Let G be a generator of E[F_p]. Plotting the functional graph with f(x,y) = reduce(x,y) + G gives a graph with many components.

Such pseudo-random iterated function over finite Abelian groups are exploited in Pollard's Rho algorithm for discrete logarithm. It's believed in a "random enough" iteration within a group of order N, a cycle an be found within approx 0.6267 sqrt(N) steps in average. Finding non-trivial functional graph within E[F_p] may give insight on better discrete logarithm algorithms.