Decentralisation is one of the most important structural principles of blockchains and it should be present in all aspects of these systems. There is a growing scientific effort to develop protocols that enable the exchange of digital assets between two heterogeneous blockchains without a third-party arbitrator. We investigate the scenario where two parties wish to exchange digital tokens and run a swap protocol without the intervention of a third party. This is a complex and cooperative process for which – in a trust-less environment – atomicity and fairness must be ensured. While smart contracts provide a convenient way to achieve this, we want to ensure that the two parties leave no traceable data on the respective chains. The challenge here is that the two digital assets can reside on different chains with different signature schemes. Tackling these issues, we present a protocol description for the exchange of two arbitrary cryptocurrencies. A generic standard for atomic swap implementations in terms of the required cryptographic primitives is given. Additionally, we derive a protocol for the necessary interactions between two arbitrary chains using these primitives. To demonstrate applicability, we illustrate how this protocol can be instantiated with Schnorr and BLS signatures.

Fast reroute (FRR) is among the fastest survivable routing approaches in packet-switched networks, because the routers are equipped with a resilient routing table in advance such that the packets can be rerouted instantly upon failures solely relying on local information, i.e., without notification messages. However, designing the routing algorithm for FRR is challenging as the number of possible sets of failed network links can be extremely high, while the algorithm should keep track of which routers are aware of the failure. Therefore, FRR methods often rely on spanning arborescences, which provide multiple disjoint failover paths up to the global connectivity of the network. In this paper, we propose a generic algorithmic framework that theoretically increases the number of failover paths to the local connectivity between each node and the root by extending an efficient connectivity preserving operation from graph theory – called edge splitting-off – to decompose the network topology node-by-node, and use Integer Linear Programs (ILPs) on these partial subproblems to build routing arborescences in the reverse direction for the original topology. Although our practical implementation cannot reach the local connectivity in all instances, we demonstrate through simulations that it still outperforms the state-of-the-art FRR mechanisms and provides better resilience with shorter paths in the arborescences.

Fast reroute (FRR) mechanisms that can instantly handle network failures in the data plane are gaining attention in packet-switched networks. In FRR no notification messages are required as the nodes adjacent to the failure are prepared with a routing table such that the packets are re-routed only based on local information. However, designing the routing algorithm for FRR is challenging because the number of possible sets of failed network links and nodes can be extremely high, while the algorithm should keep track of which nodes are aware of the failure. In this paper, we propose a generic algorithmic framework that combines the benefits of Integer Linear Programming (ILP) and an effective approach from graph theory related to constructive graph characterization of k-connected graphs, i.e., edge splitting-off. We illustrate these benefits through arborescence design for FRR and show that (i) due to the ILP we have great flexibility in defining the routing problem, while (ii) the problem can still be solved very fast. We demonstrate through simulations that our framework outperforms state-of-the-art FRR mechanisms andvprovides better resilience with shorter paths in the arborescences.

Several recent studies shed light on the vulnerability of networks against regional failures, which are failures of multiple nodes and links in a physical region due to a natural disaster. The paper defines a novel design framework, called Geometric Network Augmentation (GNA), which determines a set of node pairs and the new cable routes to be deployed between each of them to make the network always remain connected when a regional failure of a given size occurs. With the proposed GNA design framework, we provide mathematical analysis and efficient heuristic algorithms that are built on the latest computational geometry tools and combinatorial optimization techniques. Through extensive simulation, we demonstrate that augmentation with just a small number of new cable routes will achieve the desired resilience against all the considered regional failures.

To evaluate the expected availability of a backbone network service, the administrator should consider all possible failure scenarios under the specific service availability model stipulated in the corresponding service-level agreement. Given the increase in natural disasters and malicious attacks with geographically extensive impact, considering only independent single component failures is often insufficient. This paper builds a stochastic model of geographically correlated link failures caused by disasters to estimate the hazards an optical backbone network may be prone to and to understand the complex correlation between possible link failures. We first consider link failures only and later extend our model also to capture node failures. With such a model, one can quickly extract essential information such as the probability of an arbitrary set of network resources to fail simultaneously, the probability of two nodes to be disconnected, the probability of a path to survive a disaster. Furthermore, we introduce standard data structures and a unified terminology on Probabilistic Shared Risk Link Groups (PSRLGs), along with a pre-computation process, which represents the failure probability of a set of resources succinctly. In particular, we generate a quasilinear-sized data structure in polynomial time, which allows the efficient computation of the cumulative failure probability of any set of network elements. Our evaluation is based on carefully pre-processed seismic hazard data matched to real-world optical backbone network topologies.

