Search

We draw a new connection between Coppersmith’s method for finding small solutions to polynomial congruences modulo integers and the capacity theory of adelic subsets of algebraic curves. Coppersmith’s method uses lattice basis reduction to construct an auxiliary polynomial that vanishes at the desired solutions. Capacity theory provides a toolkit for proving when polynomials with certain boundedness properties do or do not exist. Using capacity theory, we prove that Coppersmith’s bound for univariate polynomials is optimal in the sense that there are no auxiliary polynomials of the type he used that would allow finding roots of size \(N^{1/d+\epsilon }\) for any monic degree-d polynomial modulo N. Our results rule out the existence of polynomials of any degree and do not rely on lattice algorithms, thus eliminating the possibility of improvements for special cases or even superpolynomial-time improvements to Coppersmith’s bound. We extend this result to constructions of auxiliary polynomials using binomial polynomials, and rule out the existence of any auxiliary polynomial of this form that would find solutions of size \(N^{1/d+\epsilon }\) unless N has a very small prime factor.

Pollard Rho is one of integer factorization algorithms for factoring the modulus in order to recover the private key which is the one of two keys of RSA and is kept secret. However, this algorithm cannot finish all values of the modulus. Later, New Factorization algorithm (NF) which is based on Pollard Rho was proposed to solve the problem of Pollard Rho that cannot finish all value of the modulus. Nevertheless, both of Pollard Rho and NF have to take time – consuming to find two large prime factors of the modulus, because they must compute the greatest common divisor for all iterations of the computation. In this paper, the method to speed up NF is presented by reducing the size of the parameter which is used to be one of two parameters to compute the greatest common divisor. The reason is, if the size of one of two parameters is reduced, the computation time for computing the greatest common divisor is also decreased. The experimental results show that the computation time of this method is decreased for all values of the modulus. Moreover, the average computation time of the proposed method for factoring the modulus is faster than NF about 6 percentages.

The meeting place of algebra and computer science is called computer algebra. We refer to von zur Gathen & Gerhard (2013) for a comprehensive introduction to it.

Many applications of embedded devices require the generation of cryptographic secret parameters during the life cycle of the product. In such an unsafe context, several papers have shown that key generation algorithms are vulnerable to side-channel attacks. This is in particular the case of the generation of the secret prime factors in RSA . Until now, the threat has been demonstrated against naive implementations whose operations' flow depends on secret data, and a simple countermeasure is to avoid such kind of dependency. In this paper, we propose a new attack that renders this defence strategy ineffective. It is in particular able to break secure implementations recommended by the ANSI X9.31 and FIPS 186-4 standards. We analyse its efficiency for various realistic attack contexts and we demonstrate its practicality through experiments against a smart-card implementation. Possible countermeasures are eventually proposed, drawing the following main conclusion: prime generation algorithms should avoid the use of a prime sieve combined with a deterministic process to generate the prime candidates from a random seed.

It is only natural that we start these notes with probably the oldest Book Proof, usually attributed to Euclid (Elements IX, 20). It shows that the sequence of primes does not end.

Let p and l be prime numbers. In this paper, we consider the l-indivisibility of the class numbers of the intermediate fields in the cyclotomic Z p -extension of Q. Moreover, we study the class numbers of the intermediate fields in the composite of such extensions.

An optical method for prime factorization is modified. The procedure in the original method is similar to that with quantum computing. In this repot, some differences between the quantum solution and the method are discussed. And, improvement for our method is proposed based on the discussion.

