Analysis and Optimization of Improved Index Calculus Algorithm

Hu Jianjun

doi:doi:10.11648/j.mcs.20230802.14

| Peer-Reviewed

Analysis and Optimization of Improved Index Calculus Algorithm

Hu Jianjun

Published in Mathematics and Computer Science (Volume 8, Issue 2)

Received: 5 April 2023 Accepted: 30 March 2023 Published: 13 April 2023

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

Abstract

IC (Index Calculus) algorithm is the most effective probability algorithm for solving discrete logarithm of finite prime fields, and IICA (improved Index Calculus algorithm) is an improved algorithm based on IC in the third stage. The essence of IICA is to convert the number required to solve the discrete logarithm into the product of the power of prime factors, and then multiply every prime factor larger than the smooth bound by a smooth number approximating a large prime p from the right end, that is, to perform congruence transformation for every prime factor larger than the smooth bound. If all prime factors larger than the smooth bound fall within the smooth bound, the number required to solve the discrete logarithm is successfully solved. Unfortunately, given a large prime number p, some prime factors do not have congruent transformations of smooth numbers. For this, this paper analyzes the features of the IICA algorithm, based on the characteristics of IICA algorithm, is given when the IICA algorithm cannot undertake congruence transformation termination conditions, namely when ⌈ p/p_i ⌉ not smooth algorithm is terminated, where p_i is greater than a smooth boundary element factor. According to the ⌈ p/p_i ⌉ not smooth algorithm was terminated when judging conditions, optimized the IICA algorithm, and the correctness of the optimization algorithm is verified by an example.

Published in	Mathematics and Computer Science (Volume 8, Issue 2)
DOI	10.11648/j.mcs.20230802.14
Page(s)	57-61
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2023. Published by Science Publishing Group

Keywords

Discrete Logarithm, Decomposition Base, Smooth Boundary, Factorization, Prime Finite Fields

References

[1]	Adleman L M. A subexponential algorithm for discrete logarithms with applications to cryptography [C]. Proc. 20th IEEE Found. Comp. Sei. Symp., IEEE Computer Society, Long Beach, CA, 1979, 55-60.
[2]	Adleman L M, Demarrais J. A subexponential algorithm for discrete logarithms over all finite fields [J]. Mathematics of computation, 1993, 61 (203): 1-15.
[3]	Andreas E, Pierrick G. A general framework for subexponential discrete logarithm algorithms [J]. Acta Arithmetica, 2002, 102: 83-103.
[4]	Enge A, Gaudry P, Thomé E. An L (1/3) discrete logarithm algorithm for low degree curves [J]. Journal of Cryptology, 2011, 24 (1): 24-41.
[5]	Padmavathy R, Bhagvati C. Index calculus method based on smooth numbers of ±1 over Z* p [J]. International Journal of Network Security, 2013, 15 (1): 210-218.
[6]	Gretel S S. A brief survey of the discrete logarithm problem [D]. University of Hawaii at Manoa, 2011.
[7]	Hu Jianjun, Wang Wei, Li Hengjie. An improved Index Calculus algorithm [J]. Journal of Nanchang University (Engineering & Technology), 2016, 38 (3): 286-289.
[8]	Mukhopadhyay M. Aspects of Index Calculus Algorithms for Discrete Logarithm and Class Group Computations [D]. Indian Statistical Institute, Kolkata, 2021.
[9]	Zhang Mingyao, Zhang Fan. Concrete Mathematics: Fundamentals of Computer Science (Second Edition) [M]. Beijing: Posts and Telecommunications Press, 2013.
[10]	Hu Jianjun. A discrete logarithm solution method based on ICA [J]. Engineering Journal of Wuhan University, 2021, 54 (9): 874-878.
[11]	Victor Shoup. A Computational Introduction to Number Theory and Algebra (BETA version 3) [M]. London: Cambridge University Press, 2004.
[12]	Howell J S. The Index Calculus Algorithm for Discrete Logarithms [D]. Clemson University, 1998.
[13]	Silverman J H, Suzuki J. Elliptic curve discrete logarithms and the index calculus [C]. International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 1998: 110-125.
[14]	Padmavathy R, Bhagvati C. Performance analysis of index calculus method [J]. Journal of Discrete Mathematical Sciences and Cryptography, 2009, 12 (3): 353-371.
[15]	Galbraith S D, Zobernig L. Obfuscated fuzzy hamming distance and conjunctions from subset product problems [C] // Theory of Cryptography: 17th International Conference, TCC 2019, Nuremberg, Germany, December 1–5, 2019, Proceedings, Part I. Cham: Springer International Publishing, 2019: 81-110.
[16]	De Micheli G, Gaudry P, Pierrot C. Asymptotic complexities of discrete logarithm algorithms in pairing-relevant finite fields [C] // Advances in Cryptology–CRYPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020, Proceedings, Part II 40. Springer International Publishing, 2020: 32-61.
[17]	Mukhopadhyay M, Sarkar P. Pseudo-Random Walk on Ideals: Practical Speed-Up in Relation Collection for Class Group Computation [J]. Cryptology ePrint Archive, 2021.

