Search

We revisit the seminal Brill–Noether algorithm for plane curves with ordinary singularities. Our new approach takes advantage of fast algorithms for polynomials and structured matrices. We design a new probabilistic algorithm of Las Vegas type that computes a Riemann–Roch space in expected sub-quadratic time. [ABSTRACT FROM AUTHOR]

In this paper, we represent vector bundles over a regular algebraic curve as pairs of lattices over the maximal orders of its function field and we give polynomial time algorithms for several tasks: computing determinants of vector bundles, kernels and images of global homomorphisms, isomorphisms between vector bundles, cohomology groups, extensions, and splitting into a direct sum of indecomposables. Most algorithms are deterministic except for computing isomorphisms when the base field is infinite. Some algorithms are only polynomial time if we may compute Hermite forms of pseudo-matrices in polynomial time. All algorithms rely exclusively on algebraic operations in function fields. For applications, we give an algorithm enumerating isomorphism classes of vector bundles on an elliptic curve, and to construct algebraic geometry codes over vector bundles. We implement all our algorithms into a SageMath package. [ABSTRACT FROM AUTHOR]

The paper is an introduction to the use of the classical Newton–Puiseux procedure, oriented towards an algorithmic description of it. This procedure allows to obtain polynomial approximations for parameterizations of branches of an algebraic plane curve at a singular point. We look for an approach that can be easily grasped and is almost self-contained. We illustrate the use of the algorithm first in a completely worked out example of a curve with a point of multiplicity 6, and secondly, in the study of triple points on reduced plane curves. [ABSTRACT FROM AUTHOR]

Application of the method of computing the location of all types of level lines of a real polynomial on the real plane is demonstrated. The theory underlying this method is based on methods of local and global analysis by the means of power geometry and computer algebra. Three nontrivial examples of computing level lines of real polynomials on the real plane are discussed in detail. The following computer algebra algorithms are used: factorization of polynomials, computation of the Gröbner basis, construction of the Newton polygon, and representation of an algebraic curve on a plane. It is shown how computational difficulties can be overcome. [ABSTRACT FROM AUTHOR]

The usual univariate interpolation problem of finding a monic polynomial f of degree n that interpolates n given values is well understood. This paper studies a variant where f is required to be composite, say, a composition of two polynomials of degrees d and e , respectively, with d e = n , and with d + e − 1 given values. Some special cases are easy to solve, and for the general case, we construct a homotopy between it and a special case. We compute a geometric solution of the algebraic curve presenting this homotopy, and this also provides an answer to the interpolation task. The computing time is polynomial in the geometric data, like the degree, of this curve. A consequence is that for almost all inputs, a decomposable interpolation polynomial exists. [ABSTRACT FROM AUTHOR]

The original algorithm of D.V. Chudnovsky and G.V. Chudnovsky for the multiplication in extensions of finite fields provides a bilinear complexity which is uniformly linear with respect to the degree of the extension. Recently, Randriambololona generalized the method, allowing asymmetry in the interpolation procedure. The aim of this article is to make effective this method. We first make explicit this generalization in order to construct the underlying asymmetric algorithms. Then, we propose a generic strategy to construct these algorithms using places of higher degrees and without derivated evaluation. Finally, we provide examples of three multiplication algorithms along with their Magma implementation: in F 16 13 using only rational places, in F 4 5 using also places of degree two, and in F 2 5 using also places of degree four. [ABSTRACT FROM AUTHOR]

We present a complete algorithm for computing the affine equivalences between two implicit planar algebraic curves. We provide evidence of the efficiency of the algorithm, implemented in Maple, and compare its performance with existing algorithms. As a part of the process for developing the algorithm, we characterize planar algebraic curves, possibly singular, possibly reducible, invariant under infinitely many affine equivalences. [ABSTRACT FROM AUTHOR]

In algebraic geometry, the Frobenius map (or called Frobenius action , or Frobenius operator) F ⁎ on cohomology groups plays an important role in the classification of algebraic varieties over a field of positive characteristic. In particular, representation matrices for F ⁎ give rise to many important invariants such as p -rank and a -number. Several methods for computing representation matrices for F ⁎ have been proposed for specific curves. In this paper, we present an algorithm to compute representation matrices for F ⁎ of general projective schemes over a perfect field of positive characteristic. We also propose an efficient algorithm specific to complete intersections; it requires to compute only certain coefficients in a power of a multivariate polynomial. Our algorithms shall derive fruitful applications such as computing Hasse-Witt matrices, and enumerating superspecial curves. In particular, the second algorithm for complete intersections provides a useful tool to judge the superspeciality of an algebraic curve, which is a key ingredient to prove main results in Kudo and Harashita (2017a,b, 2020) on the enumeration of superspecial genus-4 curves. [ABSTRACT FROM AUTHOR]

