The Applications of Algebraic Polynomial Rings in Satellite Coding and Cryptography

Document Type : Review Articles


1 Department of Fundamental Sciences Marand Faculty of Engineering University of Tabriz Tabriz, I. R. Iran

2 Department of Geomatics Engineering Marand Faculty of Engineering University of Tabriz Tabriz, I. R. Iran


This survey illustrates and investigates the application of polynomial rings over finite fields to generate PRN codes for Global Navigation Satellite System (GNSS) satellites. In GNSS, satellites continually broadcast signals at two or more frequencies, including pseudo-random noise (PRN) codes. Each GNSS satellite has its own PRN code, and due to the unique mathematical properties of PRN codes, all satellites can communicate at the same frequency without interfering with another one. Although PRN code appears to be devoid of any discernible structure, it is composed of a deterministic series of pulses that will repeat itself after its period. The PRN code generator employs two shift registers known as Gold polynomials, and the suitable polynomial is decided by the number of satellites. The approach used in satellites is based on the usage of two primitive polynomials, with the output of the first polynomial being used as input for the second polynomial.


[1] F. Arnault, T. Berger, M. Minier and B. Pousse, Revisiting LFSRs for cryptographic applications, IEEE Trans. Inf. Theory 57 (12) (2011) 8095 - 8113.
[2] J. L. Awange and J. B. Kyalo Kiema, Modernization of GNSS, In: Environmental Geoinformatics, Environmental Science and Engineering, Springer, Berlin, Heidelberg (2013) pp.
47 - 54.
[3] R. Chaudhary and V. Gupta, Error control techniques and their applications,
Int. J. Comput. Appl. Eng. Sci. I (II) (2011) 187 - 191.
[4] C. Flaut, Some application of difference equations in cryptography and coding theory,
J. Difference Equ. Appl. 25 (7) (2019) 905 - 920.
[5] M. S. Grewal, A. P. Andrews and C. G. Bartone, Global Navigation Satellite Systems, Inertial Navigation, and Integration, 4th ed., John Wiley & Sons Inc., Hoboken, NJ, 2020.
[6] G. N. Gulak, Method for constructing primitive polynomials for cryptographic subsystems of dependable automated systems,
J. Automation Inf. Sci. 52 (12) (2020) 52 - 57.
[7] W. Guo and F. W. Fu, Semilinear transformations in coding theory and their application to cryptography,
arXiv : 2107.03157 (2020).
[8] M. M. Hafidhi, E. Boutillon and C. Winstead, Reliable gold code generators for GPS receivers, In: IEEE
58th Int. Midwest Symposium on Circuits and Systems (MWSCAS), ort Collins, CO (2015) pp. 1 - 4.
[9] D. Harris, L. Black, P. Hernandez-Martinez, B. Pepin, J. Williams and W. T. T. Team, Mathematics and its value for engineering students: what are the implications for teaching?,
Int. J. Math. Edu. Sci. Tech. 46 (3) (2015) 321 - 336.
[10] C. J. Hegarty, GNSS signals-An overview, In: IEEE Int. Frequency Control Symposium Proc., Baltimore, MD, USA (2012) pp.
1 - 7.
[11] C. J. Hegarty, A simple model for GPS C/A-code self-interference,
J. Institute Navigation 67 (2) (2020) 319 - 331.
[12] M. Hell, Using coding techniques to analyze weak feedback polynomials, In: IEEE Int. Symposium Inf. Theory, Austin, TX, USA (2010) pp.
2523 - 2527.
[13] G. I. Ivchenko, Y. I. Medvedev and V. A. Mironova, Krawtchouk polynomials and their applications in cryptography and coding theory,
Mat. Vopr. Kriptogr. 6 (1) (2015) 33 - 56.
[14] B. P. Kumar and C. S. Paidimarry, Development and analysis of C/A code generation of GPS receiver in FPGA and DSP, In: Proc. Conf. Recent Adv. Eng. Comput. Sci. (RAECS), Chandigarh, India (2014) pp. 1 - 5.
[15] R. B. Langley, P. J. Teunissen and O. Montenbruck,
Introduction to GNSS, In: P. J. Teunissen and O. Montenbruck (eds) Springer Handbook of Global Navigation Satellite Systems, Springer Handbooks, Springer, Cham, 2017.
[16] W. Lechner and S. Baumann, Global navigation satellite systems,
Comput. Elect. Agriculture 25 (1-2) (2000) 67 - 85.
[17] J. L. Massey, A short introduction to coding theory and practice, In: Proc. Int. Symp. on Signals, Systems and Electronics (ISSSE ’89), Erlangen, Germany (1989) pp.
6:29 - 6:33.
[18] S. Mesnager, Semi-bent functions from oval polynomials, In: Stam, M. (ed.), IMA Int. Conf. Cryptography and Coding (IMACC 2013), LNCS, Vol. 8308, Springer, Heidelberg (2013) pp.
1 - 15.
[19] I. Muchtadi-Alamsyah, Algebraic structures in cryptography, Proc. Int. Conf. Math. Sci. (Keynote Speaker), 2011.
[20] M. W. Paryasto, B. Rahardjo, I. Muchtadi-Alamsyah and M. Hafiz, Implementation of Polynomial-ONB I Basis Conversion,
J. Ilmiah Teknik Komputer i (2) (2010).
[21] S. Puchinger and A. Wachter-Zeh, Fast operations on linearized polynomials and their applications in coding theory,
J. Symb. Comput. 89 (2018) 194–215.
[22] C. Shi and N. Wei,
Satellite Navigation for Digital Earth, In: H. Guo, M. F. Goodchild, A. Annoni, (eds) Manual of Digital Earth, Springer, Singapore, 2020.
[23] D. Torrieri,
Principles of Spread-Spectrum Communication Systems, Maryland: Springer International Publishing Switzerland, 2015.
[24] H. N. Viet, K. R. Kwon, K. S. Moon and S. H. Lee, Simulation model implementation of GPS IF signal generator,
Int. Conf. Inf. Commun. (ICIC), Hanoi, Vietnam (2017) 17084069.
[25] S. Wallner, J. -A. Avila-Rodriguez, G. W. Hein and J. J. Rushanan, Galileo E1 OS and GPS L1C pseudo-random noise codes-requirements, generation, optimization and comparison, Proc.
20th Int. Technical Meeting of the Satellite Division of The Institute of Navigation (ION-GNSS 2007) (2007) pp. 1549 - 1563.
[26] W. Guan, Y. Wu, S. Wen, C. Yang, H. Chen, Z. Zhang and Y. Chen, High precision three-dimensional iterative indoor localization algorithm using code division multiple access modulation based on visible light communication, Optical Eng. 55 (10) (2016) 106105.
[27] L. Winternitz, Introduction to GPS and other global navigation satellite systems, In: Annual Time and Frequency Metrology Seminar, no. GSFC-E-DAATN42241, 2017.
[28] J. Xie, H. Wang, P. Li and Y. Meng,
Satellite Navigation Systems and Technologies, Springer, Singapore, 2021.
[29] Y. Zheng, A note on a class of permutation polynomials,
4th Int. Conf. Emerging Intelligent Data and Web Technologies (EIDWT) (2013) pp. 302 - 306.
[30] Y. Zheng, Q. Wang and W. Wei, On inverses of permutation polynomials of small degree over finite fields,
IEEE Trans. Inf. Theory 66 (2) (2019) 914 - 922.