A Conjecture on Primes in Arithmetic Progressions and Geometric Intervals

in American Mathematical Monthly (2022), 129(10), 979-983

Dirichlet’s theorem on primes in arithmetic progressions states that for any positive integer q and any coprime integer a, there are infinitely many primes in the arithmetic progression a + nq (n ∈ N ... [more ▼]

Dirichlet’s theorem on primes in arithmetic progressions states that for any positive integer q and any coprime integer a, there are infinitely many primes in the arithmetic progression a + nq (n ∈ N). Unfortunately, the theorem does not predict the gap between those primes. Several renowned open questions such as the size of Linnik’s constant try to say more about the distribution of such primes. This manuscript postulates a weak, but explicit, generalization of Linnik’s theorem, namely that each geometric interval [q^t, q^(t+1)] contains a prime from each coprime congruence class modulo q ∈ N≥2. Subsequently, it proves the conjecture theoretically for all sufficiently large t, as well as computationally for all sufficiently small q. Finally, the impact of this conjecture on a result of Pomerance related to Carmichael’s conjecture is outlined. [less ▲]

Twisted Edwards-Form Elliptic Curve Cryptography for 8-bit AVR-based Sensor Nodes

in Chen, Kefei; Xie, Qi; Qiu, Weidong (Eds.) et al Proceedings of the first ACM Workshop on Asia Public-Key Cryptography (ASIAPKC 2013) (2013, May)

Wireless Sensor Networks (WSNs) pose a number of unique security challenges that demand innovation in several areas including the design of cryptographic primitives and protocols. Despite recent progress ... [more ▼]

Wireless Sensor Networks (WSNs) pose a number of unique security challenges that demand innovation in several areas including the design of cryptographic primitives and protocols. Despite recent progress, the efficient implementation of Elliptic Curve Cryptography (ECC) for WSNs is still a very active research topic and techniques to further reduce the time and energy cost of ECC are eagerly sought. This paper presents an optimized ECC implementation that we developed from scratch to comply with the severe resource constraints of 8-bit sensor nodes such as the MICAz and IRIS motes. Our ECC software uses Optimal Prime Fields (OPFs) as underlying algebraic structure and supports two different families of elliptic curves, namely Weierstraß-form and twisted Edwards-form curves. Due to the combination of efficient field arithmetic and fast group operations, we achieve an execution time of 5.8*10^6 clock cycles for a full 158-bit scalar multiplication on an 8-bit ATmega128 microcontroller, which is 2.78 times faster than the widely-used TinyECC library. Our implementation also shows that the energy cost of scalar multiplication on a MICAz (or IRIS) mote amounts to just 19 mJ when using a twisted Edwards curve over a 160-bit OPF. This result compares fairly well with the energy figures of two recently-presented hardware designs of ECC based on twisted Edwards curves. [less ▲]

Finding the Eigenvalue in Elkies' Algorithm

in Experimental Mathematics (2001), 10(2), 275-285

One important part of Elkies' algorithm for computing the group order of an elliptic curve is the search for an eigenvalue of the Frobenius endomorphism. In this paper we compare two well known algorithms ... [more ▼]

One important part of Elkies' algorithm for computing the group order of an elliptic curve is the search for an eigenvalue of the Frobenius endomorphism. In this paper we compare two well known algorithms with two new ideas based on the Babystep Giantstep method. Moreover we show how resultants can be used to speed up this search. Finally we present a fast probabilistic algorithm for checking whether a given rational function is congruent to an entry in a table of rational functions modulo some fixed polynomial. [less ▲]

Efficient Point Multiplication for Elliptic Curves over Special Optimal Exten­sion Fields

in Proceedings of Public-Key Cryptography and Computational Number Theo­ry Conference (2000)

I generalize an idea of Gallant, Lambert, Vanstone for fast multipli­cation of points on elliptic curves with efficient endomorphisms. I describe how this generaliza­tion improves point multiplication for ... [more ▼]

I generalize an idea of Gallant, Lambert, Vanstone for fast multipli­cation of points on elliptic curves with efficient endomorphisms. I describe how this generaliza­tion improves point multiplication for elliptic curves defined over optimal extension fields. Finally we present practical results for the new algo­rithm compared to Gal­lant's algorithm. [less ▲]

A Few Remarks on the Security of Internet Applications

in Proceedings of he First International Workshop on Information Integration and Web-based Applications & Services (1999)

In this short publication, I present a few facts on the security of some cur­rent In­ternet applications. Since one strong focus of this conference was the us­age of the In­ternet for electronic business ... [more ▼]

In this short publication, I present a few facts on the security of some cur­rent In­ternet applications. Since one strong focus of this conference was the us­age of the In­ternet for electronic business applications, I address two applica­tions often used in electronic business: electronic mail (E-mail) and se­cure ac­cess of web pages using the SSL protocol. It should be noted that all the facts presented in the note are well-known to security experts and not new. It might however be helpful for the ordinary of electronic commerce to become more aware of some security-related problems of the Internet. [less ▲]

Fast Multiplication on Elliptic Curves over Small Fields of Characteristic Two

in Journal of Cryptology (1998), 11(4), 219-234

The paper shows how Frobenius expansions can be used to speed up mul­tiplication of points on elliptic curves that are defined over very small fields of charac­teristic two. The Frobenius expansion ... [more ▼]

The paper shows how Frobenius expansions can be used to speed up mul­tiplication of points on elliptic curves that are defined over very small fields of charac­teristic two. The Frobenius expansion algorithm is analyzed in theory and in practice. It can gain significant improvements in practical applica­tions. These curves are there­fore especially interesting for implementations of elliptic curve cryptosystems. [less ▲]

A Public Key Cryptosystem based on Elliptic Curves over Z/nZ Equivalent to Factoring

in Advances in Cryptology - Eurocrypt '96 (1996)

The paper describes a new cryptosystem for elliptic curves over the ring Z/nZ which is equivalent to the Rabin-Williams cryptosystem. We prove that breaking the new cryptosystem is equivalent to factoring ... [more ▼]

The paper describes a new cryptosystem for elliptic curves over the ring Z/nZ which is equivalent to the Rabin-Williams cryptosystem. We prove that breaking the new cryptosystem is equivalent to factoring the modulus n. [less ▲]

Counting the Number of Points on Elliptic Curves over Finite Fields of Characteristic Greater than Three

in Proceedings of Algorithmic Number Theory Symposium I, Lecture Notes in Computer Science (1994)

The paper describes the implementation of the Algorithm of Atkin and Elkies for computing the group order of elliptic curves over large prime fields. The focus of the paper lays on algorithmical aspects ... [more ▼]

The paper describes the implementation of the Algorithm of Atkin and Elkies for computing the group order of elliptic curves over large prime fields. The focus of the paper lays on algorithmical aspects of the Atkin/Elkies algorithm. Practical data and running times are given. [less ▲]

On basis vectors of lattices

E-print/Working paper (n.d.)

Integer lattices enjoy increasing interest among mathematicians and cryptographers. However, there are still many elementary open questions, like finding specific vectors or particular bases of a given ... [more ▼]

Integer lattices enjoy increasing interest among mathematicians and cryptographers. However, there are still many elementary open questions, like finding specific vectors or particular bases of a given lattice. Our study consists in exhibiting which integer vectors may be chosen as basis vectors of a chosen lattice. The compelling part of our development is that this condition is obtained through an unusual application of Dirichlet's Theorem on primes in arithmetic progressions and that it has a surprising consequence for vectors achieving the successive minima. [less ▲]

A conjecture on primes in arithmetic progressions and geometric intervals

E-print/Working paper (n.d.)

We conjecture that any interval of the form [q^t ,q^(t+1) ], where q≥ 2 and t≥1 denote positive integers, contains at least one prime from each coprime congruence class. We prove this conjecture first ... [more ▼]

We conjecture that any interval of the form [q^t ,q^(t+1) ], where q≥ 2 and t≥1 denote positive integers, contains at least one prime from each coprime congruence class. We prove this conjecture first unconditionally for all 2≤q≤45000 and all t≥1 and second under ERH for almost all q≥2 and all t≥2. Furthermore, we outline heuristic arguments for the validity of the conjecture beyond the proven bounds and we compare it with related long-standing conjectures. Finally, we discuss some of its consequences. [less ▲]