Primality test for numbers of the form (2p)^2ⁿ+1

DOI10.4064/AA169-4-1zbMATH Open1370.11139arXiv1307.1840OpenAlexW2793181854MaRDI QIDQ5261959FDOQ5261959

Authors: Yingpu Deng, Dandan Huang 

Publication date: 8 July 2015

Published in: Acta Arithmetica (Search for Journal in Brave)

Abstract: We describe a primality test for number $M=(2p{)}^{2^n}+1$ with odd prime $p$ and positive integer $n$. And we also give the special primality criteria for all odd primes $p$ not exceeding 19. All these primality tests run in polynomial time in log${}_2(M)$. A certain special $2p$-th reciprocity law is used to deduce our result.

Full work available at URL: https://arxiv.org/abs/1307.1840

Recommendations

• Primality test for numbers of the form \(A p^n + w_n\)
• Primality testing for numbers of the form \(h\cdot 2^n\pm 1\)
• Explicit primality criteria for $(p-1)p^n-1$
• Primality tests for numbers of the form \(k\cdot 2^m\pm 1\)
• Some primality conditions for \(N=2p^n -1\)

zbMATH Keywords

computational complexityprimality testreciprocity lawgeneralized Fermat numbers

Mathematics Subject Classification ID

Factorization; primality (11A51) Primality (11Y11)

Cites Work

• The Magma algebra system. I: The user language
• PRIMES is in P
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Primality test for numbers \(M\) with a large power of 5 dividing \(M^{4}-1\).
• Cubic reciprocity and generalised Lucas-Lehmer tests for primality of 𝐴.3ⁿ±1
• A generalization of Proth's theorem
• Primality test for numbers of the form \(A p^n + w_n\)

Cited In (10)

• Primality tests for 2^{𝑝}±2^{(𝑝+1)/2}+1 using elliptic curves
• Deterministic primality test for numbers of the form \(A^2. 3^n+1\), \(n \geq 3\) odd
• Title not available (Why is that?)
• Conjectured polynomial time primality tests for numbers of special forms
• Primality test for numbers of the form \(A p^n + w_n\)
• An \(\tilde{O}(\log^{2}(N))\) time primality test for generalized Cullen numbers
• Sharpening ``Primes is in P for a large family of numbers
• Effective Primality Tests for Some Integers of the Forms A5 n - 1 and A7 n - 1
• Primality test for numbers \(M\) with a large power of 5 dividing \(M^{4}-1\).
• A primality test for \(Kp^{n}+1\) numbers

Uses Software

• Magma

This page was built for publication: Primality test for numbers of the form \((2p)^{2^n}+1\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5261959)