Algorithms and software for two new methods of solving polynomial equations based on constructing a convex polygon are described. The first method approximately solves the equations using the Hadamard polygon. The second method makes it possible to find branches of an algebraic curve in the vicinity of its singular points and in the vicinity of infinity using the Newton polygon and sketch real algebraic curves on the plane. The corresponding geometries and computer algebra algorithms for analyzing arbitrarily complicated cases are discussed. [ABSTRACT FROM AUTHOR]

Partial derivatives are widely used to convert regular expressions to nondeterministic automata. For the word membership problem, it is not strictly necessary to build an automaton. In this paper, we study the size of partial derivatives on the average case. For expressions in strong star normal form, we show that on average and asymptotically the largest partial derivative is at most half the size of the expression. The results are obtained in the framework of analytic combinatorics considering generating functions of parametrised combinatorial classes defined implicitly by algebraic curves. Our average case estimates suggest that a detailed word membership algorithm based directly on partial derivatives should be analysed both theoretically and experimentally. [ABSTRACT FROM AUTHOR]

In algebraic geometry, it is important to provide effective parametrizations for families of curves, both in theory and in practice. In this paper, we present such an effective parametrization for the moduli of genus-5 curves that are neither hyperelliptic nor trigonal. Subsequently, we construct an algorithm for a complete enumeration of non-special genus-5 curves having more rational points than a specified bound, where "non-special curve" means that the curve is non-hyperelliptic and non-trigonal with mild singularities of the associated sextic model that we propose. As a practical application, we implement this algorithm using the computer algebra system MAGMA, specifically for curves over the prime field of characteristic 3. [ABSTRACT FROM AUTHOR]

We provide an efficient algorithm to detect whether two given trigonometric curves, i.e. two parametrized curves whose components are truncated Fourier series, in any dimension, are affinely equivalent, i.e. whether there exists an affine mapping transforming one of the curves onto the other. If the coefficients of the parametrizations are known exactly (the exact case), the algorithm boils down to univariate gcd computation, so it is efficient and fast. If the coefficients of the parametrizations are known with finite precision, e.g. floating point numbers (the approximate case), the univariate gcd computation is replaced by the computation of approximate gcds. Our experiments show that the method works well, even for high degrees. [ABSTRACT FROM AUTHOR]

Separated variables for a classical GL(3) magnetic chain are coordinates of a generic positive divisor D of degree n on a genus g nonhyperelliptic algebraic curve. Because n > g, this divisor D has unique representative ρ(D) in the Jacobian, which can be constructed by using dim|D| = n − g steps of Abel’s algorithm. We study the properties of the corresponding chain of divisors and prove that the classical GL(3) magnetic chain is a superintegrable system with dim|D| = 2 superintegrable Hamiltonians. [ABSTRACT FROM AUTHOR]

