Implementing the asymptotically fast version of the elliptic curve primality proving algorithm

The elliptic curve primality proving (ECPP) algorithm is one of the current fastest practical algorithms for proving the primality of large numbers. Its running time currently cannot be proven rigorously, but heuristic arguments show that it should run in time to prove the primality of . An asymptotically fast version of it, attributed to J. O. Shallit, is expected to run in time . We describe this version in more detail, leading to actual implementations able to handle numbers with several thousands of decimal digits.

     

Explicit primality criteria for

Deterministic polynomial time primality criteria for have been known since the work of Lucas in 1876-1878. Little is known, however, about the existence of deterministic polynomial time primality tests for numbers of the more general form , where is any fixed prime. When (p-1)/2$"> we show that it is always possible to produce a Lucas-like deterministic test for the primality of which requires that only modular multiplications be performed modulo , as long as we can find a prime of the form such that is not divisible by . We also show that for all with such a can be found very readily, and that the most difficult case in which to find a appears, somewhat surprisingly, to be that for . Some explanation is provided as to why this case is so difficult.

     

Probabilistic algorithm for finding roots of linearized polynomials

A probabilistic algorithm is presented for finding a basis of the root space of a linearized polynomial

构建最小k 重控制集的概率算法

点集D ⊆ V (G) 称为图G 的k 重控制集, 如果D 满足V (G) - D 中任意结点在D 中至少有k 个邻居. 在无线网络中, 最小k 重控制集(MkDS) 用以构建健壮的虚拟骨干网. 构建虚拟骨干网是无线网络中最基本也是最重要的问题. 在本文中, 我们提出一种快速的分布式概率算法来构建k重控制集. 我们构建的k 重控制集的期望大小不超过最优解的O(k²) 倍. 算法的运行时间复杂度为O((Δ logΔ+log log n)n),其中Δ = max{|D(p)|}, D(p) 是以p 为中心半径为1 的圆盘中的结点, 最大值的比较范围是给定集合中所有的p 点.     

Probabilistic viscosity algorithm for the scalar conservation law

We derive an algorithm for solving the initial value problem for u_t = ½σ²u_xx + f(u)u_x. The approach is based on the representation of the solution to the above equation in the form of the functional of Brownian motion. For small σ we get the approximation for u_t = f(u)u_x. A comparison with the random choice method is illustrated by the numerical example.     

The Lucas-Pratt primality tree

In 1876, E. Lucas showed that a quick proof of primality for a prime could be attained through the prime factorization of and a primitive root for . V. Pratt's proof that PRIMES is in NP, done via Lucas's theorem, showed that a certificate of primality for a prime could be obtained in modular multiplications with integers at most . We show that for all constants , the number of modular multiplications necessary to obtain this certificate is greater than for a set of primes with relative asymptotic density 1.

     

Elliptic periods and primality proving

We construct extension rings with fast arithmetic using isogenies between elliptic curves. As an application, we give an elliptic version of the AKS primality criterion.     

A two-stage algorithm for combinatorial testing

Covering arrays are combinatorial structures which have applications in fields like software testing and hardware Trojan detection. In this paper we proposed a two-stage simulated annealing algorithm to construct covering arrays. The proposed algorithm is instanced in this paper through the construction of ternary covering arrays of strength three. We were able to get 579 new upper bounds. In order to show the generality of our proposal, we defined a new benchmark composed of 25 instances of MCAs taken from the literature, all instances were improved.     

An algorithm for testing Leopoldt's conjecture

Based on an elementary version of Leopoldt's conjecture due to Iwasawa and Sands we develop an algorithm for testing this conjecture in an arbitrary algebraic number field for any prime p. Using this algorithm we are able to prove Leopoldt's conjecture for several pure fields of degree 5 and 7. We also discuss relations with class numbers.     

Probabilistic analysis of the next fit decreasing algorithm for bin-packing

We use a simple deterministic inequality to simplify and strengthen previous results on the probabilistic analysis of Next Fit Decreasing for Bin-Packing.     

Elliptic curve primality tests for Fermat and related primes

We use elliptic curves with complex multiplication to develop primality tests for Fermat primes and for primes of the form ?²³−²?−1³+1 and ?²²−²?−1²+1.     

On a class of primality criteria

Translated from Matematicheskie Zametki, Vol. 56, No. 1, pp. 146–148, July, 1994.     

Height bounds,nullstellensatz and primality

In this study, we find height bounds in the polynomial ring over the field of algebraic numbers to test the primality of an ideal. We also obtain height bounds in the arithmetic Nullstellensatz. We apply nonstandard analysis and hence our constants will be ineffective.     

On the primality of

For each prime , let be the product of the primes less than or equal to . We have greatly extended the range for which the primality of and are known and have found two new primes of the first form ( ) and one of the second (). We supply heuristic estimates on the expected number of such primes and compare these estimates to the number actually found.

     

Probabilistic analysis of a parallel algorithm for finding maximal independent sets

We consider a natural parallel version of the classical greedy algorithm for finding a maximal independent set in a graph. This version was studied in Coppersmith, Raghavan, and Tompa and they conjecture there that its expected running time on random graphs of arbitrary edge density of O (log n). We prove that conjecture.     

Proving primality in essentially quartic random time

This paper presents an algorithm that, given a prime , finds and verifies a proof of the primality of in random time . Several practical speedups are incorporated into the algorithm and discussed in detail.

     

Deterministic primality test for numbers of the form odd

We use a result of E. Lehmer in cubic residuacity to find an algorithm to determine primality of numbers of the form , odd, . The algorithm represents an improvement over the more general algorithm that determines primality of numbers of the form , , presented by Berrizbeitia and Berry (1999).