اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدDeterministic elliptic curve primality proving for a special sequence of numbers
93
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 se
cond 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 ar
e 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 def
ine 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. ]
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