Bloom filters and their variants are widely used as space-efficient probabilistic data structures for representing sets and are very popular in networking applications. They support fast element insertion and deletion, along with membership queries with the drawback of false positives. Bloom filters can be designed to match the false positive rates that are acceptable for the application domain. However, in many applications, a common engineering solution is to set the false positive rate very small and ignore the existence of the very unlikely false positive answers. This article is devoted to close the gap between the two design concepts ofunlikelyandnot havingfalse positives. We propose a data structure called EGH filter that supports the Bloom filter operations, and besides, it can guarantee false positive free operations for a finite universe and a restricted number of elements stored in the filter. We refer to the limited universe and filter size as the false positive free zone of the filter. We describe necessary conditions for the false-positive free zone of a filter. We then generalize the filter to support the listing of the elements through the use of counters rather than bits. We detail networking applications of the filter and discuss potential generalizations. We evaluate the performance of the filter in comparison with the traditional Bloom filters. We also evaluate the price in terms of memory that needs to be paid to guarantee real false positive-free operations for having a deterministic Bloom filter-like behavior. Our data structure is based on recently developed combinatorial group testing techniques.

Generalized diversity coding is a promising proactive recovery scheme against single edge failures for unicast connections in transport networks. At the source node, the user data is split into two parts, and their bitwise XOR is computed as a third redundancy sub-flow. In order to guarantee instantaneous failure recovery without costly node upgrades, the network must ensure that any two of the three sub-flows reach the destination node in case of a single edge failure only by allowing flow duplication or merging identical flows, and avoiding any coding operation in the core network. In this paper, we investigate the corresponding routing problem to calculate capacity-efficient routes for these sub-flows. We propose a polynomial-time algorithm for topologies without capacity constraints on the links and without capability limitations of the nodes. We show that with node limitations the presented algorithm (as well as a minimum cost disjoint path-pair) provides a 4/3-approximation for the routing problem. Furthermore, we formulate an integer linear program to provide a minimum cost solution with arbitrary constraints in general graphs and we propose a polynomial-time algorithm in directed acyclic graphs. Our simulation results suggest that with upgrading only a small set of core network nodes with flow duplication and merging capabilities most of the benefits of generalized diversity coding can be achieved.

At backbone network planning, an important task is to identify the failures to get prepared for. Technically, a list of link sets, called Shared Risk Link Groups (SRLG), is defined. The observed reliability of network services strongly depends on how carefully this list was selected and whether it contains every high-risk failure event. Regional failures often cause the breakdown of multiple elements of the network, which are physically close to each other. In this article, we show that operators should prepare a network for only a small number of possible regional failure events. In particular, we give an approach to generate the list of SRLGs that hit every possible circular disk shaped disaster of a given radius r. We show that this list has O((n + x)ρr) SRLGs, where n is the number of nodes in the network and x is the number of link crossings, and ρ, is the maximal number of links that could be hit by a circular disaster of radius r. We give a fast polynomial algorithm to enumerate the list of SRLGs and show that its worst-case time complexity is asymptotically optimal under some practical restrictions. Finally, through extensive simulations, we show that this list in practice has a size of ≈ 1.2n.

Bloom filters and their variants are widely used as space efficient probabilistic data structures for representing set systems and are very popular in networking applications. They support fast element insertion and deletion, along with membership queries with the drawback of false positives. Bloom filters can be designed to match the false positive rates that are acceptable for the application domain. However, in many applications a common engineering solution is to set the false positive rate very small, and ignore the existence of the very unlikely false positive answers. This paper is devoted to close the gap between the two design concepts of unlikely and not having false positives. We propose a data structure, called EGH filter, that supports the Bloom filter operations and besides it can guarantee false positive free operations for a finite universe and a restricted number of elements stored in the filter. We refer to the limited universe and filter size as the false positive free zone of the filter. We describe necessary conditions for the false positive free zone of a filter and generalize the filter to support listing of the elements. We evaluate the performance of the filter in comparison with the traditional Bloom filters. Our data structure is based on recently developed combinatorial group testing techniques.

