Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDeterministic elliptic curve primality proving for a special sequence of numbers
96
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We give a deterministic algorithm that very quickly proves the primality or compositeness of the integers N in a certain sequence, using an elliptic curve E/Q with complex multiplication by the ring of integers of Q(sqrt(-7)). The algorithm uses O(log N) arithmetic operations in the ring Z/NZ, implying a bit complexity that is quasi-quadratic in log N. Notably, neither of the classical N-1 or N+1 primality tests apply to the integers in our sequence. We discuss how this algorithm may be applied, in combination with sieving techniques, to efficiently search for very large primes. This has allowed us to prove the primality of several integers with more than 100,000 decimal digits, the largest of which has more than a million bits in its binary representation. At the time it was found, it was the largest proven prime N for which no significant partial factorization of N-1 or N+1 is known.
rate research
Read More
We provide a framework for using elliptic curves with complex multiplication to determine the primality or compositeness of integers that lie in special sequences, in deterministic quasi-quadratic time. We use this to find large primes, including the largest prime currently known whose primality cannot feasibly be proved using classical methods.
In this paper, we derive some identities involving special numbers and moments of random variables by using the generating functions of the moments of certain random variables. Here the related special numbers are Stirling numbers of the first and second kinds, degenerate Stirling numbers of the first and second kinds, derangement numbers, higher-order Bernoulli numbers and Bernoulli numbers of the second kind.
The Baillie-PSW primality test combines Fermat and Lucas probable prime tests. It reports that a number is either composite or probably prime. No odd composite integer has been reported to pass this combination of primality tests if the parameters are chosen in an appropriate way. Here, we describe a significant strengthening of this test that comes at almost no additional computational cost. This is achieved by including in the test what we call Lucas-V pseudoprimes, of which there are only five less than $10^{15}$.
The Mordell-Weil groups $E(mathbb{Q})$ of elliptic curves influence the structures of their quadratic twists $E_{-D}(mathbb{Q})$ and the ideal class groups $mathrm{CL}(-D)$ of imaginary quadratic fields. For appropriate $(u,v) in mathbb{Z}^2$, we define a family of homomorphisms $Phi_{u,v}: E(mathbb{Q}) rightarrow mathrm{CL}(-D)$ for particular negative fundamental discriminants $-D:=-D_E(u,v)$, which we use to simultaneously address questions related to lower bounds for class numbers, the structures of class groups, and ranks of quadratic twists. Specifically, given an elliptic curve $E$ of rank $r$, let $Psi_E$ be the set of suitable fundamental discriminants $-D<0$ satisfying the following three conditions: the quadratic twist $E_{-D}$ has rank at least 1; $E_{text{tor}}(mathbb{Q})$ is a subgroup of $mathrm{CL}(-D)$; and $h(-D)$ satisfies an effective lower bound which grows asymptotically like $c(E) log (D)^{frac{r}{2}}$ as $D to infty$. Then for any $varepsilon > 0$, we show that as $X to infty$, we have $$#, left{-X < -D < 0: -D in Psi_E right } , gg_{varepsilon} X^{frac{1}{2}-varepsilon}.$$ In particular, if $ell in {3,5,7}$ and $ell mid |E_{mathrm{tor}}(mathbb{Q})|$, then the number of such discriminants $-D$ for which $ell mid h(-D)$ is $gg_{varepsilon} X^{frac{1}{2}-varepsilon}.$ Moreover, assuming the Parity Conjecture, our results hold with the additional condition that the quadratic twist $E_{-D}$ has rank at least 2.
Let $E_1$ and $E_2$ be $overline{mathbb{Q}}$-nonisogenous, semistable elliptic curves over $mathbb{Q}$, having respective conductors $N_{E_1}$ and $N_{E_2}$ and both without complex multiplication. For each prime $p$, denote by $a_{E_i}(p) := p+1-#E_i(mathbb{F}_p)$ the trace of Frobenius. Under the assumption of the Generalized Riemann Hypothesis (GRH) for the convolved symmetric power $L$-functions $L(s, mathrm{Sym}^i E_1otimesmathrm{Sym}^j E_2)$ where $i,jin{0,1,2}$, we prove an explicit result that can be stated succinctly as follows: there exists a prime $p mid N_{E_1}N_{E_2}$ such that $a_{E_1}(p)a_{E_2}(p)<0$ and [ p < big( (32+o(1))cdot log N_{E_1} N_{E_2}big)^2. ] This improves and makes explicit a result of Bucur and Kedlaya. Now, if $Isubset[-1,1]$ is a subinterval with Sato-Tate measure $mu$ and if the symmetric power $L$-functions $L(s, mathrm{Sym}^k E_1)$ are functorial and satisfy GRH for all $k le 8/mu$, we employ similar techniques to prove an explicit result that can be stated succinctly as follows: there exists a prime $p mid N_{E_1}$ such that $a_{E_1}(p)/(2sqrt{p})in I$ and [ p < left((21+o(1)) cdot mu^{-2}log (N_{E_1}/mu)right)^2. ]
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