Let N = pq be an RSA modulus with a public exponent e and a private exponent d. Wiener’s famous attack on RSA with d < N 0.25 and its extension by Boneh and Durfee to d < N 0.292 show that using a small d makes RSA completely insecure. However, for larger d, it is known that RSA can be broken in polynomial time under special conditions. For example, various partial key exposure attacks on RSA and some attacks using additional information encoded in the public exponent e are efficient to factor the RSA modulus. These attacks were later improved and extended in various ways. In this paper, we present a new attack on RSA with a public exponent e satisfying an equation ed − k(N + 1 − ap − bq) = 1 where \(\frac{a}{b}\) is an unknown approximation of \(\frac{q}{p}\). We show that RSA is insecure when certain amount of the Least Significant Bits (LSBs) of ap and bq are known. Further, we show that the existence of good approximations \(\frac{a}{b}\) of \(\frac{q}{p}\) with small a and b substantially reduces the requirement of LSBs of ap and bq.

There is an extensive literature on perfect powers and “almost” perfect powers in products of the form $$ n\left( {n + d} \right) \ldots \left( {n + \left( {k - 1} \right)d} \right) $$ (1) where n, d, k are positive integers with gcd(n,d) = 1 and k ≥ 3. By an “almost” perfect power we mean a number of the shape b times a perfect power, where b is a positive integer having no prime factor greater than a given number, say k. The classical case d = 1 has been completely settled. Further, for d > 1, a lot of interesting partial results have been published. For survey papers on results obtained before 1999 we refer to Tijdeman [41], [42], Shorey and Tijdeman [37], [38], Shorey [33], [34] and Győry [19].

In the present work we discuss several problems concerning the difference of primes, primarily regarding the difference of consecutive primes. Most of them were either initiated by Paul Erdős (sometimes with coauthors), or were raised ahead of Erdős; nevertheless he was among those who reached very important results in them (like the problem of the large and small gaps between consecutive primes).

Let N, k positive integers, χ a character modulo N. We know that the Hecke operators T(n),(n, N) = 1 can be diagonalized simultaneously in the space S(N,k,χ). On the other hand, if f is an eigenfunction of all Hecke operators T(n), then L(s, f) has an Euler product. So we want to ask the following question: Can all Hecke operators T(n) be diagonalized simultaneously in the space S(N, k, χ).

This work is focused on characterizing the existence of a perfect discrete Morse function on a triangulated 3-manifold M, that is, a discrete Morse function satisfying that the numbers of critical simplices coincide with the corresponding Betti numbers. We reduce this problem to the existence of such kind of function on a spine L of M, that is, a 2-subcomplex L such that M−Δ collapses to L, where Δ is a tetrahedron of M. Also, considering the decomposition of every 3-manifold into prime factors, we prove that if every prime factor of M admits a perfect discrete Morse function, then M admits such kind of function.

An asymmetric pairing $e\colon{\mathbb{G}}_2\times{\mathbb{G}}_1\to{\mathbb{G}}_T$ is considered such that ${\mathbb{G}}_1=E({\mathbb F}_p)[r]$ and ${\mathbb{G}}_2=\tilde E({\mathbb F}_{p^{k/d}})[r]$ , where k is the embedding degree of the elliptic curve $E/{\mathbb F}_p$ , r is a large prime divisor of $\# E({\mathbb F}_p)$ , and $\tilde E$ is the degree-d twist of E over ${\mathbb F}_{p^{k/d}}$ with $r \mid \tilde E ({\mathbb F}_{p^{k/d}} )$ . Hashing to ${\mathbb{G}}_1$ is considered easy, while hashing to ${\mathbb{G}}_2$ is done by selecting a random point Q in $\tilde E({\mathbb F}_{p^{k/d}})$ and computing the hash value cQ, where c·r is the order of $\tilde E({\mathbb F}_{p^{k/d}})$ . We show that for a large class of curves, one can hash to ${\mathbb{G}}_2$ in $\textup{O}(1/\varphi (k)\log c)$ time, as compared with the previously fastest-known $\textup{O}(\log p)$ . In the case of BN curves, we are able to double the speed of hashing to ${\mathbb{G}}_2$ . For higher-embedding-degree curves, the results can be more dramatic. We also show how to reduce the cost of the final-exponentiation step in a pairing calculation by a fixed number of field multiplications.