Parallel computation of division over gf(2n) covering divide-by-zero based on tile assembly model

Yongnan Li; Limin Xiao

doi:10.1109/ISPA-BDCloud-SustainCom-SocialCom48970.2019.00080

Parallel computation of division over gf(2ⁿ) covering divide-by-zero based on tile assembly model

Yongnan Li
, Limin Xiao

School of Computer Science and Engineering

Chinese People's Public Security University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

Abstract

This paper proposes how to compute division over finite field GF(2ⁿ) that could cover the case of zero divisor based on tile assembly model. Key functions are accomplished by combining n final configurations of two different sub-models. The final configuration of every sub-model contains 2n²-n computation tiles which perform 10 different functions. The coding ways of most computation tiles are optimized than the previous model to improve the complexity. The highest bit of modulus number is omitted to simplify the encoding way of computation tiles in the assembly process. This model requires 4591 types of computation tiles and 13 types of boundary tiles. The assembly time complexity is 2n²-1 and the space complexity is n⁴.

Original language	English
Title of host publication	Proceedings - 2019 IEEE Intl Conf on Parallel and Distributed Processing with Applications, Big Data and Cloud Computing, Sustainable Computing and Communications, Social Computing and Networking, ISPA/BDCloud/SustainCom/SocialCom 2019
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	526-533
Number of pages	8
ISBN (Electronic)	9781728143286
DOIs	https://doi.org/10.1109/ISPA-BDCloud-SustainCom-SocialCom48970.2019.00080
State	Published - Dec 2019
Event	17th IEEE International Conference on Parallel and Distributed Processing with Applications, 9th IEEE International Conference on Big Data and Cloud Computing, 9th IEEE International Conference on Sustainable Computing and Communications, 12th IEEE International Conference on Social Computing and Networking, ISPA/BDCloud/SustainCom/SocialCom 2019 - Xiamen, China Duration: 16 Dec 2019 → 18 Dec 2019

Publication series

Name	Proceedings - 2019 IEEE Intl Conf on Parallel and Distributed Processing with Applications, Big Data and Cloud Computing, Sustainable Computing and Communications, Social Computing and Networking, ISPA/BDCloud/SustainCom/SocialCom 2019

Conference

Conference	17th IEEE International Conference on Parallel and Distributed Processing with Applications, 9th IEEE International Conference on Big Data and Cloud Computing, 9th IEEE International Conference on Sustainable Computing and Communications, 12th IEEE International Conference on Social Computing and Networking, ISPA/BDCloud/SustainCom/SocialCom 2019
Country/Territory	China
City	Xiamen
Period	16/12/19 → 18/12/19

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 7 Affordable and Clean Energy

Keywords

Divide-by-zero
Division
Finite field gf(2)
Parallel computing
Tile assembly model

Access to Document

10.1109/ISPA-BDCloud-SustainCom-SocialCom48970.2019.00080

Cite this

Li, Y., & Xiao, L. (2019). Parallel computation of division over gf(2ⁿ) covering divide-by-zero based on tile assembly model. In Proceedings - 2019 IEEE Intl Conf on Parallel and Distributed Processing with Applications, Big Data and Cloud Computing, Sustainable Computing and Communications, Social Computing and Networking, ISPA/BDCloud/SustainCom/SocialCom 2019 (pp. 526-533). Article 9047447 (Proceedings - 2019 IEEE Intl Conf on Parallel and Distributed Processing with Applications, Big Data and Cloud Computing, Sustainable Computing and Communications, Social Computing and Networking, ISPA/BDCloud/SustainCom/SocialCom 2019). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISPA-BDCloud-SustainCom-SocialCom48970.2019.00080

