Algorithmic Subfield Representation of the Depth of Descent Tree

A finite field K admits a sparse medium subfield representation if

– it has a subfield of q² elements for a prime power q, i.e. K is isomorphic to F_q^2k with k ≥ 1;

– there exist two polynomials h₀ and h₁ over F_q² of small degree, such that h₁X^q − h₀ has a degree k irreducible factor.

We shall assume that all the fields under consideration admit a sparse medium subfield representation. Furthermore, we also assume that the degrees of the polynomials h₀ and h₁ are uniformly bounded by a constant δ. Any finite field of the form F_q^2k with k ≤ q + 2 admits a sparse medium subfield representation with polynomials h₀ and h₁ of degree at most 2.

In a field in sparse medium subfield representation, elements will always be represented as polynomials of degree less than k with coefficients in F_q². When we talk about the discrete logarithm of such an element, we implicitly assume that a basis for this discrete logarithm has been chosen, and that we work in a subgroup whose order has no small irreducible factor to limit ourselves to this case.

Proposition: Let K = F_q^2k be a finite field that admits a sparse medium subfield representation. Under the heuristics, there exists an algorithm whose complexity is polynomial in q and k and which can be used for the following two tasks.

1. Given an element of K represented by a polynomial P ∈ F_q²[X] with 2 ≤ deg P ≤ k − 1, the algorithm returns an expression of log P (X ) as a linear combination of at most O(kq²) logarithms logP_i(X) with degP_i ≤ ⌈1/2 degP⌉ and of log h₁(X).

2. The algorithm returns the logarithm of h₁(X) and the logarithms of all the elements of K of the form X + a, for a in F_q².

Let P(X) be an element of K for which we want to compute the discrete logarithm. Here P is a polynomial of degree at most k − 1 and with coefficients in F_q². We start by applying the algorithm of the above Proposition to P. We obtain a relation of the form

log P = e₀ log h₁ + e_i log P_i,

where the sum has at most κq²k terms for a constant κ and the P_i’s have degree at most ⌈1/2 degP⌉. Then, we apply recursively the algorithm to the P_i’s, thus creating a descent procedure where at each step, a given element P is expressed as a product of elements, whose degree is at most half the degree of P (rounded up) and the arity of the descent tree is in O(q²k). At the end of the process, the logarithm of P is expressed as a linear combination of the logarithms of h₁ and of the linear polynomials, for which the logarithms are computed with the algorithm in the above Proposition in its second form.

We are left with the complexity analysis of the descent process. Each internal node of the descent tree corresponds to one application of the algorithm of the above Proposition, therefore each internal node has a cost which is bounded by a polynomial in q and k. The total cost of the descent is therefore bounded by the number of nodes in the descent tree times a polynomial in q and k. The depth of the descent tree is in O(log k). The number of nodes of the tree is then less than or equal to its arity raised to the power of its depth, which is (q²k)^{O(log k)}. Since any polynomial in q and k is absorbed in the O() notation in the exponent, we obtain the following result.

Let K = F_q²k be a finite field that admits a sparse medium subfield representation. Assuming the same heuristics as in the above Proposition, any discrete logarithm in K can be computed in a time bounded by

max(q, k)^{O(log k)}

Advertisement

Alt-Right Drama Trauma: Nameless

Is it possible to comment upon the “movement” Sturm und Drang taking place lately, without mentioning any names or (overtly) taking any sides? In this latest “Nameless” Podcast, Andy Nowicki includes the perils of knee-jerk trolling and alpha male “beta-baiting.”

Being Mediatized: How 3 Realms and 8 Dimensions Explain ‘Being’ by Peter Blank.

Experience of Reflection: ‘Self itself is an empty word’
Leary – The neuroatomic winner: “In the province of the mind, what is believed true is true, or becomes true within limits to be learned by experience and experiment.” (Dr. John Lilly)

Media theory had noted the shoring up or even annihilation of the subject due to technologies that were used to reconfigure oneself and to see oneself as what one was: pictures, screens. Depersonalization was an often observed, reflective state of being that stood for the experience of anxiety dueto watching a ‘movie of one’s own life’ or experiencing a malfunction or anomaly in one’s self-awareness.

To look at one’s scaffolded media identity meant in some ways to look at the redactionary product of an extreme introspective process. Questioning what one interpreted oneself to be doing in shaping one’s media identities enhanced endogenous viewpoints and experience, similar to focusing on what made a car move instead of deciding whether it should stay on the paved road or drive across a field. This enabled the individual to see the formation of identity from the ‘engine perspective’.

Experience of the Hyperreal: ‘I am (my own) God’
Leary – The metaprogramming winner: “I make my own coincidences, synchronities, luck, and Destiny.”

Meta-analysis of distinctions – seeing a bird fly by, then seeing oneself seeing a bird fly by, then thinking the self that thought that – becomes routine in hyperreality. Media represent the opposite: a humongous distraction from Heidegger’s goal of the search for ‘Thinking’: capturing at present the most alarming of what occupies the mind. Hyperreal experiences could not be traced back to a person’s ‘real’ identities behind their aliases. The most questionable therefore related to dismantled privacy: a privacy that only existed because all aliases were constituting a false privacy realm. There was nothing personal about the conversations, no facts that led back to any person, no real change achieved, no political influence asserted.

From there it led to the difference between networked relations and other relations, call these other relations ‘single’ relations, or relations that remained solemnly silent. They were relations that could not be disclosed against their will because they were either too vague, absent, depressing, shifty, or dangerous to make the effort worthwhile to outsiders.

The privacy of hyperreal being became the ability to hide itself from being sensed by others through channels of information (sight, touch, hearing), but also to hide more private other selves, stored away in different, more private networks from others in more open social networks.

Choosing ‘true’ privacy, then, was throwing away distinctions one experienced between several identities. As identities were space the meaning of time became the capacity for introspection. The hyperreal being’s overall identity to the inside as lived history attained an extra meaning – indeed: as alter- or hyper-ego. With Nietzsche, the physical body within its materiality occasioned a performance that subjected its own subjectivity. Then and only then could it become its own freedom.

With Foucault one could say that the body was not so much subjected but still there functioning on its own premises. Therefore the sensitory systems lived the body’s life in connection with (not separated from) a language based in a mediated faraway from the body. If language and our sensitory systems were inseparable, beings and God may as well be.

Being Mediatized