In order to evaluate the expected availability of a service, a network administrator should consider all possible failure scenarios under the specific service availability model stipulated in the corresponding service-level agreement. Given the increase in natural disasters and malicious attacks with geographically extensive impact, considering only independent single link failures is often insufficient. In this paper, we build a stochastic model of geographically correlated link failures caused by disasters, in order to estimate the hazards a network may be prone to, and to understand the complex correlation between possible link failures. With such a model, one can quickly extract information, such as the probability of an arbitrary set of links to fail simultaneously, the probability of two nodes to be disconnected, the probability of a path to survive a failure, etc. Furthermore, we introduce a pre-computation process, which enables us to succinctly represent the joint probability distribution of link failures. In particular, we generate, in polynomial time, a quasilinear-sized data structure, with which the joint failure probability of any set of links can be computed efficiently.

Shared Risk Link Group (SRLG) is a failure the network is prepared for, which contains a set of links subject to a common risk of single failure. During planning a backbone network, the list of SRLGs must be defined very carefully, because leaving out one likely failure event will significantly degrade the observed reliability of the network. Regional failures are manifested at multiple locations of the network, which are physically close to each other. In this paper we show that operators should prepare a network for only a small number of possible regional failure events. In particular, we give a fast systematic approach to generate the list of SRLGs that cover every possible circular disk failure of a given radius r. We show that this list has O((n + x)σr) SRLGs, where n is the number of nodes in the network, x is the number of link crossings, and σris the maximal number of links that could be hit by a disk failure of radius r. Finally through extensive simulations we show that this list in practice has size of ≈ 1.2 n.

In this paper, we propose a new proactive recovery scheme against single edge failures for unicast connections in transport networks. The new scheme is a generalization of diversity coding where the source data AB are split into two parts A and B and three data flows A, B, and their exclusive OR (XOR) A⊕B are sent along the network between the source and the destination node of the connection. By ensuring that two data flows out of the three always operate even if a single edge fails, the source data can be instantaneously recovered at the destination node. In contrast with diversity coding, we do not require the three data flows to be routed along three disjoint paths; however, in our scheme, a data flow is allowed to split into two parallel segments and later merge back. Thus, our generalized diversity coding (GDC) scheme can be used in sparse but still two-connected network topologies. Our proof improves an earlier result of network coding, by using purely graph theoretical tool set instead of algebraic argument. In particular, we show that when the source data are divided into two parts, robust intra-session network coding against single edge failures is always possible without any in-network algebraic operation. We present linear-time robust code construction algorithms for this practical special case in minimal coding graphs. We further characterize this question, and show that by increasing the number of edge failures and source data parts, we lose these desired properties.

A special class of preferences, given by a directed acyclic graph, is considered. They are represented by incomplete pairwise comparison matrices as only partial information is available: for some pairs no comparison is given in the graph. A weighting method satisfies the linear order preservation property if it always results in a ranking such that an alternative directly preferred to another does not have a lower rank. We study whether two procedures, the Eigenvector Method and the Logarithmic Least Squares Method meet this axiom. Both weighting methods break linear order preservation, moreover, the ranking according to the Eigenvector Method depends on the incomplete pairwise comparison representation chosen.

Network-wide local unambiguous failure localization (NL-UFL) has been demonstrated as an interesting scenario of monitoring trails (m-trails). It attempts to enable every node to autonomously localize any failure event in the network in a distributed and all-optical manner by inspecting a set of m-trails traversing through the node. This paper investigates the m-trail allocation problem under the NL-UFL scenario by taking each link and node failure event into consideration. Bound analysis is performed using combinatorial group testing (CGT) theory and this is followed by the introduction of a novel heuristic on general topologies. Extensive simulation is conducted to examine the proposed heuristic in terms of the required cover length and the number of m-trails to achieve NL-UFL.