In 2015, Guth [Math. Proc. Cambridge Philos. Soc., 159 (2015), pp. 459{469] proved that for any set of k-dimensional bounded complexity varieties in Rd and for any positive integer D, there exists a polynomial of degree at most D whose zero set divides Rd into open connected sets so that only a small fraction of the given varieties intersect each of these sets. Guth's result generalized an earlier result of Guth and Katz [Ann. Math., 181 (2015), pp. 155{190] for points. Guth's proof relies on a variant of the Borsuk-Ulam theorem, and for k > 0, it is unknown how to obtain an explicit representation of such a partitioning polynomial and how to construct it efficiently. In particular, it is unknown how to effectively construct such a polynomial for bounded-degree algebraic curves (or even lines) in R³. We present an efficient algorithmic construction for this setting. Given a set of n input algebraic curves and a positive integer D, we efficiently construct a decomposition of space into O(D3 log3 D) open "cells," each of which meets O(n=D2) curves from the input. The construction time is O(n²). For the case of lines in 3-space, we present an improved implementation whose running time is O(n4/3 polylog n). The constant of proportionality in both time bounds depends on D and the maximum degree of the polynomials defining the input curves. As an application, we revisit the problem of eliminating depth cycles among nonvertical lines in 3-space, recently studied by Aronov and Sharir [Discrete Comput. Geom., 59 (2018), pp. 725{741] and show an algorithm that cuts n such lines into O(n3/2+ɛ) pieces that are depth-cycle free for any · > 0. The algorithm runs in O(n3/2+ɛ) time, which is a considerable improvement over the previously known algorithms. [ABSTRACT FROM AUTHOR]

We present an algorithm for computing the Berkovich skeleton of a superelliptic curve yn = f(x) over a valued field. After defining superelliptic weighted metric graphs, we show that each one is realizable by an algebraic superelliptic curve when n is prime. Lastly, we study the locus of superelliptic weighted metric graphs inside the moduli space of tropical curves of genus g. [ABSTRACT FROM AUTHOR]

Based on analogies between algebraic curves and graphs, Baker and Norine introduced divisorial gonality , a graph parameter for multigraphs related to treewidth, multigraph algorithms and number theory. Various equivalent definitions of the gonality of an algebraic curve translate to different notions of gonality for graphs, called stable gonality and stable divisorial gonality. We consider so-called hyperelliptic graphs (multigraphs of gonality 2, in any meaning of graph gonality) and provide a safe and complete set of reduction rules for such multigraphs. This results in an algorithm to recognize hyperelliptic graphs in time O (m + n log ⁡ n) , where n is the number of vertices and m the number of edges of the multigraph. A corollary is that we can decide with the same runtime whether a two-edge-connected graph G admits an involution σ such that the quotient G / 〈 σ 〉 is a tree. [ABSTRACT FROM AUTHOR]

In this paper, we first summarize the algorithm presented in Blasco and Pérez-Díaz (2014) for computing the generalized asymptotes of algebraic curves implicitly defined. This algorithm is based on the computation of Puiseux series. The main and very important contribution of this paper is a new and efficient method that allows to easily compute all the generalized asymptotes of an algebraic plane curve implicitly defined by just solving a triangular system of equations. The method can be easily generalized to the case of algebraic curves implicitly defined in the n -dimensional space. [ABSTRACT FROM AUTHOR]

In this paper, we give a fast algorithm for the computation of the Arf closure of an algebroid curve with more than one branch, generalizing an algorithm presented by Arslan and Sahin for the algebroid branch case. [ABSTRACT FROM AUTHOR]

We make use of the complex implicit representation in order to provide a deterministic algorithm for checking whether or not two implicit algebraic curves are related by a similarity. The algorithm has been implemented in the computer algebra system Maple 2016. The implementation can be freely downloaded from the webpage of one of the authors. Examples and evidence of the good practical performance of the algorithm are given. [ABSTRACT FROM AUTHOR]

We present effective upper bounds on the symmetric bilinear complexity of multiplication in extensions of a base finite field Fp2 of prime square order, obtained by combining estimates on gaps between prime numbers together with an optimal construction of auxiliary divisors for multiplication algorithms by evaluation-interpolation on curves. Most of this material dates back to a 2011 unpublished work of the author, but it still provides the best results on this topic at the present time. Then a few updates are given in order to take recent developments into account, including comparison with a similar work of Ballet and Zykin, generalization to classical bilinear complexity over Fp, and to short multiplication of polynomials, as well as a discussion of open questions on gaps between prime numbers or more generally values of certain arithmetic functions. [ABSTRACT FROM AUTHOR]

For an elliptic curve E over a finite field Fq, where q is a prime power, we propose new algorithms for testing the supersingularity of E. Our algorithms are based on the polynomial identity testing problem for the p-th division polynomial of E. In particular, an efficient algorithm using points of high order on E is given. [ABSTRACT FROM AUTHOR]

Abstract In this paper, we provide a method that allows to construct parametric curves having (or not) non-ordinary singularities and having (or not) neighboring points. This method is based on a characterization of the non-ordinary singularities and neighboring points by means of linear equations involving the given parametrization. As a consequence, we obtain an algorithm that constructs a parametrization which contains a given point, P , as a singularity as well as some additional information as for instance, the order of P , parameters corresponding to P , multiplicity of each parameter and the singularities in the first neighborhood of the singularity P. Highlights • We provide a method that allows to construct parametric curves having (or not) non-ordinary singularities and having (or not) neighboring points. • The method is based on a characterization of the non-ordinary singularities and neighboring points by means of linear equations. • We obtain an algorithm that outputs a parametrization of a rational curve having singularities at some given input points. • In the algorithm, the singularity, P , the order of P , the parameters (and their multiplicity) corresponding to P , and the first neighborhood of P , are fixed. • We translate every detail of the definitions and resolutions into the language of parametric equations, which are quite helpful to CAGD. [ABSTRACT FROM AUTHOR]

We improve previously known lower bounds for the minimum distance of certain two-point AG codes constructed using a Generalized Giulietti–Korchmaros curve (GGK). Castellanos and Tizziotti recently described such bounds for two-point codes coming from the Giulietti–Korchmaros curve. Our results completely cover and in many cases improve on their results, using different techniques, while also supporting any GGK curve. Our method builds on the order bound for AG codes: to enable this, we study certain Weierstrass semigroups. This allows an efficient algorithm for computing our improved bounds. We find several new improvements upon the MinT minimum distance tables. [ABSTRACT FROM AUTHOR]

We shall propose two verifiable multi-secret sharing schemes based on novel nonhomogeneous linear recursions. In the initial phase, the secret shadow of each participant is selected by himself. In the construction phase, the dealer puts the information of shared secrets in the initialization vector of non-homogeneous linear recursions of degree t - 1. In the verification phase, verification algorithms based on elliptic curve are designed to resist a variety of cheating actions or attacks. In the recovery phase, each participant just needs to provide secret share instead of secret shadow. The proposed schemes have the following features: verifiability, the reuse of secret shadows and shared secrets is possible, only public channels are needed. Compared with previous schemes, they have better performance, fewer public values, lower computation complexity, shorter key length and less running time [ABSTRACT FROM AUTHOR]

This paper introduces the Binomial Expansion Cryptosystem, a prototype for a crpytosytem which could also be of interest to small elite organizations. Let be a set of positive integers. The Binomial Expansion Cryptosystem exploits the one to one correspondence between a finite integer power product expansion, , and its associated power series representation , by taking the product representation, converting it into series format, and transmitting a set of N coefficients, namely . The crux of our decryption amounts to solving a finite number of Diophantine equations. It is accomplished through a so called Generalized Top-Down Algorithm and transforms into . Algebraic and complexity properties of the Generalized Top-Down Algorithm are analyzed. Preliminary security issues are discussed. Numerous detailed examples are provided. [ABSTRACT FROM AUTHOR]

Recently an image encryption algorithm based on DNA encoding and the Elliptic Curve Cryptography (ECC) is proposed. This paper aims to investigate the security the DNA-based image encryption algorithm and its resistance against chosen plaintext attack. The results of the analysis demonstrate that security of the algorithm mainly relies on one static shuffling step, with a simple confusion operation. In this study, a practical plain image recovery method is proposed, and it is shown that the images encrypted with the same key could easily be recovered using the suggested cryptanalysis method with as low as two chosen plain images. Also, a strategy to improve the security of the algorithm is presented in this paper. [ABSTRACT FROM AUTHOR]

We give an optimal-size representation for the elements of the trace zero subgroup of the Picard group of an elliptic or hyperelliptic curve of any genus, with respect to a field extension of any prime degree. The representation is via the coefficients of a rational function, and it is compatible with scalar multiplication of points. We provide efficient compression and decompression algorithms, and complement them with implementation results. We discuss in detail the practically relevant cases of small genus and extension degree, and compare with the other known compression methods. [ABSTRACT FROM AUTHOR]

Point compression is an essential technique to save bandwidth and memory when deploying elliptic curve based security solutions in wireless communication systems. In this contribution, we provide new linear algebra (LA) based compression algorithms for multiple points on elliptic curves, that are compression algorithms which only make use of LA (with a constant number of field multiplications and at most one inversion, with no quadratic or higher degree polynomial root finding). In particular, we extend the results of Khabbazian et al. (IEEE Trans Comput 56(3):305-313, 2007) to four (resp. five) points on elliptic curves by generically storing five (resp. six) field elements and provide an asymptotic generalization to any number n of points on a curve $$y^2=f(x)$$ by generically storing $$n+1$$ values. [ABSTRACT FROM AUTHOR]

Let C be a real plane algebraic curve defined by the resultant of two polynomials (resp. by the discriminant of a polynomial). Geometrically such a curve is the projection of the intersection of the surfaces P ( x , y , z ) = Q ( x , y , z ) = 0 (resp. P ( x , y , z ) = ∂ P ∂ z ( x , y , z ) = 0 ), and generically its singularities are nodes (resp. nodes and ordinary cusps). State-of-the-art numerical algorithms compute the topology of smooth curves but usually fail to certify the topology of singular ones. The main challenge is to find practical numerical criteria that guarantee the existence and the uniqueness of a singularity inside a given box B , while ensuring that B does not contain any closed loop of C . We solve this problem by first providing a square deflation system, based on subresultants, that can be used to certify numerically whether B contains a unique singularity p or not. Then we introduce a numeric adaptive separation criterion based on interval arithmetic to ensure that the topology of C in B is homeomorphic to the local topology at p . Our algorithms are implemented and experiments show their efficiency compared to state-of-the-art symbolic or homotopic methods. [ABSTRACT FROM AUTHOR]

Computing large Riemann–Roch spaces for plane projective curves still constitutes a major algorithmic and practical challenge. Seminal applications concern the construction of arbitrarily large algebraic geometry error correcting codes over alphabets with bounded cardinality. Nowadays such codes are increasingly involved in new areas of computer science such as cryptographic protocols and "interactive oracle proofs". In this paper, we design a new probabilistic algorithm of Las Vegas type for computing Riemann–Roch spaces of smooth divisors, in characteristic zero, and with expected complexity exponent 2.373 (a feasible exponent for linear algebra) in terms of the input size. [ABSTRACT FROM AUTHOR]

The notion of strict equivalence for order one differential equations of the form f ( y ′ , y , z ) = 0 with coefficients in a finite extension K of C ( z ) is introduced. The equation gives rise to a curve X over K and a derivation D on its function field K ( X ) . Procedures are described for testing strict equivalence, strict equivalence to an autonomous equation, computing algebraic solutions and verifying the Painlevé property. These procedures use known algorithms for isomorphisms of curves over an algebraically closed field of characteristic zero, the Risch algorithm and computation of algebraic solutions. The most involved cases concern curves X of genus 0 or 1. This paper complements work of M. Matsuda and of G. Muntingh & M. van der Put. [ABSTRACT FROM AUTHOR]

The implementation of a library of basic functions for the construction and analysis of planar quintic Pythagorean-hodograph (PH) curves is presented using the complex representation. The special algebraic structure of PH curves permits exact algorithms for the computation of key properties, such as arc length, elastic bending energy, and offset (parallel) curves. Single planar PH quintic segments are constructed as interpolants to first-order Hermite data (end points and derivatives), and this construction is then extended to open or closed C2 PH quintic spline curves interpolating a sequence of points in the plane. The nonlinear nature of PH curves incurs a multiplicity of formal solutions to such interpolation problems, and a key aspect of the algorithms is to efficiently single out the unique “good” interpolant among them. [ABSTRACT FROM AUTHOR]

Securing provenance data in distributed environment is a challenge and with the rapid increase in its size, volume and variety it becomes more challenging. Provenance data are more sensitive than actual data as they include the workflow or the chain kind of structure. A little change can be disastrous. There are various existing security algorithms and frameworks but distributed nature of infrastructure and large volume of data makes the implementation of existing security models very complex. This paper discusses the security challenges of provenance data and proposes a secure way to store provenance data in highly distributed infrastructure. [ABSTRACT FROM AUTHOR]

This paper proposes the computation of the Tate pairing, Ate pairing and its variations on the special Jacobi quartic elliptic curve . We improve the doubling and addition steps in Miller's algorithm to compute the Tate pairing. We use the birational equivalence between Jacobi quartic curves and Weierstrass curves, together with a specific point representation to obtain the best result to date among curves with quartic twists. For the doubling and addition steps in Miller's algorithm for the computation of the Tate pairing, we obtain a theoretical gain up to and , depending on the embedding degree and the extension field arithmetic, with respect to Weierstrass curves and previous results on Jacobi quartic curves. Furthermore and for the first time, we compute and implement Ate, twisted Ate and optimal pairings on the Jacobi quartic curves. Our results are up to more efficient compared to the case of Weierstrass curves with quartic twists. [ABSTRACT FROM AUTHOR]

Algorithms describing the topology of real algebraic curves search primarily the singular points and they are usually based on algebraic techniques applied directly to the curve equation. We adopt a different approach, which is primarily based on the identification and approximation of smooth monotonous curve segments, which can in certain cases cross the singularities of the curve. We use not only the primary algebraic equation of the planar curve but also (and more importantly) its implicit support function representation. This representation is also used for an approximation of the segments. This way we obtain an approximate graph of the entire curve which has several nice properties. It approximates the curve within a given Hausdorff distance. The actual error can be measured efficiently and behaves as O ( N − 3 ) where N is the number of segments. The approximate graph is rational and has rational offsets. In the simplest case it consists of arc segments which are efficiently represented via the support function. The question of topological equivalence of the approximate and precise graphs of the curve is also addressed and solved using bounding triangles and axis projections. The theoretical description of the whole procedure is accompanied by several examples which show the efficiency of our method. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the notion of infinity branches as well as approaching curves. We present some properties which allow us to obtain an algorithm that compares the behavior of two implicitly defined algebraic plane curves at the infinity. As an important result, we prove that if two plane algebraic curves have the same asymptotic behavior, the Hausdorff distance between them is finite. [ABSTRACT FROM AUTHOR]

We present an algorithm for the computation of the topological type of a real compact Riemann surface associated to an algebraic curve, i.e., its genus and the properties of the set of fixed points of the anti-holomorphic involution τ, namely, the number of its connected components, and whether this set divides the surface into one or two connected components. This is achieved by transforming an arbitrary canonical homology basis to a homology basis where the A-cycles are invariant under the anti-holomorphic involution τ. [ABSTRACT FROM AUTHOR]

We analyze the complexity of the computation of the class group structure, regulator, and a system of fundamental units of an order in a certain class of number fields. Our approach differs from Buchmann's, who proved a complexity bound under the generalized Riemann hypothesis of L(1/2,O(1)) when the discriminant tends to infinity with fixed degree. We achieve a heuristic subexponential complexity in O(L(1/3,O(1))) under the generalized Riemann hypothesis when both the discriminant and the degree of the extension tend to infinity by using techniques due to Enge, Gaudry and Thomé in the context of algebraic curves over finite fields. We also address rigorously the problem of the precision of the computation of the regulator. [ABSTRACT FROM AUTHOR]

We develop in this article an algorithm that, given a projective curve $$C$$ , computes a gonal map, that is, a finite morphism from $$C$$ to $$\mathbb P ^1$$ of minimal degree. Our method is based on the computation of scrollar syzygies of canonical curves. We develop an improved version of our algorithm for curves with a unique gonal map and we discuss a characterization of such curves in terms of Betti numbers. Finally, we derive an efficient algorithm for radical parametrization of curves of gonality $$\le 4$$ . [ABSTRACT FROM AUTHOR]

Abstract: We present an algorithm that, given a non-rational irreducible real space curve, satisfying certain conditions, computes a rational parametrization of a space curve near the input one. For a given tolerance , the algorithm checks whether a planar projection of the given space curve is ϵ-rational and, in the affirmative case, generates a planar parametrization that is lifted to a space parametrization. This output rational space curve is of the same degree as the input curve, both have the same structure at infinity, and the Hausdorff distance between their real parts is finite. Moreover, in the examples we check that the distance is small. [Copyright &y& Elsevier]

Abstract: In this paper we present a fast addition algorithm in the Jacobian of a curve over a finite field . We give formulae for which require when and when ; and for the computation of −D which require . The ⊕ operation is sufficient to compute scalar multiplications after performing a single (initial) −D. Computing the scalar multiplication , based on the previous fact combined with our algorithm for computing , is to date the fastest one performing this operation for curves. These formulae can be easily combined to compute the full group addition and doubling in and respectively, which compares favorably with previously presented formulae. [Copyright &y& Elsevier]

Abstract: We present a certified and complete algorithm to compute arrangements of real planar algebraic curves. It computes the decomposition of the plane induced by a finite number of algebraic curves in terms of a cylindrical algebraic decomposition. From a high-level perspective, the overall method splits into two main subroutines, namely an algorithm denoted Bisolve to isolate the real solutions of a zero-dimensional bivariate system, and an algorithm denoted GeoTop to compute the topology of a single algebraic curve. Compared to existing approaches based on elimination techniques, we considerably improve the corresponding lifting steps in both subroutines. As a result, generic position of the input system is never assumed, and thus our algorithm never demands for any change of coordinates. In addition, we significantly limit the types of symbolic operations involved, that is, we only use resultant and computations as purely symbolic operations. The latter results are achieved by combining techniques from different fields such as (modular) symbolic computation, numerical analysis and algebraic geometry. We have implemented our algorithms as prototypical contributions to the C++-project Cgal. We exploit graphics hardware to expedite the remaining symbolic computations. We have also compared our implementation with the current reference implementations, that is, Lgp and Maple’s Isolate for polynomial system solving, and Cgal’s bivariate algebraic kernel for analyses and arrangement computations of algebraic curves. For various series of challenging instances, our exhaustive experiments show that the new implementations outperform the existing ones. [Copyright &y& Elsevier]

A low storage algorithm for constructing isogenies between ordinary elliptic curves was proposed by Galbraith, Hess and Smart (GHS). We give an improvement of this algorithm by modifying the pseudorandom walk so that lower-degree isogenies are used more frequently. This is motivated by the fact that high degree isogenies are slower to compute than low degree ones. We analyse the running time of the parallel collision search algorithm when the partitioning is uneven. We also give experimental results. We conclude that our algorithm is around $$14$$ times faster than the GHS algorithm when constructing horizontal isogenies between random isogenous elliptic curves over a $$160$$-bit prime field. The results apply to generic adding walks and the more general group action inverse problem; a speed-up is obtained whenever the cost of computing edges in the graph varies significantly. [ABSTRACT FROM AUTHOR]

Abstract: Optimal approximation of closed polygons differs from the case of open polygons in the sense that the location of a starting point must be determined in a suitable way. We present an algorithm which first computes a proper extremal arc as starting point and then approximates the input polygon with a minimum number of circular arcs and line segments. The resulting curve is called Cyclic Minimum Arc Path (CMAP). Our algorithm guarantees the CMAP staying inside a user-specified tolerance. In contrast to the existing approaches, we do not restrict the breakpoints of the arc spline to a predefined set of points but choose them automatically. This has considerable effects on the resulting number of segments. We can handle every type of tolerance zone representing the user-specified tolerance as long it is formed by piecewise restricted analytic curves. In case of polygonal tolerance zones the proposed algorithm takes time for an original polygonal chain with n vertices. For generating a solution which has at most one additional segment we present an algorithm. [Copyright &y& Elsevier]

Abstract: We give explicit computational algorithms to construct minimal degree (always ⩽4) ramified covers of for algebraic curves of genus 5 and 6. This completes the work of Schicho and Sevilla (who dealt with the case) on constructing radical parametrisations of arbitrary genus g curves. Zariski showed that this is impossible for the general curve of genus ⩾7. We also construct minimal degree birational plane models and show how the existence of degree 6 plane models for genus 6 curves is related to the gonality and geometric type of a certain auxiliary surface. [Copyright &y& Elsevier]

Abstract: We address the algebraic problem of analyzing the local topology of each singularity of a plane complex algebraic curve defined by a squarefree polynomial with both exact (i.e. integers or rationals) and inexact data (i.e. numerical values). For the inexact data, we associate a positive real number that measures the noise in the coefficients. This problem is ill-posed in the sense that tiny changes in the input produce huge changes in the output. We design a regularization method for estimating the local topological type of each singularity of a plane complex algebraic curve. Our regularization method consists of the following: (i) a symbolic–numeric algorithm that computes the approximate local topological type of each singularity; (ii) and a parameter choice rule, i.e. a function in the noise level. We prove that the symbolic–numeric algorithm together with the parameter choice rule computes an approximate solution, which satisfies the convergence for noisy data property. We implement our algorithm in a new software package called GENOM3CK written in the Axel free algebraic geometric modeler and in the Mathemagix free computer algebra system. For our purpose, both of these systems provide modern graphical capabilities, and algebraic and geometric tools for exact and inexact input data. [Copyright &y& Elsevier]

Abstract: Computing offset curves and surfaces is a fundamental operation in many technical applications. This paper discusses some issues that are encountered during the process of designing offsets, especially the problems of their reducibility and rationality (which are closely related). This study is crucial especially for formulating subsequent algorithms when the number and quality of offset components must be revealed. We will formulate new algebraic and geometric conditions on reducibility of offsets and demonstrate how they can be applied. In addition, we will present that our investigations can also serve to better understand the varieties fulfilling the Pythagorean conditions (PH curves/PN surfaces). A certain analogy of the PH condition for parameterized curves (or general parameterized hypersurfaces) will be presented also for implicitly given (not necessarily rational) curves (or hypersurfaces). [Copyright &y& Elsevier]