Primality test for numbers of the form $(2p)^{2^n}+1$

• Autorzy: Yingpu Deng , Dandan Huang
• Języki publikacji: EN

Abstrakty

EN

We describe a primality test for $M=(2p)^{2^n}+1$ with an odd prime p and a positive integer n, which are a particular type of generalized Fermat numbers. We also present special primality criteria for all odd prime numbers p not exceeding 19. All these primality tests run in deterministic polynomial time in the input size log₂M. A special 2pth power reciprocity law is used to deduce our result.

Kategorie tematyczne

• 11A51: Factorization; primality
• 11Y11: Primality

• Wydawca: Institute of Mathematics Polish Academy of Sciences
• Czasopismo: Acta Arithmetica
• Rocznik: 2015
• Tom: 169
• Numer: 4
• Strony: 301-317

Daty

wydano

2015

Twórcy

autor

Yingpu Deng

• Key Laboratory of Mathematics Mechanization, NCMIS, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, 100190, Beijing, P.R. China

autor

Dandan Huang

• Key Laboratory of Mathematics Mechanization, NCMIS, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, 100190, Beijing, P.R. China

Identyfikatory

DOI

10.4064/aa169-4-1