Jacobi Symbol Parity Checking Algorithm for Subset Product

Trey Li

Paper 2022/1308

Jacobi Symbol Parity Checking Algorithm for Subset Product

Trey Li

Abstract

It is well-known that the subset product problem is NP-hard. We give a probabilistic polynomial time algorithm for the special case of high F_2-rank.

Note: This is the 2nd paper of the series.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: Subset product Jacobi symbol Parity checking Algorithm Characteristic matrix Rank
Contact author(s): treyquantum @ gmail com
History: 2022-10-03: approved; 2022-10-02: received; See all versions
Short URL: https://ia.cr/2022/1308
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1308,
      author = {Trey Li},
      title = {Jacobi Symbol Parity Checking Algorithm for Subset Product},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1308},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1308}},
      url = {https://eprint.iacr.org/2022/1308}
}