Cite This Article

Plain Text BibTeX RIS

APA Style

Hu Jianjun. (2023). Analysis and Optimization of Improved Index Calculus Algorithm. Mathematics and Computer Science, 8(2), 57-61. https://doi.org/10.11648/j.mcs.20230802.14

Copy | Download

ACS Style

Hu Jianjun. Analysis and Optimization of Improved Index Calculus Algorithm. Math. Comput. Sci. 2023, 8(2), 57-61. doi: 10.11648/j.mcs.20230802.14

Copy | Download

AMA Style

Hu Jianjun. Analysis and Optimization of Improved Index Calculus Algorithm. Math Comput Sci. 2023;8(2):57-61. doi: 10.11648/j.mcs.20230802.14

Copy | Download

@article{10.11648/j.mcs.20230802.14,
  author = {Hu Jianjun},
  title = {Analysis and Optimization of Improved Index Calculus Algorithm},
  journal = {Mathematics and Computer Science},
  volume = {8},
  number = {2},
  pages = {57-61},
  doi = {10.11648/j.mcs.20230802.14},
  url = {https://doi.org/10.11648/j.mcs.20230802.14},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.mcs.20230802.14},
  abstract = {IC (Index Calculus) algorithm is the most effective probability algorithm for solving discrete logarithm of finite prime fields, and IICA (improved Index Calculus algorithm) is an improved algorithm based on IC in the third stage. The essence of IICA is to convert the number required to solve the discrete logarithm into the product of the power of prime factors, and then multiply every prime factor larger than the smooth bound by a smooth number approximating a large prime p from the right end, that is, to perform congruence transformation for every prime factor larger than the smooth bound. If all prime factors larger than the smooth bound fall within the smooth bound, the number required to solve the discrete logarithm is successfully solved. Unfortunately, given a large prime number p, some prime factors do not have congruent transformations of smooth numbers. For this, this paper analyzes the features of the IICA algorithm, based on the characteristics of IICA algorithm, is given when the IICA algorithm cannot undertake congruence transformation termination conditions, namely when  ⌈ p/pi ⌉ not smooth algorithm is terminated, where pi is greater than a smooth boundary element factor. According to the ⌈ p/pi ⌉ not smooth algorithm was terminated when judging conditions, optimized the IICA algorithm, and the correctness of the optimization algorithm is verified by an example.},
 year = {2023}
}

Copy | Download

TY  - JOUR
T1  - Analysis and Optimization of Improved Index Calculus Algorithm
AU  - Hu Jianjun
Y1  - 2023/04/13
PY  - 2023
N1  - https://doi.org/10.11648/j.mcs.20230802.14
DO  - 10.11648/j.mcs.20230802.14
T2  - Mathematics and Computer Science
JF  - Mathematics and Computer Science
JO  - Mathematics and Computer Science
SP  - 57
EP  - 61
PB  - Science Publishing Group
SN  - 2575-6028
UR  - https://doi.org/10.11648/j.mcs.20230802.14
AB  - IC (Index Calculus) algorithm is the most effective probability algorithm for solving discrete logarithm of finite prime fields, and IICA (improved Index Calculus algorithm) is an improved algorithm based on IC in the third stage. The essence of IICA is to convert the number required to solve the discrete logarithm into the product of the power of prime factors, and then multiply every prime factor larger than the smooth bound by a smooth number approximating a large prime p from the right end, that is, to perform congruence transformation for every prime factor larger than the smooth bound. If all prime factors larger than the smooth bound fall within the smooth bound, the number required to solve the discrete logarithm is successfully solved. Unfortunately, given a large prime number p, some prime factors do not have congruent transformations of smooth numbers. For this, this paper analyzes the features of the IICA algorithm, based on the characteristics of IICA algorithm, is given when the IICA algorithm cannot undertake congruence transformation termination conditions, namely when  ⌈ p/pi ⌉ not smooth algorithm is terminated, where pi is greater than a smooth boundary element factor. According to the ⌈ p/pi ⌉ not smooth algorithm was terminated when judging conditions, optimized the IICA algorithm, and the correctness of the optimization algorithm is verified by an example.
VL  - 8
IS  - 2
ER  -

Copy | Download

Author Information

Hu Jianjun

School of Digital Media, Lanzhou University of Arts and Science, Lanzhou, China

Download PDF

Sections

Plain Text BibTeX RIS

APA Style

Hu Jianjun. (2023). Analysis and Optimization of Improved Index Calculus Algorithm. Mathematics and Computer Science, 8(2), 57-61. https://doi.org/10.11648/j.mcs.20230802.14

Copy | Download

ACS Style

Hu Jianjun. Analysis and Optimization of Improved Index Calculus Algorithm. Math. Comput. Sci. 2023, 8(2), 57-61. doi: 10.11648/j.mcs.20230802.14

Copy | Download

AMA Style

Hu Jianjun. Analysis and Optimization of Improved Index Calculus Algorithm. Math Comput Sci. 2023;8(2):57-61. doi: 10.11648/j.mcs.20230802.14

Copy | Download

@article{10.11648/j.mcs.20230802.14,
  author = {Hu Jianjun},
  title = {Analysis and Optimization of Improved Index Calculus Algorithm},
  journal = {Mathematics and Computer Science},
  volume = {8},
  number = {2},
  pages = {57-61},
  doi = {10.11648/j.mcs.20230802.14},
  url = {https://doi.org/10.11648/j.mcs.20230802.14},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.mcs.20230802.14},
  abstract = {IC (Index Calculus) algorithm is the most effective probability algorithm for solving discrete logarithm of finite prime fields, and IICA (improved Index Calculus algorithm) is an improved algorithm based on IC in the third stage. The essence of IICA is to convert the number required to solve the discrete logarithm into the product of the power of prime factors, and then multiply every prime factor larger than the smooth bound by a smooth number approximating a large prime p from the right end, that is, to perform congruence transformation for every prime factor larger than the smooth bound. If all prime factors larger than the smooth bound fall within the smooth bound, the number required to solve the discrete logarithm is successfully solved. Unfortunately, given a large prime number p, some prime factors do not have congruent transformations of smooth numbers. For this, this paper analyzes the features of the IICA algorithm, based on the characteristics of IICA algorithm, is given when the IICA algorithm cannot undertake congruence transformation termination conditions, namely when  ⌈ p/pi ⌉ not smooth algorithm is terminated, where pi is greater than a smooth boundary element factor. According to the ⌈ p/pi ⌉ not smooth algorithm was terminated when judging conditions, optimized the IICA algorithm, and the correctness of the optimization algorithm is verified by an example.},
 year = {2023}
}

Copy | Download

TY  - JOUR
T1  - Analysis and Optimization of Improved Index Calculus Algorithm
AU  - Hu Jianjun
Y1  - 2023/04/13
PY  - 2023
N1  - https://doi.org/10.11648/j.mcs.20230802.14
DO  - 10.11648/j.mcs.20230802.14
T2  - Mathematics and Computer Science
JF  - Mathematics and Computer Science
JO  - Mathematics and Computer Science
SP  - 57
EP  - 61
PB  - Science Publishing Group
SN  - 2575-6028
UR  - https://doi.org/10.11648/j.mcs.20230802.14
AB  - IC (Index Calculus) algorithm is the most effective probability algorithm for solving discrete logarithm of finite prime fields, and IICA (improved Index Calculus algorithm) is an improved algorithm based on IC in the third stage. The essence of IICA is to convert the number required to solve the discrete logarithm into the product of the power of prime factors, and then multiply every prime factor larger than the smooth bound by a smooth number approximating a large prime p from the right end, that is, to perform congruence transformation for every prime factor larger than the smooth bound. If all prime factors larger than the smooth bound fall within the smooth bound, the number required to solve the discrete logarithm is successfully solved. Unfortunately, given a large prime number p, some prime factors do not have congruent transformations of smooth numbers. For this, this paper analyzes the features of the IICA algorithm, based on the characteristics of IICA algorithm, is given when the IICA algorithm cannot undertake congruence transformation termination conditions, namely when  ⌈ p/pi ⌉ not smooth algorithm is terminated, where pi is greater than a smooth boundary element factor. According to the ⌈ p/pi ⌉ not smooth algorithm was terminated when judging conditions, optimized the IICA algorithm, and the correctness of the optimization algorithm is verified by an example.
VL  - 8
IS  - 2
ER  -

Copy | Download