Li, Yongnan ; Xiao, Limin. / Parallel computation of division over gf(2ⁿ) covering divide-by-zero based on tile assembly model. Proceedings - 2019 IEEE Intl Conf on Parallel and Distributed Processing with Applications, Big Data and Cloud Computing, Sustainable Computing and Communications, Social Computing and Networking, ISPA/BDCloud/SustainCom/SocialCom 2019. Institute of Electrical and Electronics Engineers Inc., 2019. pp. 526-533 (Proceedings - 2019 IEEE Intl Conf on Parallel and Distributed Processing with Applications, Big Data and Cloud Computing, Sustainable Computing and Communications, Social Computing and Networking, ISPA/BDCloud/SustainCom/SocialCom 2019).

@inproceedings{ed576f415f18437fad8610f59032d8a2,

title = "Parallel computation of division over gf(2n) covering divide-by-zero based on tile assembly model",

abstract = "This paper proposes how to compute division over finite field GF(2n) that could cover the case of zero divisor based on tile assembly model. Key functions are accomplished by combining n final configurations of two different sub-models. The final configuration of every sub-model contains 2n2-n computation tiles which perform 10 different functions. The coding ways of most computation tiles are optimized than the previous model to improve the complexity. The highest bit of modulus number is omitted to simplify the encoding way of computation tiles in the assembly process. This model requires 4591 types of computation tiles and 13 types of boundary tiles. The assembly time complexity is 2n2-1 and the space complexity is n4.",

keywords = "Divide-by-zero, Division, Finite field gf(2), Parallel computing, Tile assembly model",

author = "Yongnan Li and Limin Xiao",

note = "Publisher Copyright: {\textcopyright} 2019 IEEE.; 17th IEEE International Conference on Parallel and Distributed Processing with Applications, 9th IEEE International Conference on Big Data and Cloud Computing, 9th IEEE International Conference on Sustainable Computing and Communications, 12th IEEE International Conference on Social Computing and Networking, ISPA/BDCloud/SustainCom/SocialCom 2019 ; Conference date: 16-12-2019 Through 18-12-2019",

year = "2019",

month = dec,

doi = "10.1109/ISPA-BDCloud-SustainCom-SocialCom48970.2019.00080",

language = "英语",

series = "Proceedings - 2019 IEEE Intl Conf on Parallel and Distributed Processing with Applications, Big Data and Cloud Computing, Sustainable Computing and Communications, Social Computing and Networking, ISPA/BDCloud/SustainCom/SocialCom 2019",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "526--533",

booktitle = "Proceedings - 2019 IEEE Intl Conf on Parallel and Distributed Processing with Applications, Big Data and Cloud Computing, Sustainable Computing and Communications, Social Computing and Networking, ISPA/BDCloud/SustainCom/SocialCom 2019",

address = "美国",

}

Li, Y & Xiao, L 2019, Parallel computation of division over gf(2ⁿ) covering divide-by-zero based on tile assembly model. in Proceedings - 2019 IEEE Intl Conf on Parallel and Distributed Processing with Applications, Big Data and Cloud Computing, Sustainable Computing and Communications, Social Computing and Networking, ISPA/BDCloud/SustainCom/SocialCom 2019., 9047447, Proceedings - 2019 IEEE Intl Conf on Parallel and Distributed Processing with Applications, Big Data and Cloud Computing, Sustainable Computing and Communications, Social Computing and Networking, ISPA/BDCloud/SustainCom/SocialCom 2019, Institute of Electrical and Electronics Engineers Inc., pp. 526-533, 17th IEEE International Conference on Parallel and Distributed Processing with Applications, 9th IEEE International Conference on Big Data and Cloud Computing, 9th IEEE International Conference on Sustainable Computing and Communications, 12th IEEE International Conference on Social Computing and Networking, ISPA/BDCloud/SustainCom/SocialCom 2019, Xiamen, China, 16/12/19. https://doi.org/10.1109/ISPA-BDCloud-SustainCom-SocialCom48970.2019.00080

