Algorithms for Relatively Cyclotomic Primes

• Autorzy: Grześkowiak M.
• Języki publikacji: EN

Abstrakty

EN

We present a general method of generating primes p and q such that q divides Φn(p), where n > 2 is a fixed number. In particular, we present the deterministic method of finding a primitive nth roots of unity modulo q. We estimate the computational complexity of our methods.

Słowa kluczowe

EN

computing a primitive nth root of unity modulo primes; primes of special form; public key cryptography

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 125, nr 2
• Strony: 161--181
• Opis fizyczny: Bibliogr. 33 poz.

Twórcy

autor

Grześkowiak M.

• Adam Mickiewicz University, Faculty of Mathematics and Computer Science, Umultowska 87, 61-614 Poznań, Poland

Bibliografia

• [1] Agrawal, M., Kayal, N., Saxena, N.: Primes is in P, Annals of Mathematics, 160(2), September 2004, 781793.
• [2] Saban Alaca, Williams, K. S.: Introductory Algebraic Number Theory, Cambridge University Press, 2004.
• [3] Arnold, A., Monagan, M. B.: Calculating cyclotomic polynomials, Math. Comput., 80(276), 2011, 23592379.
• [4] Bach, E., von zur Gathen, J., Jr., H. W. L.: Factoring polynomials over special finite fields, Finite Fields and Their Applications, 7(1), 2001, 5 -28, ISSN 1071-5797.
• [5] Bach, E., Shallit, J.: Algorithmic Number Theory, Volume I: Efficient Algorithms, MIT Press, 1996.
• [6] Bateman, P., Horn, R.: A heuristic asymptotic formula concerning the distribution of prime numbers, Math. Comp., 16, 1962, 363-367, ISSN 0025-5718.
• [7] Borevich, Z., Shafarevich, I.: Number Theory, Academic Press, 1966, ISBN 9780121178512.
• [8] Buell, D. A., Ed.: Algorithmic Number Theory, 6th International Symposium, ANTS-VI, Burlington, VT, USA, June 13-18, 2004, Proceedings, vol. 3076 of Lecture Notes in Computer Science, Springer, 2004, ISBN 3-540-22156-5.
• [9] Davenport, H.: Multiplicative Number Theory, Springer-Verlag, 1980.
• [10] van Dijk, M., Granger, R., Page, D., Rubin, K., Silverberg, A., Stam, M., Woodruff, D.: Practical cryptography in high dimensional tori, Proc. of24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Advances in Cryptology - (EUROCRYPT’05), Aarhus, Denmark, LNCS, 3494, Springer-Verlag, May 2005.
• [11] Giuliani, K., Gong, G.: Analogues to the Gong-Harn andXTR cryptosystems, Technical Report 34, CORR, The University of Waterloo, 2003.
• [12] Gong, G., Harn, L.: Public-key cryptosystems based on cubic finite field extension, IEEE Transactions on Information Theory, 45(7), November 1999, 2601-2605.
• [13] Grześkowiak, M.: Generating a large prime pactor of p4 ±p2 + 1 in polynomial time, OTM Conferences (2), 2008.
• [14] Grześkowiak, M.: On generating elements of rders dividing p2k ± pk + 1, IWSEC, 2008.
• [15] Grześkowiak, M.: Algorithm for generating primes for the Giuliani-Gong public key system, Journal of Internet Services and Information Security (JISIS), 1(2/3), 8 2011, 21-31.
• [16] Grześkowiak, M.: Generating elements of orders dividing p6 ± p5 + p4 ± p3 + p2 + p ± 1, Ann. UMCS, Inf., 11(2), January 2011, 113-125, ISSN 1732-1360.
• [17] Grześkowiak, M.: Algorithm for generating primes p and q such that q divides p4 ±p3 + p2 ±p +1, Fundam. Inform., 114(3-4), 2012, 287-299.
• [18] Heath-Brown, D.: Almost-primes in arithmetic progression and short intervals, Proc. London Proc. Cambridge Phil. Soc., 86, 1978, 357-375.
• [19] Karatsuba, A.: Basic Analytic Number Theory, Springer-Verlag, 1983.
• [20] Lang, S.: Algebraic Number Theory, Springer-Verlag, 1994, ISBN 978-0-387-94225-4.
• [21] Lenstra, A., Verheul, E.: The XTR public key system, Proc. of 20th Annual International Cryptology Conference Crypto 2000, Advances in Cryptology (CRYPTO 2000), Santa Barbara, California, USA, LNCS, 1880, Springer-Verlag, August 2000.
• [22] Lenstra, A. K.: Factoring multivariate polynomials over algebraic number fields, SIAM J. Comput., 16(3), 1987, 591-598.
• [23] Narkiewicz, W.: Elementary and Analytic Theory of Algebraic Numbers, Springer-Verlag, 2004, ISBN 978-3-540-21902-6.
• [24] Pila, J.: Frobenius maps of abelian varieties and finding roots of unity in finite fields, 55(192), October 1990, 745-763, ISSN 0025-5718 (print), 1088-6842 (electronic).
• [25] Rabin, M.: Probabilistic algorithm for testing primality, J. Number Theory, 12(1), 1980, 128-138.
• [26] Rotaru, A. S., Iftene, S.: A complete generalization of Atkin’s square root algorithm, Fundam. Inform., 123, 2013, in press.
• [27] Rubin, K., Silverberg, A.: Torus-based cryptography, CRYPTO, 2003.
• [28] Rubin, K., Silverberg, A.: Using primitive subgroups to do more with fewer bits, in: Buell [8], 18-41.
• [29] Schinzel, A., Sierpinski, W.: Sur Certaines Hypotheses Concernment Les Nombres Premiers, Acta Arith., 4, 1958, 185-208, Erratum 5 (1958).
• [30] Sze, T.-W., Washington, L. C.: On taking square roots without quadratic nonresidues over finite fields, Math. Comput., 80(275), 2011, 1797-1811.
• [31] Titchmarsh, E.: A divisor problem, Rend. Circ. Mat. Palermo, 54, 1943, 87-105.
• [32] Wagstaff, S.: Greatest of the least primes in arithmetic progressions having a given modulus, Math. Comp., 33, 1979, 1073-1080.
• [33] Zrałek, B.: Using partial smoothness of p-1 for factoring polynomials modulo p, Math. Comput., 79(272), 2010, 2353-2359.