Survivable routing methods have been thoroughly investigated in the past decades in transport networks. However, the proposed approaches suffered either from slow recovery time, poor bandwidth utilization, high computational or operational complexity, and could not really provide an alternative to the widely deployed single edge failure resilient dedicated 1 + 1 protection approach. Diversity coding is a candidate to overcome these difficulties with a relatively simple technique: dividing the connection data into two parts, and adding some redundancy at the source node. However, a missing link to make diversity coding a real alternative to 1+1 in transport networks is finding its minimum cost survivable routing, even in sparse topologies, where previous approaches may fail. In this paper we propose a polynomial-time algorithm with O(|V||E| log |V|) complexity for this routing problem. On the other hand, we show that the same routing problem turns to be NP-hard as soon as we limit the forwarding capabilities of some nodes and the capacities of some links of the network.

Shared protection, such as failure-dependent protection (FDP), is well recognized for its outstanding capacity efficiency in all-optical mesh networks, at the expense of lengthy restoration time due to multihop signaling mechanisms for failure localization, notification, and device configuration. This paper investigates a novel monitoring trail (m-trail) scenario, called Global Neighborhood Failure Localization (G-NFL), that aims to enable any shared protection scheme, including FDP, for achieving all-optical and ultra-fast failure restoration. We first define the neighborhood of a node, which is a set of links whose failure states should be known to the node in restoration of the corresponding working lightpaths (W-LPs). By assuming every node can obtain the on-off status of traversing m-trails and W-LPs via lambda monitoring, the proposed G-NFL problem routes a set of m-trails such that each node can localize any failure in its neighborhood. Bound analysis is performed on the minimum bandwidth required for m-trails under the proposed G-NFL problem. Then, a simple yet efficient heuristic approach is presented. Extensive simulation is conducted to verify the proposed G-NFL scenario under a number of different definitions of nodal neighborhood that concern the extent of dependency between the monitoring plane and data plane. The effect of reusing the spare capacity by FDP for supporting m-trails is examined. We conclude that the proposed G-NFL scenario enables a general shared protection scheme, toward signaling-free and ultra-fast failure restoration like p-Cycle, while achieving optimal capacity efficiency as FDP.

Network-wide local unambiguous failure localization (NL-UFL) [1] has been demonstrated as an interesting scenario of monitoring trails (m-trails). It attempts to enable every node to autonomously localize any failure event in the network in a distributed and all-optical manner by inspecting a set of m-trails traversing through the node. This paper investigates the m-trail allocation problem under the NL-UFL scenario by taking each link and node failure event into consideration. Bound analysis is performed using combinatorial group testing (CGT) theory and this is followed by the introduction of a novel heuristic on general topologies. Extensive simulation is conducted to examine the proposed heuristic in terms of the required cover length and the number of m-trails to achieve NL-UFL.

In this paper we close the gap between end-to-end diversity coding and intra-session network coding for unicast connections resilient against single link failures. In particular, we show that coding operations are sufficient to perform at the source and receiver if the user data can be split into at most two parts over the filed GF(2). Our proof is purely combinatorial and based on standard graph and network flow techniques. It is a linear time construction that defines the route of subflows A, B and A ⊕ B between the source and destination nodes. The proposed resilient flow decomposition method generalizes the 1+1 protection and the end-to-end diversity coding approaches while keeping both of their benefits. It provides a simple yet resource efficient protection method feasible in 2-connected backbone topologies. Since the core switches do not need to be modified, this result can bring benefits to current transport networks.

Failure dependent protection (FDP) is known to achieve optimal capacity efficiency among all types of protection, at the expense of longer recovery time and more complicated signaling overhead. This particularly hinders the usage of FDP in all-optical mesh networks. As a remedy, this paper investigates a new restoration framework that enables all-optical fault management and device configuration via state-of-the-art failure localization techniques, such as the FDP restoration process. It can be implemented without relying on any control plane signaling. With the proposed restoration framework, a novel spare capacity allocation problem is defined and is further analyzed on circulant topologies for any single link failure, aiming to gain a solid understanding of the problem. By allowing reuse of monitoring resources for restoration capacity, we are particularly interested in the monitoring resource hidden property, where less or even no monitoring resources are consumed as more working traffic is in place. To deal with general topologies, we introduce a novel heuristic approach to the proposed spare capacity allocation problem, which comprises a generic FDP survivable routing scheme followed by a novel monitoring resource allocation method. Extensive simulation is conducted to examine the proposed scheme and verify the proposed restoration framework.

