Serwis Infona wykorzystuje pliki cookies (ciasteczka). Są to wartości tekstowe, zapamiętywane przez przeglądarkę na urządzeniu użytkownika. Nasz serwis ma dostęp do tych wartości oraz wykorzystuje je do zapamiętania danych dotyczących użytkownika, takich jak np. ustawienia (typu widok ekranu, wybór języka interfejsu), zapamiętanie zalogowania. Korzystanie z serwisu Infona oznacza zgodę na zapis informacji i ich wykorzystanie dla celów korzytania z serwisu. Więcej informacji można znaleźć w Polityce prywatności oraz Regulaminie serwisu. Zamknięcie tego okienka potwierdza zapoznanie się z informacją o plikach cookies, akceptację polityki prywatności i regulaminu oraz sposobu wykorzystywania plików cookies w serwisie. Możesz zmienić ustawienia obsługi cookies w swojej przeglądarce.
For an odd composite number n, let w(n) denote the least witness for n; that is, the least positive number w for which n is not a strong pseudoprime to the base w. It is widely conjectured, but not proved, that w(n) > 3 for infinitely many n. We show the stronger result that w(n) > (log n)1/(3 log log log n) for infinitely many n. We also show that there are finite sets of odd composites which...
This is a report on work in progress on our new implementation of the relation collection stage of the general number field sieve integer factoring algorithm. Our experiments indicate that we have achieved a substantial speed-up compared to other implementations that are reported in the literature. The main improvements are a new lattice sieving technique and a trial division method that is based...
There are well known subexponential algorithms for finding discrete logarithms over finite fields. However, the methods which underlie these algorithms do not appear to be easily adaptable for finding discrete logarithms in the groups associated with elliptic curves and the Jacobians of hyperelliptic curves. This has led to the development of cryptographic systems based on the discrete logarithm problem...
We report on algorithmic aspects of the problem of explicitly computing the rate of growth of the field of Nk-th division points on an n-dimensional simple Abelian variety with Complex Multiplication. Two new examples are discussed.
The heart of Schoof's algorithm for computing the cardinality m of an elliptic curve over a finite field is the computation of m modulo small primes l. Elkies and Atkin have designed practical improvements to the basic algorithm, that make use of “good” primes l. We show how to use powers of good primes in an efficient way. This is done by computing isogenies between curves over the ground field....
We present a variant of an algorithm of Oliver Atkin for counting the number of points on an elliptic curve over a finite field. We describe an implementation of this algorithm for prime fields. We report on the use of this implementation to count the number of points on a curve over $$\mathbb{F}$$ p, where p is a 375-digit prime.
Functional decomposition—whether a function f(x) can be written as a composition of functions g(h(x)) in a nontrivial way—is an important primitive in symbolic computation systems. The problem of univariate polynomial decomposition was shown to have an efficient solution by Kozen and Landau [9]. Dickerson [5] and von zur Gathen [13] gave algorithms for certain multivariate cases. Zippel [15] showed...
In this paper we present a technique that uses a new interpolation scheme to reconstruct a multivariate polynomial factorization from a number of univariate factorizations. Whereas other interpolation algorithms for polynomial factorization depend on various extensions of the Hilbert irreducibility theorem, our approach is the first to depend only upon the classical formulation. The key to our technique...
The fastest method known for factoring integers is the ‘number field sieve’. An analogous method over function fields is developed, the ‘function field sieve’, and applied to calculating discrete logarithms over GF(pn). An heuristic analysis shows that there exists a cε ℜ>0 such that the function field sieve computes discrete logarithms within random time: Lp...
We discuss the computational application of Heegner points to the study of elliptic curves over Q, concentrating on the curves Ed: Dy2 = x3 − x arising in the “congruent number” problem. We begin by briefly reviewing the cyclotomic construction of units in real quadratic number fields, which is analogous in many ways to the Heegner-point approach...
The Weil-Taniyama conjecture states that every elliptic curve E/ℚ of conductor N can be parametrized by modular functions for the congruence subgroup Γ0(N) of the modular group Γ = PSL(2, ℤ). Equivalently, there is a non-constant map ϕ from the modular curve X0(N) to E. We present here a method of computing the degree of such a map ϕ for arbitrary N. Our method, which works for...
The Gaussian algorithm for lattice reduction in dimension 2 (under both the standard version and the centered version) is analysed. It is found that, when applied to random inputs, the complexity is asymptotically constant, the probability distribution decays geometrically, and the dynamics is characterized by a conditional invariant measure. The proofs make use of connections between lattice reduction,...
Let L be a k-dimensional lattice in IRm with basis B = (b1,...,bk). Let A = (a1,...,ak) be a rational approximation to B. Assume that A has rank k and a lattice basis reduction algorithm applied to the columns of A yields a transformation T = (t1,...,tk) ε GL(k, ℤ) such that Ati ≤ si...
We introduce a new left-shift binary algorithm, LSBGCD, for computing the greatest common divisor of two integers, and we provide an analysis of the worst-case behavior of this algorithm. The analysis depends on a theorem of Ramharter about the extremal behavior of certain continuants.
Podaj zakres dat dla filtrowania wyświetlonych wyników. Możesz podać datę początkową, końcową lub obie daty. Daty możesz wpisać ręcznie lub wybrać za pomocą kalendarza.