Parallel computation of division over gf(2ⁿ) covering divide-by-zero based on tile assembly model. / Li, Yongnan; Xiao, Limin.
Proceedings - 2019 IEEE Intl Conf on Parallel and Distributed Processing with Applications, Big Data and Cloud Computing, Sustainable Computing and Communications, Social Computing and Networking, ISPA/BDCloud/SustainCom/SocialCom 2019. Institute of Electrical and Electronics Engineers Inc., 2019. p. 526-533 9047447 (Proceedings - 2019 IEEE Intl Conf on Parallel and Distributed Processing with Applications, Big Data and Cloud Computing, Sustainable Computing and Communications, Social Computing and Networking, ISPA/BDCloud/SustainCom/SocialCom 2019).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Parallel computation of division over gf(2n) covering divide-by-zero based on tile assembly model

AU - Li, Yongnan

AU - Xiao, Limin

PY - 2019/12

Y1 - 2019/12

N2 - This paper proposes how to compute division over finite field GF(2n) that could cover the case of zero divisor based on tile assembly model. Key functions are accomplished by combining n final configurations of two different sub-models. The final configuration of every sub-model contains 2n2-n computation tiles which perform 10 different functions. The coding ways of most computation tiles are optimized than the previous model to improve the complexity. The highest bit of modulus number is omitted to simplify the encoding way of computation tiles in the assembly process. This model requires 4591 types of computation tiles and 13 types of boundary tiles. The assembly time complexity is 2n2-1 and the space complexity is n4.

AB - This paper proposes how to compute division over finite field GF(2n) that could cover the case of zero divisor based on tile assembly model. Key functions are accomplished by combining n final configurations of two different sub-models. The final configuration of every sub-model contains 2n2-n computation tiles which perform 10 different functions. The coding ways of most computation tiles are optimized than the previous model to improve the complexity. The highest bit of modulus number is omitted to simplify the encoding way of computation tiles in the assembly process. This model requires 4591 types of computation tiles and 13 types of boundary tiles. The assembly time complexity is 2n2-1 and the space complexity is n4.

KW - Divide-by-zero

KW - Division

KW - Finite field gf(2)

KW - Parallel computing

KW - Tile assembly model

UR - https://www.scopus.com/pages/publications/85085486534

U2 - 10.1109/ISPA-BDCloud-SustainCom-SocialCom48970.2019.00080

DO - 10.1109/ISPA-BDCloud-SustainCom-SocialCom48970.2019.00080

M3 - 会议稿件

AN - SCOPUS:85085486534

T3 - Proceedings - 2019 IEEE Intl Conf on Parallel and Distributed Processing with Applications, Big Data and Cloud Computing, Sustainable Computing and Communications, Social Computing and Networking, ISPA/BDCloud/SustainCom/SocialCom 2019

SP - 526

EP - 533

BT - Proceedings - 2019 IEEE Intl Conf on Parallel and Distributed Processing with Applications, Big Data and Cloud Computing, Sustainable Computing and Communications, Social Computing and Networking, ISPA/BDCloud/SustainCom/SocialCom 2019

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 17th IEEE International Conference on Parallel and Distributed Processing with Applications, 9th IEEE International Conference on Big Data and Cloud Computing, 9th IEEE International Conference on Sustainable Computing and Communications, 12th IEEE International Conference on Social Computing and Networking, ISPA/BDCloud/SustainCom/SocialCom 2019

Y2 - 16 December 2019 through 18 December 2019

ER -

Li Y, Xiao L. Parallel computation of division over gf(2ⁿ) covering divide-by-zero based on tile assembly model. In Proceedings - 2019 IEEE Intl Conf on Parallel and Distributed Processing with Applications, Big Data and Cloud Computing, Sustainable Computing and Communications, Social Computing and Networking, ISPA/BDCloud/SustainCom/SocialCom 2019. Institute of Electrical and Electronics Engineers Inc. 2019. p. 526-533. 9047447. (Proceedings - 2019 IEEE Intl Conf on Parallel and Distributed Processing with Applications, Big Data and Cloud Computing, Sustainable Computing and Communications, Social Computing and Networking, ISPA/BDCloud/SustainCom/SocialCom 2019). doi: 10.1109/ISPA-BDCloud-SustainCom-SocialCom48970.2019.00080