The paper investigates a novel monitoring trail (m-trail) scenario that can enable any shared protection scheme for achieving all-optical and ultra-fast failure restoration. Given a set of working (W-LPs) and protection (P-LPs) lightpaths, we firstly define the neighborhood of a node, which is a set of links whose failure states should be known to the node in restoration of the corresponding W-LPs. A set of m-trails is routed such that each node can localize any failure in its neighborhood according to the ON-OFF status of the traversing m-trails. Bound analysis is performed on the minimum bandwidth required for the m-trails. Extensive simulation is conducted to verify the proposed scheme.

The paper considers the problem of single-link failure localization in all-optical mesh networks. Our study follows a generic monitoring approach using supervisory lightpaths (S-LPs), in which a set of bi-directional monitoring trails (bm-trails) are defined and closely monitored, such that the network controller can achieve unambiguous failure localization (UFL) for any single link by collecting the flooded alarms from the affected bm-trails. With a target of minimizing the number of bm-trails (or the length of alarm codes) required for single-link UFL, the paper provides optimal (or essentially optimal) solutions to the bm-trail allocation problem on a number of well known topologies. First we demonstrate that the theoretical lower bound of [log2(|E|+1)] bm-trails can be achieved in any 2 · [{ log2{(|E|+1)} }] connected graph, where |E| is the number of links. Next, we prove an essentially optimal solution for 1-by-N grid topologies (also known as chocolate bar graphs), where [{0.42+ log2{(|E|+2)}}] bm-trails can be achieved. Based on the solution for chocolate bars, we further investigate bm-trail solutions to general 2-dimensional (2D) grid topologies, and the developed solution requires no more than 3+[ log2(|E|+1)] bm-trails for UFL. Such an optimal (or essentially optimal) logarithmic behavior, although has been well observed in general topologies in our previous studies , is formalized for the first time in this paper via a suite of polynomial-time deterministic constructions that consume less than a few seconds of running time in topologies of thousands of nodes.

Monitoring trail (m-trail) has been proposed as an effective approach for link failure localization in all-optical wavelength division multiplexing (WDM) mesh networks. Previous studies in failure localization rely on alarm dissemination via control plane signaling such that the network controller can collect the flooded alarms to form an alarm code for failure identification. Such cross-layer signaling effort obviously leads to additional control complexity. This paper investigates a novel m-trail failure localization scenario, called network-wide local unambiguous failure localization (NWL-UFL), where each node can perform UFL based on locally available on–off state of traversing m-trails, such that alarm dissemination in the control plane can be completely avoided. The paper first defines and formulates the m-trail allocation problem under NWL-UFL and conducts a series of bound analysis on the cover length required for localizing any single-link failure. This is the first study on monitoring trail allocation problem that aims to gain understanding on the consumed cover length via analytical approaches due to the special feature of the NWL-UFL scenario. A novel heuristic algorithm based on random spanning tree assignment (RSTA) and greedy link swapping (GLS) is developed for solving the formulated problem. Extensive simulation on thousands of randomly generated network topologies is conducted to verify the proposed scheme by comparing it to a naive counterpart and with the derived lower bounds. We also demonstrate the impact of topology diversity on the performance of the proposed scheme as well as its scalability regarding network sizes.

Achieving fast and precise failure localization has long been a highly desired feature in all-optical mesh networks. Monitoring trail (m-trail) has been proposed as the most general monitoring structure for achieving unambiguous failure localization (UFL) of any single link failure while effectively reducing the amount of alarm signals flooding the networks. However, it is critical to come up with a fast and intelligent m-trail design approach for minimizing the number of m-trails and the total bandwidth consumed, which ubiquitously determines the length of the alarm code and bandwidth overhead for the m-trail deployment, respectively. In this paper, the m-trail design problem is investigated. To gain a deeper understanding of the problem, we first conduct a bound analysis on the minimum length of alarm code of each link required for UFL on the most sparse (i.e., ring) and dense (i.e., fully meshed) topologies. Then, a novel algorithm based on random code assignment (RCA) and random code swapping (RCS) is developed for solving the m-trail design problem. The algorithm is verified by comparison to an integer linear program (ILP) approach, and the results demonstrate its superiority in minimizing the fault management cost and bandwidth consumption while achieving significant reduction in computation time. To investigate the impact of topology diversity, extensive simulation is conducted on thousands of random network topologies with systematically increased network density.

Achieving fast, precise, and scalable fault localization has long been a highly desired feature in all-optical mesh networks. Monitoring tree (m-tree) is an interesting method that has been introduced as the most general monitoring structure for achieving unambiguous failure localization (UFL). Ideally, with J m-trees one can monitor up to 2J-1 links when a single failure has to be located. Such a logarithmic behavior has also been observed in numerous case studies of real life network topologies. It is expected that the m-tree framework will lead to a highly scalable link failure monitoring mechanism for not only all-optical mesh networks, but any possible future information system with mesh topologies, such as all-optical mesh networks, touch panels, quantum computing, and VLSI. It is an important task to investigate the extent such an optimal logarithmic behavior may hold, in particular in practically relevant network topologies. As an endeavor toward this goal, the paper investigates the problem by identifying essentially tight logarithmic bounds for two dimensional lattice networks. Experiments are conducted to show the feasibility and performance of the proposed constructions.

Let f1,..., fs be a system of polynomials in K[x1,..., xm] generating a zero-dimensional ideal I , where K is an arbitrary algebraically closed field. Assume that the factor algebra A = K[x1 , . . . , xm]/I is Gorenstein and that we have a bound delta > 0 such that a basis for A can be computed from multiples of f1,..., fs of degrees at most delta. We propose a method using Sylvester or Macaulay type resultant matrices of f1,..., fs and J , where J is a polynomial of degree delta generalizing the Jacobian, to compute moment matrices, and in particular matrices of traces for A. These matrices of traces in turn allow us to compute a system of multiplication matrices {Mxi|i = 1,..., m} of the radical of I, following the approach in the previous work by Janovitz-Freireich, Ronyai and Szanto. Additionally, we give bounds for delta for the case when I has finitely many projective roots.

We present a method based on Dickson's lemma to compute the "approximate radical" of a zero dimensional ideal I in C[x1, . . . , xm] which has zero clusters: the approximate radical ideal has exactly one root in each cluster for sufficiently small clusters. Our method is "global" in the sense that it does not require any local approximation of the zero clusters: it reduces the problem to the computation of the numerical nullspace of the so called "matrix of traces", a matrix computable from the generating polynomials of I. To compute the numerical nullspace of the matrix of traces we propose to use Gauss elimination with pivoting, and we prove that if I has k distinct zero clusters each of radius at most ε in the ∞-norm, then k steps of Gauss elimination on the matrix of traces yields a submatrix with all entries asymptotically equal to ε2. We also prove that the computed approximate radical has one root in each cluster with coordinates which are the arithmetic mean of the cluster, up to an error term asymptotically equal to ε2. In the univariate case our method gives an alternative to known approximate square-free factorization algorithms which is simpler and its accuracy is better understood.

This paper contains two main results. The first is an explicit construction of bipartite graphs which do not contain certain complete bipartite subgraphs and have maximal density, up to a constant factor, under this constraint. This construction represents the first significant progress in three decades on this old problem in extremal graph theory. The construction beats the previously known probabilistic lower bound on density. The proof uses the elements of commutative algebra and algebraic geometry (theory of ideals, integral extensions, valuation rings). The second result concerns monotone span programs. We obtain the first superpolynomial lower bounds for explicit functions in this model. The best previous lower bound was $\Omega(n^{5/2})$ by Beimel, Gal, Paterson (FOCS’95); our analysis exploits a general combinatorial lower bound criterion from that paper. We give two proofs of superpolynomial lower bounds; one based on an analysis of Paley-type bipartitie graphs via Weil’s character sum estimates. A third result demonstrates the power of monotone span programs by exhibiting a function computable in this model in linear size while requiring superpolynomial size monotone circuits and exponential size monotone formulae.

Let p be a prime and F be a polynomial with integer coefficients. Suppose that the discriminant of F is not divisible by p. Denote by m the degree of the splitting field of F over Q and by L, the maximal size of the coefficients of F. Then, assuming the generalized Riemann hypothesis (GRH ), the irreducible factors of F modulo p in (deterministic) time polynomial in deg F, m, L, and $\log p$ can be found. This is a generalization of a result of Huang [Riemann hypothesis and finding roots over finite fields, in Proceedings of the 17th ACM Symposium on Theory of Computing, Providence, Rhode Island, 1985, pp.121–130]. As an application, under GRH certain equations of the form $nP = R$ can be solved, where R is a given and P is an unknown point of an elliptic curve defined over $GF ( p )$ in polynomial time (n is counted in unary). Finally, an elliptic analogue of a result obtained recently by von zur Gathen [Theoretical Computer Science, 52 (1987), pp. 77–89] and independently by Mignotte and Schnorr [Comptes Rendus de l’Académie des Sciences. Série I. Mat hematique, 306 (1988), pp. 467–472] is proved, and thus a step is taken toward enlarging the set of primes p for which, under GRH, polynomials over $GF ( p )$ in deterministic polynomial time can be factored.

The bit complexity of computing irreducible representations of finite groups is considered. Exact computations in algebraic number fields are performed symbolically. A polynomial-time algorithm for finding a complete set of inequivalent irreducible representations over the field of complex numbers of a finite group given by its multiplication table is presented. It follows that some representative of each equivalence class of irreducible representations admits a polynomial-size description. The problem of decomposing a given representation V of the finite group G over an algebraic number field F into absolutely irreducible constituents is considered. It is shown that this can be done in deterministic polynomial time if V is given by the list of matrices (V(g); g in G) and in randomized (Las Vegas) polynomial time under the more concise input (V(g); g in S), where S is a set of generators of G.>

Let p be a prime and F be a polynomial with integer coefficients. Suppose that the discriminant of F is not divisible by p, and denote by m the degree of the splitting field of F over Q and by L the maximal size of the coefficients of F. Then, assuming the generalized Riemann hypothesis (GRH), it is shown that the irreducible factors of F modulo p can be found in deterministic time polynomial in deg F, m, log p, and L. As an application, it is shown that it is possible under GRH to solve certain equations of the form nP=R, where R is a given and P is an unknown point of an elliptic curve defined over GF(p) in polynomial time (n is counted in unary). An elliptic analog of results obtained recently about factoring polynomials with the help of smooth multiplicative subgroups of finite field is proved.>

We propose a new deterministic method of factoring polynomials over finite fields. Assuming the Generalized Riemann Hypothesis (GRH), we obtain, in polynomial time, the factorization of any polynomial with a bounded number of irreducible factors. Other consequences include a polynomial time algorithm to find a nontrivial factor of any completely splitting even degree polynomial when a quadratic nonresidue in the field is given.

Let F be a finite field or an algebraic number field. In previous work we have shown how to find the basic building blocks (the radical and the simple components) of a finite dimensional algebra over F in polynomial time (deterministically in characteristic zero and Las Vegas in the finite case). Here we address the more general problem of finding zero divisors in A. This problem is equivalent to finding a nontrivial common invariant subspace of a set of linear operators and includes, as a subcase, the problem of factoring polynomials over the field in question. In [FR] the problem of zero divisors has been reduced, in polynomial time (Las Vegas in the finite case), to the case of simple algebras. We show that, while zero divisors can be found in Las Vegas polynomial time if F is finite, the problem over the rationals might be substantially more difficult. We link the problem to hard number theoretic problems such as quadratic residuosity modulo a composite number. We show that assuming the Generalized Riemann Hypothesis, there exists a randomized polynomial time reduction from quadratic residuosity to determining whether or not a given 4-dimensional algebra over Q has zero divisors. It will follow that finding a pair of zero divisors is at least as hard as factoring squarefree integers.

The first structure theory in abstract algebra was that of finite dimensional Lie algebras (Cartan-Killing), followed by the structure theory of associative algebras (Wedderburn-Artin). These theories determine, in a non-constructive way, the basic building blocks of the respective algebras (the radical and the simple components of the factor by the radical). In view of the extensive computations done in such algebras, it seems important to design efficient algorithms to find these building blocks.